Submission #49743

#	Time	Username	Problem	Language	Result	Execution time	Memory
49743		dongwon0427	New Home (APIO18_new_home)	C++11	0 / 100	4239 ms	139832 KiB

new_home

/*
god taekyu
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

#define INF 210000000
#define OPEN 1
#define CLOSE 2
#define MAX 300005

int n,k,q;
struct query {
    int idx,loc,year;
};
struct store {
    int loc,type,year,status;
};

query Q[MAX];
store A[MAX*2];
vector<int> LOC;
void input() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>k>>q;
    for(int i=0;i<n;i++) {
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        a*=2;
        A[2*i] = {a,b,c,OPEN};
        A[2*i+1] = {a,b,d+1,CLOSE};
    }
    for(int i=0;i<q;i++) {
        int a,b;
        cin>>a>>b;
        a*=2;
        Q[i] = {i,a,b};
    }

    sort(A,A+2*n,[](store a,store b){return a.loc < b.loc;});
    for(int i=0;i<2*n;i++) {
        LOC.push_back(A[i].loc);
    }
    LOC.erase(unique(LOC.begin(),LOC.end()),LOC.end());

    sort(A,A+2*n,[](store a,store b){return a.year < b.year;});
    sort(Q,Q+q,[](query a,query b){return a.year < b.year;});
}

int T[MAX], T_filled = 0;
map<int,int> M[MAX]; //val, gaesu
int rightseg[4*MAX];//max
int leftseg[4*MAX]; //min
multiset<int> rightS[MAX];//max
multiset<int> leftS[MAX];//min
void updt(int seg[],int idx,int s,int e,int x,int v,int flag) {
    if(s == e) {
        seg[idx] = v;
        return;
    }
    if(x<=(s+e)/2) {
        updt(seg,idx*2,s,(s+e)/2,x,v,flag);
    } else {
        updt(seg,idx*2+1,(s+e)/2+1,e,x,v,flag);
    }
    if(flag == 0) {
        seg[idx] = max(seg[idx*2] , seg[idx*2+1]);
    } else {
        seg[idx] = min(seg[idx*2] , seg[idx*2+1]);
    }
}
void add_line(int bot,int top,int dir) {
    int idx = lower_bound(LOC.begin(),LOC.end(),bot) - LOC.begin();
    //cout<<"add : "<<bot<<" ~ "<<top<<'\n';
    if(dir == 1) {
        rightS[idx].insert(top);
        multiset<int>::iterator it = rightS[idx].end(); it--;
        updt(rightseg,1,0,n-1,idx,(*it),0);
    } else {
        leftS[idx].insert(top);
        multiset<int>::iterator it = leftS[idx].begin();
        updt(leftseg,1,0,n-1,idx,(*it),1);
    }
}
void del_line(int bot,int top,int dir) {
    //cout<<"del : "<<bot<<" ~ "<<top<<'\n';
    int idx = lower_bound(LOC.begin(),LOC.end(),bot) - LOC.begin();
    //cout<<"add : "<<bot<<" ~ "<<top<<'\n';
    if(dir == 1) {
        rightS[idx].erase(rightS[idx].find(top));
        multiset<int>::iterator it = rightS[idx].end(); it--;
        updt(rightseg,1,0,n-1,idx,(*it),0);
    } else {
        leftS[idx].erase(leftS[idx].find(top));
        multiset<int>::iterator it = leftS[idx].begin();
        updt(leftseg,1,0,n-1,idx,(*it),1);
    }
}
void _add(int loc, int type) {
    if(T[type] == 0) T_filled++;
    T[type]++;

    M[type][loc]++;

    if(M[type][loc] == 1) {
        map<int,int>::iterator it;
        int rht=INF,lft=-1;

        it = M[type].find(loc); it++;
        if(it != M[type].end()) rht = (*it).first;
        it = M[type].find(loc);
        if(it != M[type].begin()) {it--;lft = (*it).first;}

        if(rht == INF && lft == -1) {
            add_line(loc,rht,1);
            add_line(loc,lft,-1);
        } else if(rht == INF) {
            del_line(lft,INF,1);
            add_line(lft,(lft+loc)/2,1);
            add_line(loc,(lft+loc)/2,-1);
            add_line(loc,rht,1);
        } else if(lft == -1) {
            del_line(rht,-1,-1);
            add_line(rht,(loc+rht)/2,-1);
            add_line(loc,(loc+rht)/2,1);
            add_line(loc,lft,-1);
        } else {
            del_line(lft,(lft+rht)/2,1);
            del_line(rht,(lft+rht)/2,-1);
            add_line(loc,(loc+rht)/2,1);
            add_line(loc,(loc+lft)/2,-1);
            add_line(rht,(loc+rht)/2,-1);
            add_line(lft,(loc+lft)/2,1);
        }
    }

}
void _del(int loc, int type) {
    T[type]--;
    if(T[type] == 0) T_filled--;

    M[type][loc]--;
    if(M[type][loc] == 0) {
        map<int,int>::iterator it;
        int rht=INF,lft=-1;

        it = M[type].find(loc); it++;
        if(it != M[type].end()) rht = (*it).first;
        it = M[type].find(loc);
        if(it != M[type].begin()) {it--;lft = (*it).first;}

        if(rht == INF && lft == -1) {
            del_line(loc,rht,1);
            del_line(loc,lft,-1);
        } else if(rht == INF) {
            del_line(lft,(lft+loc)/2,1);
            del_line(loc,(lft+loc)/2,-1);
            del_line(loc,rht,1);
            add_line(lft,INF,1);
        } else if(lft == -1) {
            del_line(rht,(loc+rht)/2,-1);
            del_line(loc,(loc+rht)/2,1);
            del_line(loc,lft,-1);
            add_line(rht,-1,-1);
        } else {
            del_line(loc,(loc+rht)/2,1);
            del_line(loc,(loc+lft)/2,-1);
            del_line(rht,(loc+rht)/2,-1);
            del_line(lft,(loc+lft)/2,1);
            add_line(lft,(lft+rht)/2,1);
            add_line(rht,(lft+rht)/2,-1);
        }

        M[type].erase(loc);
    }
}
int leftquery(int idx,int s,int e,int v) {
    if(leftseg[idx] > v) return -1;
    if(s==e) {
        if(leftseg[idx] <= v) return s;
        return -1;
    }
    if(leftseg[idx*2+1] <= v) return leftquery(idx*2+1,(s+e)/2+1,e,v);
    return leftquery(idx*2,s,(s+e)/2,v);
}
int rightquery(int idx,int s,int e,int v) {
    if(rightseg[idx] < v) return INF;
    if(s==e) {
        if(rightseg[idx] >= v) return s;
        return INF;
    }
    if(rightseg[idx*2] >= v) return rightquery(idx*2,s,(s+e)/2,v);
    return rightquery(idx*2+1,(s+e)/2+1,e,v);
}
int main() {
    input();

    for(int i=0;i<n;i++) {
        rightS[i].insert(-1);
        updt(rightseg,1,0,n-1,i,-1,0);
        leftS[i].insert(INF);
        updt(leftseg,1,0,n-1,i,INF,1);
    }
    int Aidx = 0;
    for(int i=0;i<q;i++) {
        while(Aidx < 2*n && A[Aidx].year <= Q[i].year) {
            if(A[Aidx].status == OPEN) {
                _add(A[Aidx].loc, A[Aidx].type);
            } else {
                _del(A[Aidx].loc, A[Aidx].type);
            }
            Aidx++;
        }
        /*for(int j=4;j<=7;j++) {
            cout<<rightseg[j]<<' ';
        }
        cout<<'\n';
        for(int j=4;j<=7;j++) {
            cout<<leftseg[j]<<' ';
        }
        cout<<"\n\n";*/
        if(T_filled != k) {
            cout<<"-1\n";
        } else {
            int R = rightquery(1,0,n-1,Q[i].year);
            int L = leftquery(1,0,n-1,Q[i].year);
            //cout<<"ans : "<<LOC[R]<<' '<<LOC[L]<<'\n';
            if(R == INF && L == -1) {
                cout<<"-1\n";
            } else if(R == INF) {
                cout<<(-Q[i].loc + LOC[L])/2<<"\n";
            } else if(L == -1) {
                cout<<(-LOC[R] + Q[i].loc)/2<<"\n";
            } else {
                cout<<max((-Q[i].loc + LOC[L])/2 , (-LOC[R] + Q[i].loc)/2)<<"\n";
            }
        }
    }
    return 0;
}

/*
god taekyu
*/

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20