Gym 100231B Intervals

http://codeforces.com/gym/100231/attachments/download/1868/20132014-ct-s01e03-codeforces-trainings-season-1-episode-3-en.pdf
//
// Created by     on 16/3/6.
///
// Created by     on 16/3/6.
//
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int max_n = 50000+100;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
struct seg{
    int a,b,c;
    bool operatorconst seg& s) const {
        return bint segTree[max_n*4+10];
void pushup(int rt){
    segTree[rt] = segTree[rt<<1]+segTree[rt<<1|1];
}
void update(int p,int l,int r,int rt){
    if(l==r){
        segTree[rt] = 1;
        return;
    }
    int m = (l+r)>>1;
    if(p<=m){
        update(p,lson);
    } else{
        update(p,rson);
    }
    pushup(rt);
}
int query(int L,int R,int l,int r,int rt){
    if(L<=l&&r<=R){
        return segTree[rt];
    }
    int m = (l+r)>>1;
    int ret = 0;
    if(L<=m){
        ret+=query(L,R,lson);
    }
    if(R>m){
        ret+=query(L,R,rson);
    }
    return ret;
}
vector<int> p;
bool isexist[max_n];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    p.clear();
    while (cin>>n){
        memset(isexist,0, sizeof(isexist));
        memset(segTree,0, sizeof(segTree));
        int ans = 0;
        for(int i = 0;icin>>s[i].a>>s[i].b>>s[i].c;
        }
        sort(s,s+n);
        for(int i = 0;iint num = 0;
            num = query(s[i].a,s[i].b,1,50000,1);
            if(num>=s[i].c){
                continue;
            } else{
                int cnt = s[i].c-num;
                int it = 0;
                int pos = 0;
                while (itif(!isexist[s[i].b-pos]){
                        update(s[i].b-pos,1,50000,1);
                        isexist[s[i].b-pos] = true;
                        it++;
                        ans++;
                    }
                    pos++;
                }
            }
        }
        cout<return 0;
}

좋은 웹페이지 즐겨찾기