Submission #1207140

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207140		lighton	New Home (APIO18_new_home)	C++17	100 / 100	2173 ms	223816 KiB

new_home

#include<bits/stdc++.h>
#define pb push_back
#define all(v) v.begin(),v.end()
#define forf(i,s,e) for(int i = s; i<=e; i++)
#define forb(i,s,e) for(int i = s; i>=e; i--)
#define idx(i,v) lower_bound(all(v),i)-v.begin()
#define comp(v) v.erase(unique(all(v)),v.end())
#define sz(v) (int)v.size()
#define fs first
#define se second
#define SP << " " <<
#define LN << "\n"
#define IO cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
ll inf = 1e17;
int N,M,Q;

struct Seg{
    ll arr[8000001];
    void update(int now, int s, int e, int f, ll x){
        if(s==e){
            arr[now] = x;
            return;
        }
        int m = s+e>>1;
        if(f<=m) update(now*2,s,m,f,x);
        else update(now*2+1,m+1,e,f,x);
        arr[now] = max(arr[now*2],arr[now*2+1]);
    }
    ll query(int now, int s, int e, int l, int r){
        if(l>r) return -inf;
        if(l<=s && e<=r) return arr[now];
        if(l>e || r<s) return -inf;
        int m = s+e>>1;
        return max(query(now*2,s,m,l,r) , query(now*2+1,m+1,e,l,r));
    }
} s1,s2;

vector<array<ll,4> > events;
multiset<ll> S[1000001];
vector<pair<ll,ll> > P;
ll ans[1000001];

int main(){
    IO
    cin>>N>>M>>Q;
    forf(i,1,N){
        ll x,t,a,b;
        cin>>x>>t>>a>>b;
        events.pb({a,-t,2*x,i});
        events.pb({b,t,2*x,i});
    }
    forf(i,1,Q){
        ll l,y; cin>>l>>y;
        events.pb({y,0,2*l,i});
    }
    sort(all(events));

    //#1
    forf(i,1,M) S[i].insert(-inf), S[i].insert(inf), P.pb({0,i});
    for(auto [t,c,x,id] : events){
        if(c < 0){
            c*= -1;
            auto it = S[c].lower_bound(x);
            ll nxt = *it, prv =*prev(it);
            S[c].insert(x);
            if(x==nxt) continue;
            P.pb({(x+nxt)/2, c}), P.pb({(prv+x)/2, c});
        }
        else if(c > 0){
            S[c].erase(S[c].find(x));
            auto it = S[c].upper_bound(x);
            ll nxt = *it, prv =*prev(it);
            if(x==nxt) continue;
            P.pb({(prv+nxt)/2, c});
        }
    }
    sort(all(P));

    //#2
    forf(i,1,sz(P)) s1.update(1,1,sz(P),i,-inf), s2.update(1,1,sz(P),i,-inf);
    forf(i,1,M){
        s1.update(1,1,sz(P),idx(make_pair(0LL,(ll)i),P)+1,inf);
        s2.update(1,1,sz(P),idx(make_pair(0LL,(ll)i),P)+1,inf);
    }
    for(auto [t,c,x,id] : events){
        if(c < 0){
            c*= -1;
            auto it = S[c].lower_bound(x);
            ll nxt = *it, prv =*prev(it);
            S[c].insert(x);
            if(x==nxt) continue;
            ll orgp = (nxt+prv)/2, nxtp = (x+nxt)/2, prvp = (x+prv)/2;
            s1.update(1,1,sz(P),idx(make_pair(orgp,c),P)+1, -inf);
            s2.update(1,1,sz(P),idx(make_pair(orgp,c),P)+1, -inf);
            s1.update(1,1,sz(P),idx(make_pair(nxtp, c), P)+1, (nxt-x)/2 + nxtp);
            s2.update(1,1,sz(P),idx(make_pair(nxtp, c), P)+1, (nxt-x)/2 - nxtp);
            s1.update(1,1,sz(P),idx(make_pair(prvp, c), P)+1, (x-prv)/2 + prvp);
            s2.update(1,1,sz(P),idx(make_pair(prvp, c), P)+1, (x-prv)/2 - prvp);
        }
        else if(c > 0){
            S[c].erase(S[c].find(x));
            auto it = S[c].lower_bound(x);
            ll nxt = *it, prv =*prev(it);
            if(x==nxt) continue;
            ll orgp = (nxt+prv)/2, nxtp = (x+nxt)/2, prvp = (x+prv)/2;
            s1.update(1,1,sz(P),idx(make_pair(nxtp, c), P)+1, -inf);
            s2.update(1,1,sz(P),idx(make_pair(nxtp, c), P)+1, -inf);
            s1.update(1,1,sz(P),idx(make_pair(prvp, c), P)+1, -inf);
            s2.update(1,1,sz(P),idx(make_pair(prvp, c), P)+1, -inf);
            s1.update(1,1,sz(P),idx(make_pair(orgp,c),P)+1, (nxt-prv)/2 + orgp);
            s2.update(1,1,sz(P),idx(make_pair(orgp,c),P)+1, (nxt-prv)/2 - orgp);
        }
        else{
            ll idx = upper_bound(all(P),make_pair(x,inf)) - P.begin();
            ll t1 = s1.query(1,1,sz(P),1,idx) - x;
            ll t2 = s2.query(1,1,sz(P),idx+1,sz(P)) + x;
            ans[id] = max(t1,t2);
        }
    }
    forf(i,1,Q){
        if(ans[i] > inf/5) cout<<-1<<"\n";
        else cout<<ans[i]/2<<"\n";
    }
}

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