Submission #976779

#	Time	Username	Problem	Language	Result	Execution time	Memory
976779		lighton	New Home (APIO18_new_home)	C++17	12 / 100	1467 ms	52896 KiB

new_home

#include<bits/stdc++.h>
#define forf(i,a,b) for(int i = a; i<=b; i++)
#define all(v) v.begin(),v.end()
using namespace std;

int n,k,q;
struct event{
    int col,t,q,qnum,x; //q=-1 : add , q=0 : update , q=1 : del
    bool operator<(const event &r) const{
        if(t==r.t) return q<r.q;
        else return t<r.t;
    }
};
vector<event> events;
int ans[300001];
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>k>>q;
    forf(i,1,n){
        int x,t,a,b;
        cin>>x>>t>>a>>b;
        events.push_back({t,a,-1,0,x});
        events.push_back({t,b,1,0,x});
    }
    forf(i,1,q){
        int l,y; cin>>l>>y;
        events.push_back({0,y,0,i,l});
    }

    sort(all(events));
    multiset<int> set1[401];
    for(auto &[nowcol,nowt,nowq,nowqnum,nowx] : events){
        if(nowq == -1) set1[nowcol].insert(nowx);
        else if(nowq==0){
            int nowans = 0;
            forf(col,1,k) {

                int tmp = 1e9;
                auto it = set1[col].lower_bound(nowx);
                if (it != set1[col].end()) tmp = min(tmp, *it - nowx);
                if (it != set1[col].begin()) tmp = min(tmp, nowx - *prev(it));
                nowans = max(nowans, tmp);
            }
            if (nowans == 1e9) nowans = -1;
            ans[nowqnum] = nowans;
        }
        else set1[nowcol].erase(set1[nowcol].find(nowx));
    }
    forf(i,1,q) cout<<ans[i]<<"\n";
}

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