Submission #491597

#	Time	Username	Problem	Language	Result	Execution time	Memory
491597		leaked	New Home (APIO18_new_home)	C++14	100 / 100	4053 ms	391988 KiB

new_home

#include <bits/stdc++.h>

#define f first
#define s second
#define sz(x) (int)(x).size()
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define vec vector
#define pw(x) (1LL<<(x))
#define m_p make_pair
#define fast_iati ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

template <class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template <class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
typedef long long ll;
typedef pair<int,int> pii;

//const int lg=log2(300'000)+1;
const int N=3e6;
bool del[2*N];
struct segtree{
    int mx[4*N];
    vec<pii> wyfu;
    segtree(){
        fill(mx,mx+4*N,-1e9);
    }
    void init(){
        sort(all(wyfu));
        wyfu.erase(unique(all(wyfu)),wyfu.end());
    }
    int gi(pii x){
        return upper_bound(all(wyfu),x)-wyfu.begin()-1;
    }
    void upd(int i,int x,int v,int tl,int tr){
        if(tl==tr){
            mx[v]=x;
            return;
        }
        int tm=(tl+tr)>>1;
        if(tm>=i)
            upd(i,x,2*v,tl,tm);
        else
            upd(i,x,2*v+1,tm+1,tr);
        mx[v]=max(mx[2*v],mx[2*v+1]);
    }
    int get(int l,int r,int v,int tl,int tr){
        if(l>r)
            return -1e9;
        if(tl>=l&&tr<=r)
            return mx[v];
        if(tl>r||tr<l)
            return -1e9;
        int tm=(tl+tr)>>1;
        return max(get(l,r,2*v,tl,tm),get(l,r,2*v+1,tm+1,tr));
    }
    void _debug(int v,int tl,int tr){
        cout<<"SLOY "<<v<<' '<<tl<<' '<<tr<<' '<<mx[v]<<endl;
        if(tl==tr)
            return ;
        int tm=(tl+tr)>>1;
        _debug(2*v,tl,tm);
        _debug(2*v+1,tm+1,tr);
    }
}lft,rgt;
vec<int> kek;
vec<pii> wyfu;
//map<pii,int>mp;
int tmr;
vec<pii> toadd[N];
vec<pii> todel[N];
void add(int l,int r,int t,int tp,int w=0){
    if(l==r) return;
    int mid=(l+r)>>1;
//    cout<<"CHINGY "<<l<<' '<<r<<' '<<t<<endl;
    if(!t){
//        del[mp[{l,tp}]]=1;
        if(!w)
            return ;
        ///r>=x
        lft.upd(lft.gi({mid,tp}),-1e9,1,0,sz(lft.wyfu));
//        cout<<"DEL LFT "<<mid<<' '<<-1e9<<' '<<tp<<endl;
        ///l<=x
        rgt.upd(rgt.gi({mid+1,tp}),-1e9,1,0,sz(rgt.wyfu));
//        cout<<"DEL RGT "<<mid+1<<' '<<-1e9<<' '<<tp<<endl;
        return;
    }
    if(!w)
        rgt.wyfu.pb({mid+1,tp}),lft.wyfu.pb({mid,tp});
//    mp[{l,tp}]=tmr;
    if(w){
        ///r>=x
        lft.upd(lft.gi({mid,tp}),-l,1,0,sz(lft.wyfu));
//        cout<<"ADD LFT "<<-l<<" "<<mid<<' '<<tp<<endl;
        ///l<=x
        rgt.upd(rgt.gi({mid+1,tp}),r,1,0,sz(rgt.wyfu));
//        cout<<"ADD RGT "<<r<<' '<<mid+1<<' '<<tp<<endl;
    }
//    ++tmr;
}
const int Nax=3e5+1;
multiset<int> st[Nax];
vec<int>here[Nax];
signed main(){
    fast_iati;
    int n,q,k;
    cin>>n>>k>>q;
    vec<array<int,3>>arr;
    vec<int>x(n),a(n),b(n),t(n);
    for(int i=0;i<n;i++){
        cin>>x[i]>>t[i]>>a[i]>>b[i];
//        x[i]=rand(),t[i]=rand()%k+1;
//        a[i]=rand(),b[i]=rand();
//        if(a[i]>b[i])
//            swap(a[i],b[i]);
        arr.push_back({a[i],0,i});
        arr.push_back({b[i]+1,-1,i});
        --t[i];
        here[t[i]].pb(i);
    }
    vec<int>l(q),y(q);
    for(int i=0;i<q;i++){
        cin>>l[i]>>y[i];
//        l[i]=rand(),y[i]=rand();
        arr.push_back({y[i],2,i});
    }
    sort(all(arr));
    auto stupid=[&](array<int,3> z){
        pii me={-1e9,0};
        int tx=l[z[1]];
        for(int j=0;j<k;j++){
            if(sz(st[j])==2) continue;
            auto it=st[j].lower_bound(tx);
            int omn=2e9;
            if(it!=st[j].end()) umin(omn,*it-tx);
            if(it!=st[j].begin()) umin(omn,tx-*prev(it));
//            cout<<"COLOUR "<<j<<' '<<omn<<' '<<tx<<endl;
            umax(me.f,omn);me.s++;
        }
        return me;
    };
    vec<int>cnt(k,0);
    for(int i=0;i<k;i++){
        add(-3e8,3e8,1,i);
        st[i].insert(-3e8);st[i].insert(3e8);
    }
    int total=0;
    vec<bool>bad(q,0);
    int j=0;
    for(auto &z : arr){
        swap(z[1],z[2]);
        if(z[2]==2){
            bad[z[1]]=(total==k?0:1);
            continue;
        }
//        cout<<"AUE "<<endl;
        if(z[2]==-1){
            int i=z[1];
            auto it=st[t[i]].lower_bound(x[i]);

            todel[j].pb({x[i],*next(it)});
            todel[j].pb({*prev(it),x[i]});
            toadd[j].pb({*prev(it),*next(it)});

            add(x[i],*next(it),0,t[i]);
            add(*prev(it),x[i],0,t[i]);
            add(*prev(it),*next(it),1,t[i]);
            st[t[i]].erase(it);
            cnt[t[i]]--;
            if(!cnt[t[i]])
                total--;
        }
        else{
            int i=z[1];
            if(!cnt[t[i]])
                total++;
            cnt[t[i]]++;
            st[t[i]].insert(x[i]);
            auto it=st[t[i]].lower_bound(x[i]);
            add(*prev(it),*next(it),0,t[i]);
            add(x[i],*next(it),1,t[i]);
            add(*prev(it),x[i],1,t[i]);

            toadd[j].pb({x[i],*next(it)});
            toadd[j].pb({*prev(it),x[i]});
            todel[j].pb({*prev(it),*next(it)});
        }
        j++;
//        cout<<z[0]<<' '<<total<<endl;
    }
//    cout<<endl;
    j=0;
    ///building
    lft.init();
    rgt.init();
    vec<int> ansq(q,-1);
//    assert(total==0);
    for(auto &z : arr){
        if(z[2]==2){
            int i=z[1];
            if(bad[i])
                continue;
            int what=0;
            ///r>=x
            umax(what,l[i]+lft.get(lft.gi(m_p(l[i],-2e9))+1,sz(lft.wyfu),1,0,sz(lft.wyfu)));
//            cout<<"AFTER L "<<what<<' '<<lft.gi(m_p(l[i],-2e9))+1<<endl;
            ///x>=l
            umax(what,-l[i]+rgt.get(0,rgt.gi(m_p(l[i],2e9)),1,0,sz(rgt.wyfu)));
//            cout<<"AFTER R "<<what<<endl;
            ansq[i]=what;
            continue;
        }
        int i=z[1];
        for(auto &z : todel[j])
            add(z.f,z.s,0,t[i],1);
        for(auto &z : toadd[j])
            add(z.f,z.s,1,t[i],1);
        j++;
//        cout<<"DEBUG "<<endl;
//        lft._debug(1,0,sz(lft.wyfu));
//        cout<<z[0]<<' '<<total<<endl;
    }
    for(auto &z : ansq)
        cout<<z<<'\n';
    return 0;
}
/*

4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10


2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7

1 1 1
100000000 1 1 1
1 1
*/

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:130:10: warning: variable 'stupid' set but not used [-Wunused-but-set-variable]
  130 |     auto stupid=[&](array<int,3> z){
      |          ^~~~~~

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