oj.uz

Submission #491589

# Submission time Handle Problem Language Result Execution time Memory
491589 2021-12-03T12:19:48 Z leaked New Home (APIO18_new_home) C++14
47 / 100
 5000 ms 365280 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 256276 KB Output is correct
2 Correct 122 ms 256316 KB Output is correct
3 Correct 118 ms 256264 KB Output is correct
4 Correct 114 ms 256152 KB Output is correct
5 Correct 122 ms 256324 KB Output is correct
6 Correct 119 ms 256420 KB Output is correct
7 Correct 115 ms 256424 KB Output is correct
8 Correct 121 ms 256440 KB Output is correct
9 Correct 119 ms 256556 KB Output is correct
10 Correct 123 ms 256452 KB Output is correct
11 Correct 125 ms 256324 KB Output is correct
12 Correct 116 ms 256424 KB Output is correct
13 Correct 118 ms 256308 KB Output is correct
14 Correct 118 ms 256288 KB Output is correct
15 Correct 128 ms 256336 KB Output is correct
16 Correct 117 ms 256412 KB Output is correct
17 Correct 116 ms 256320 KB Output is correct
18 Correct 118 ms 256480 KB Output is correct
19 Correct 117 ms 256552 KB Output is correct
20 Correct 119 ms 256332 KB Output is correct
21 Correct 117 ms 256536 KB Output is correct
22 Correct 122 ms 256488 KB Output is correct
23 Correct 118 ms 256460 KB Output is correct
24 Correct 116 ms 256324 KB Output is correct
25 Correct 120 ms 256452 KB Output is correct
26 Correct 122 ms 256364 KB Output is correct
27 Correct 121 ms 256424 KB Output is correct
28 Correct 118 ms 256364 KB Output is correct
29 Correct 116 ms 256408 KB Output is correct
30 Correct 120 ms 256324 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 256276 KB Output is correct
2 Correct 122 ms 256316 KB Output is correct
3 Correct 118 ms 256264 KB Output is correct
4 Correct 114 ms 256152 KB Output is correct
5 Correct 122 ms 256324 KB Output is correct
6 Correct 119 ms 256420 KB Output is correct
7 Correct 115 ms 256424 KB Output is correct
8 Correct 121 ms 256440 KB Output is correct
9 Correct 119 ms 256556 KB Output is correct
10 Correct 123 ms 256452 KB Output is correct
11 Correct 125 ms 256324 KB Output is correct
12 Correct 116 ms 256424 KB Output is correct
13 Correct 118 ms 256308 KB Output is correct
14 Correct 118 ms 256288 KB Output is correct
15 Correct 128 ms 256336 KB Output is correct
16 Correct 117 ms 256412 KB Output is correct
17 Correct 116 ms 256320 KB Output is correct
18 Correct 118 ms 256480 KB Output is correct
19 Correct 117 ms 256552 KB Output is correct
20 Correct 119 ms 256332 KB Output is correct
21 Correct 117 ms 256536 KB Output is correct
22 Correct 122 ms 256488 KB Output is correct
23 Correct 118 ms 256460 KB Output is correct
24 Correct 116 ms 256324 KB Output is correct
25 Correct 120 ms 256452 KB Output is correct
26 Correct 122 ms 256364 KB Output is correct
27 Correct 121 ms 256424 KB Output is correct
28 Correct 118 ms 256364 KB Output is correct
29 Correct 116 ms 256408 KB Output is correct
30 Correct 120 ms 256324 KB Output is correct
31 Correct 874 ms 276952 KB Output is correct
32 Correct 306 ms 270812 KB Output is correct
33 Correct 802 ms 275680 KB Output is correct
34 Correct 841 ms 276188 KB Output is correct
35 Correct 855 ms 276712 KB Output is correct
36 Correct 844 ms 277044 KB Output is correct
37 Correct 617 ms 275592 KB Output is correct
38 Correct 569 ms 275396 KB Output is correct
39 Correct 492 ms 275248 KB Output is correct
40 Correct 509 ms 275424 KB Output is correct
41 Correct 720 ms 275264 KB Output is correct
42 Correct 718 ms 275284 KB Output is correct
43 Correct 277 ms 271696 KB Output is correct
44 Correct 723 ms 275420 KB Output is correct
45 Correct 707 ms 275376 KB Output is correct
46 Correct 658 ms 275324 KB Output is correct
47 Correct 399 ms 274256 KB Output is correct
48 Correct 388 ms 274128 KB Output is correct
49 Correct 442 ms 274584 KB Output is correct
50 Correct 473 ms 275160 KB Output is correct
51 Correct 464 ms 274636 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5059 ms 365280 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5064 ms 354744 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 256276 KB Output is correct
2 Correct 122 ms 256316 KB Output is correct
3 Correct 118 ms 256264 KB Output is correct
4 Correct 114 ms 256152 KB Output is correct
5 Correct 122 ms 256324 KB Output is correct
6 Correct 119 ms 256420 KB Output is correct
7 Correct 115 ms 256424 KB Output is correct
8 Correct 121 ms 256440 KB Output is correct
9 Correct 119 ms 256556 KB Output is correct
10 Correct 123 ms 256452 KB Output is correct
11 Correct 125 ms 256324 KB Output is correct
12 Correct 116 ms 256424 KB Output is correct
13 Correct 118 ms 256308 KB Output is correct
14 Correct 118 ms 256288 KB Output is correct
15 Correct 128 ms 256336 KB Output is correct
16 Correct 117 ms 256412 KB Output is correct
17 Correct 116 ms 256320 KB Output is correct
18 Correct 118 ms 256480 KB Output is correct
19 Correct 117 ms 256552 KB Output is correct
20 Correct 119 ms 256332 KB Output is correct
21 Correct 117 ms 256536 KB Output is correct
22 Correct 122 ms 256488 KB Output is correct
23 Correct 118 ms 256460 KB Output is correct
24 Correct 116 ms 256324 KB Output is correct
25 Correct 120 ms 256452 KB Output is correct
26 Correct 122 ms 256364 KB Output is correct
27 Correct 121 ms 256424 KB Output is correct
28 Correct 118 ms 256364 KB Output is correct
29 Correct 116 ms 256408 KB Output is correct
30 Correct 120 ms 256324 KB Output is correct
31 Correct 874 ms 276952 KB Output is correct
32 Correct 306 ms 270812 KB Output is correct
33 Correct 802 ms 275680 KB Output is correct
34 Correct 841 ms 276188 KB Output is correct
35 Correct 855 ms 276712 KB Output is correct
36 Correct 844 ms 277044 KB Output is correct
37 Correct 617 ms 275592 KB Output is correct
38 Correct 569 ms 275396 KB Output is correct
39 Correct 492 ms 275248 KB Output is correct
40 Correct 509 ms 275424 KB Output is correct
41 Correct 720 ms 275264 KB Output is correct
42 Correct 718 ms 275284 KB Output is correct
43 Correct 277 ms 271696 KB Output is correct
44 Correct 723 ms 275420 KB Output is correct
45 Correct 707 ms 275376 KB Output is correct
46 Correct 658 ms 275324 KB Output is correct
47 Correct 399 ms 274256 KB Output is correct
48 Correct 388 ms 274128 KB Output is correct
49 Correct 442 ms 274584 KB Output is correct
50 Correct 473 ms 275160 KB Output is correct
51 Correct 464 ms 274636 KB Output is correct
52 Correct 918 ms 288080 KB Output is correct
53 Correct 913 ms 287520 KB Output is correct
54 Correct 849 ms 279872 KB Output is correct
55 Correct 769 ms 279760 KB Output is correct
56 Correct 797 ms 281964 KB Output is correct
57 Correct 729 ms 276784 KB Output is correct
58 Correct 784 ms 279716 KB Output is correct
59 Correct 823 ms 281900 KB Output is correct
60 Correct 765 ms 276740 KB Output is correct
61 Correct 435 ms 288492 KB Output is correct
62 Correct 944 ms 288208 KB Output is correct
63 Correct 865 ms 281936 KB Output is correct
64 Correct 859 ms 279764 KB Output is correct
65 Correct 827 ms 276708 KB Output is correct
66 Correct 733 ms 275420 KB Output is correct
67 Correct 704 ms 276300 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 256276 KB Output is correct
2 Correct 122 ms 256316 KB Output is correct
3 Correct 118 ms 256264 KB Output is correct
4 Correct 114 ms 256152 KB Output is correct
5 Correct 122 ms 256324 KB Output is correct
6 Correct 119 ms 256420 KB Output is correct
7 Correct 115 ms 256424 KB Output is correct
8 Correct 121 ms 256440 KB Output is correct
9 Correct 119 ms 256556 KB Output is correct
10 Correct 123 ms 256452 KB Output is correct
11 Correct 125 ms 256324 KB Output is correct
12 Correct 116 ms 256424 KB Output is correct
13 Correct 118 ms 256308 KB Output is correct
14 Correct 118 ms 256288 KB Output is correct
15 Correct 128 ms 256336 KB Output is correct
16 Correct 117 ms 256412 KB Output is correct
17 Correct 116 ms 256320 KB Output is correct
18 Correct 118 ms 256480 KB Output is correct
19 Correct 117 ms 256552 KB Output is correct
20 Correct 119 ms 256332 KB Output is correct
21 Correct 117 ms 256536 KB Output is correct
22 Correct 122 ms 256488 KB Output is correct
23 Correct 118 ms 256460 KB Output is correct
24 Correct 116 ms 256324 KB Output is correct
25 Correct 120 ms 256452 KB Output is correct
26 Correct 122 ms 256364 KB Output is correct
27 Correct 121 ms 256424 KB Output is correct
28 Correct 118 ms 256364 KB Output is correct
29 Correct 116 ms 256408 KB Output is correct
30 Correct 120 ms 256324 KB Output is correct
31 Correct 874 ms 276952 KB Output is correct
32 Correct 306 ms 270812 KB Output is correct
33 Correct 802 ms 275680 KB Output is correct
34 Correct 841 ms 276188 KB Output is correct
35 Correct 855 ms 276712 KB Output is correct
36 Correct 844 ms 277044 KB Output is correct
37 Correct 617 ms 275592 KB Output is correct
38 Correct 569 ms 275396 KB Output is correct
39 Correct 492 ms 275248 KB Output is correct
40 Correct 509 ms 275424 KB Output is correct
41 Correct 720 ms 275264 KB Output is correct
42 Correct 718 ms 275284 KB Output is correct
43 Correct 277 ms 271696 KB Output is correct
44 Correct 723 ms 275420 KB Output is correct
45 Correct 707 ms 275376 KB Output is correct
46 Correct 658 ms 275324 KB Output is correct
47 Correct 399 ms 274256 KB Output is correct
48 Correct 388 ms 274128 KB Output is correct
49 Correct 442 ms 274584 KB Output is correct
50 Correct 473 ms 275160 KB Output is correct
51 Correct 464 ms 274636 KB Output is correct
52 Execution timed out 5059 ms 365280 KB Time limit exceeded
53 Halted 0 ms 0 KB -