oj.uz

Submission #491586

# Submission time Handle Problem Language Result Execution time Memory
491586 2021-12-03T12:11:16 Z leaked New Home (APIO18_new_home) C++14
47 / 100
 5000 ms 131496 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=9e5+100;
bool del[5*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;
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);
    for(auto &z : arr){
        swap(z[1],z[2]);
        if(z[2]==2){
            bad[z[1]]=(total==k?0:1);
            continue;
        }
        if(z[2]==-1){
            int i=z[1];
            auto it=st[t[i]].lower_bound(x[i]);
            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]);
        }
//        cout<<z[0]<<' '<<total<<endl;
    }
//    cout<<endl;
    ///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(total!=k)
                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;
        }
        if(z[2]==-1){
            int i=z[1];
            auto it=st[t[i]].lower_bound(x[i]);
            add(x[i],*next(it),0,t[i],1);
            add(*prev(it),x[i],0,t[i],1);
            add(*prev(it),*next(it),1,t[i],1);
            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],1);
            add(x[i],*next(it),1,t[i],1);
            add(*prev(it),x[i],1,t[i],1);
        }
//        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:128:10: warning: variable 'stupid' set but not used [-Wunused-but-set-variable]
  128 |     auto stupid=[&](array<int,3> z){
      |          ^~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 49612 KB Output is correct
2 Correct 26 ms 49576 KB Output is correct
3 Correct 21 ms 49612 KB Output is correct
4 Correct 21 ms 49536 KB Output is correct
5 Correct 22 ms 49664 KB Output is correct
6 Correct 23 ms 49688 KB Output is correct
7 Correct 23 ms 49776 KB Output is correct
8 Correct 22 ms 49740 KB Output is correct
9 Correct 23 ms 49812 KB Output is correct
10 Correct 24 ms 49768 KB Output is correct
11 Correct 23 ms 49716 KB Output is correct
12 Correct 24 ms 49648 KB Output is correct
13 Correct 24 ms 49644 KB Output is correct
14 Correct 25 ms 49684 KB Output is correct
15 Correct 23 ms 49776 KB Output is correct
16 Correct 23 ms 49760 KB Output is correct
17 Correct 29 ms 49676 KB Output is correct
18 Correct 23 ms 49776 KB Output is correct
19 Correct 24 ms 49740 KB Output is correct
20 Correct 23 ms 49800 KB Output is correct
21 Correct 26 ms 49800 KB Output is correct
22 Correct 22 ms 49740 KB Output is correct
23 Correct 25 ms 49760 KB Output is correct
24 Correct 23 ms 49744 KB Output is correct
25 Correct 23 ms 49732 KB Output is correct
26 Correct 25 ms 49728 KB Output is correct
27 Correct 24 ms 49616 KB Output is correct
28 Correct 23 ms 49652 KB Output is correct
29 Correct 24 ms 49700 KB Output is correct
30 Correct 25 ms 49760 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 49612 KB Output is correct
2 Correct 26 ms 49576 KB Output is correct
3 Correct 21 ms 49612 KB Output is correct
4 Correct 21 ms 49536 KB Output is correct
5 Correct 22 ms 49664 KB Output is correct
6 Correct 23 ms 49688 KB Output is correct
7 Correct 23 ms 49776 KB Output is correct
8 Correct 22 ms 49740 KB Output is correct
9 Correct 23 ms 49812 KB Output is correct
10 Correct 24 ms 49768 KB Output is correct
11 Correct 23 ms 49716 KB Output is correct
12 Correct 24 ms 49648 KB Output is correct
13 Correct 24 ms 49644 KB Output is correct
14 Correct 25 ms 49684 KB Output is correct
15 Correct 23 ms 49776 KB Output is correct
16 Correct 23 ms 49760 KB Output is correct
17 Correct 29 ms 49676 KB Output is correct
18 Correct 23 ms 49776 KB Output is correct
19 Correct 24 ms 49740 KB Output is correct
20 Correct 23 ms 49800 KB Output is correct
21 Correct 26 ms 49800 KB Output is correct
22 Correct 22 ms 49740 KB Output is correct
23 Correct 25 ms 49760 KB Output is correct
24 Correct 23 ms 49744 KB Output is correct
25 Correct 23 ms 49732 KB Output is correct
26 Correct 25 ms 49728 KB Output is correct
27 Correct 24 ms 49616 KB Output is correct
28 Correct 23 ms 49652 KB Output is correct
29 Correct 24 ms 49700 KB Output is correct
30 Correct 25 ms 49760 KB Output is correct
31 Correct 862 ms 66488 KB Output is correct
32 Correct 212 ms 58528 KB Output is correct
33 Correct 735 ms 63748 KB Output is correct
34 Correct 709 ms 63932 KB Output is correct
35 Correct 768 ms 66160 KB Output is correct
36 Correct 726 ms 66080 KB Output is correct
37 Correct 513 ms 62472 KB Output is correct
38 Correct 521 ms 62484 KB Output is correct
39 Correct 400 ms 62160 KB Output is correct
40 Correct 415 ms 62136 KB Output is correct
41 Correct 586 ms 62304 KB Output is correct
42 Correct 573 ms 62244 KB Output is correct
43 Correct 171 ms 60524 KB Output is correct
44 Correct 585 ms 62396 KB Output is correct
45 Correct 570 ms 62400 KB Output is correct
46 Correct 522 ms 62240 KB Output is correct
47 Correct 294 ms 61764 KB Output is correct
48 Correct 288 ms 61792 KB Output is correct
49 Correct 377 ms 62004 KB Output is correct
50 Correct 364 ms 62144 KB Output is correct
51 Correct 367 ms 62052 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5056 ms 131496 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 5060 ms 122660 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 49612 KB Output is correct
2 Correct 26 ms 49576 KB Output is correct
3 Correct 21 ms 49612 KB Output is correct
4 Correct 21 ms 49536 KB Output is correct
5 Correct 22 ms 49664 KB Output is correct
6 Correct 23 ms 49688 KB Output is correct
7 Correct 23 ms 49776 KB Output is correct
8 Correct 22 ms 49740 KB Output is correct
9 Correct 23 ms 49812 KB Output is correct
10 Correct 24 ms 49768 KB Output is correct
11 Correct 23 ms 49716 KB Output is correct
12 Correct 24 ms 49648 KB Output is correct
13 Correct 24 ms 49644 KB Output is correct
14 Correct 25 ms 49684 KB Output is correct
15 Correct 23 ms 49776 KB Output is correct
16 Correct 23 ms 49760 KB Output is correct
17 Correct 29 ms 49676 KB Output is correct
18 Correct 23 ms 49776 KB Output is correct
19 Correct 24 ms 49740 KB Output is correct
20 Correct 23 ms 49800 KB Output is correct
21 Correct 26 ms 49800 KB Output is correct
22 Correct 22 ms 49740 KB Output is correct
23 Correct 25 ms 49760 KB Output is correct
24 Correct 23 ms 49744 KB Output is correct
25 Correct 23 ms 49732 KB Output is correct
26 Correct 25 ms 49728 KB Output is correct
27 Correct 24 ms 49616 KB Output is correct
28 Correct 23 ms 49652 KB Output is correct
29 Correct 24 ms 49700 KB Output is correct
30 Correct 25 ms 49760 KB Output is correct
31 Correct 862 ms 66488 KB Output is correct
32 Correct 212 ms 58528 KB Output is correct
33 Correct 735 ms 63748 KB Output is correct
34 Correct 709 ms 63932 KB Output is correct
35 Correct 768 ms 66160 KB Output is correct
36 Correct 726 ms 66080 KB Output is correct
37 Correct 513 ms 62472 KB Output is correct
38 Correct 521 ms 62484 KB Output is correct
39 Correct 400 ms 62160 KB Output is correct
40 Correct 415 ms 62136 KB Output is correct
41 Correct 586 ms 62304 KB Output is correct
42 Correct 573 ms 62244 KB Output is correct
43 Correct 171 ms 60524 KB Output is correct
44 Correct 585 ms 62396 KB Output is correct
45 Correct 570 ms 62400 KB Output is correct
46 Correct 522 ms 62240 KB Output is correct
47 Correct 294 ms 61764 KB Output is correct
48 Correct 288 ms 61792 KB Output is correct
49 Correct 377 ms 62004 KB Output is correct
50 Correct 364 ms 62144 KB Output is correct
51 Correct 367 ms 62052 KB Output is correct
52 Correct 879 ms 75752 KB Output is correct
53 Correct 867 ms 74264 KB Output is correct
54 Correct 758 ms 69120 KB Output is correct
55 Correct 653 ms 66932 KB Output is correct
56 Correct 729 ms 69492 KB Output is correct
57 Correct 633 ms 63672 KB Output is correct
58 Correct 684 ms 67032 KB Output is correct
59 Correct 712 ms 69364 KB Output is correct
60 Correct 659 ms 63460 KB Output is correct
61 Correct 324 ms 76040 KB Output is correct
62 Correct 887 ms 75928 KB Output is correct
63 Correct 775 ms 70412 KB Output is correct
64 Correct 838 ms 67900 KB Output is correct
65 Correct 727 ms 64000 KB Output is correct
66 Correct 652 ms 62208 KB Output is correct
67 Correct 605 ms 63312 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 49612 KB Output is correct
2 Correct 26 ms 49576 KB Output is correct
3 Correct 21 ms 49612 KB Output is correct
4 Correct 21 ms 49536 KB Output is correct
5 Correct 22 ms 49664 KB Output is correct
6 Correct 23 ms 49688 KB Output is correct
7 Correct 23 ms 49776 KB Output is correct
8 Correct 22 ms 49740 KB Output is correct
9 Correct 23 ms 49812 KB Output is correct
10 Correct 24 ms 49768 KB Output is correct
11 Correct 23 ms 49716 KB Output is correct
12 Correct 24 ms 49648 KB Output is correct
13 Correct 24 ms 49644 KB Output is correct
14 Correct 25 ms 49684 KB Output is correct
15 Correct 23 ms 49776 KB Output is correct
16 Correct 23 ms 49760 KB Output is correct
17 Correct 29 ms 49676 KB Output is correct
18 Correct 23 ms 49776 KB Output is correct
19 Correct 24 ms 49740 KB Output is correct
20 Correct 23 ms 49800 KB Output is correct
21 Correct 26 ms 49800 KB Output is correct
22 Correct 22 ms 49740 KB Output is correct
23 Correct 25 ms 49760 KB Output is correct
24 Correct 23 ms 49744 KB Output is correct
25 Correct 23 ms 49732 KB Output is correct
26 Correct 25 ms 49728 KB Output is correct
27 Correct 24 ms 49616 KB Output is correct
28 Correct 23 ms 49652 KB Output is correct
29 Correct 24 ms 49700 KB Output is correct
30 Correct 25 ms 49760 KB Output is correct
31 Correct 862 ms 66488 KB Output is correct
32 Correct 212 ms 58528 KB Output is correct
33 Correct 735 ms 63748 KB Output is correct
34 Correct 709 ms 63932 KB Output is correct
35 Correct 768 ms 66160 KB Output is correct
36 Correct 726 ms 66080 KB Output is correct
37 Correct 513 ms 62472 KB Output is correct
38 Correct 521 ms 62484 KB Output is correct
39 Correct 400 ms 62160 KB Output is correct
40 Correct 415 ms 62136 KB Output is correct
41 Correct 586 ms 62304 KB Output is correct
42 Correct 573 ms 62244 KB Output is correct
43 Correct 171 ms 60524 KB Output is correct
44 Correct 585 ms 62396 KB Output is correct
45 Correct 570 ms 62400 KB Output is correct
46 Correct 522 ms 62240 KB Output is correct
47 Correct 294 ms 61764 KB Output is correct
48 Correct 288 ms 61792 KB Output is correct
49 Correct 377 ms 62004 KB Output is correct
50 Correct 364 ms 62144 KB Output is correct
51 Correct 367 ms 62052 KB Output is correct
52 Execution timed out 5056 ms 131496 KB Time limit exceeded
53 Halted 0 ms 0 KB -