oj.uz

Submission #487793

# Submission time Handle Problem Language Result Execution time Memory
487793 2021-11-16T16:29:21 Z leaked New Home (APIO18_new_home) C++14
47 / 100
 5000 ms 401848 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 N=3e5+100;
struct segtree{
    multiset<int> st[4*N];
    void add(int l,int r,int tp,int x,int v,int tl,int tr){
        if(tl>=l&&tr<=r){
            if(tp)
                st[v].insert(x);
            else
                st[v].erase(st[v].find(x));
//            cout<<"ADDT "<<tp<<' '<<tl<<' '<<tr<<' '<<x<<endl;
            return;
        }
        if(tl>r||tr<l) return;
        int tm=(tl+tr)>>1;
        add(l,r,tp,x,2*v,tl,tm);add(l,r,tp,x,2*v+1,tm+1,tr);
    }
    pii get(int id,int v,int tl,int tr){
        pii ans={-1e9,0};
        ans.s+=sz(st[v]);
        if(sz(st[v]))
            umax(ans.f,*st[v].rbegin());
        if(tl==tr){
            return ans;
        }
        int tm=(tl+tr)>>1;
        pii w;
        if(tm>=id)
            w=get(id,2*v,tl,tm);
        else
            w=get(id,2*v+1,tm+1,tr);
        ans.f=max(ans.f,w.f);
        ans.s+=w.s;
        return ans;
    }
}lft,rgt;
vec<int> kek;
int gl(int x){
    return upper_bound(all(kek),x)-kek.begin()-1;
}
int gu(int x){
    return upper_bound(all(kek),x)-kek.begin();
}
void add(int l,int r,int t){
    if(l==r) return;
    int mid=(l+r)>>1;
    if(gl(mid)>=0)
        lft.add(gl(l),gl(mid),t,-l,1,0,sz(kek)-1);
    if(gl(mid)+1<=gl(r))
        rgt.add(gl(mid)+1,gl(r),t,r,1,0,sz(kek)-1);
}
const int Nax=3e5+1;
multiset<int> st[N];
vec<int>here[N];
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]);
//        kek.pb(x[i]);
        arr.pb({a[i],0,i});
        arr.pb({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();
        kek.pb(l[i]);
        arr.pb({y[i],2,i});
    }
    sort(all(kek));kek.erase(unique(all(kek)),kek.end());
    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;
////            cout<<"TYP "<<endl;
////            for(auto &z : st[j])
////                cout<<z<<' ';
////            cout<<endl
            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));
            umax(me.f,omn);me.s++;
        }
        return me;
    };
    auto solve=[&](array<int,3> z){
        pii me={-1e9,0};
        int x=l[z[1]];
        x=gl(x);
        pii fe=lft.get(x,1,0,sz(kek)-1);
        pii si=rgt.get(x,1,0,sz(kek)-1);
//        cout<<fe.f<<' '<<si.f<<endl;
        me.s=fe.s+si.s;
        me.f=max(fe.f+l[z[1]],si.f-l[z[1]]);
        return me;
    };
    vec<int>cnt(k,0);
    for(int i=0;i<k;i++){
        add(-3e8,3e8,1);
        st[i].insert(-3e8);
        st[i].insert(3e8);
    }
    int total=0;
    vec<int>ans(q,-1);
    for(auto &z : arr){
        swap(z[1],z[2]);
        if(z[2]==2){
//            pii og=stupid(z);
//            cout<<"TOTAL "<<total<<' '<<og.s<<endl;
//            assert(total==og.s);
            if(total!=k){
                ans[z[1]]=-1;
                continue;
            }
//            assert(rio.f==og.f);
            pii rio=solve(z);
//            assert(rio.f==og.f);
            ans[z[1]]=rio.f;
//            cerr<<"BRUTE "<<og.f<<' '<<og.s<<endl;
//            cerr<<"SOL "<<rio.f<<' '<<rio.s<<endl;
//            ans[z[1]]=rio.f;
        }
        else if(z[2]==-1){
            int i=z[1];
            auto it=st[t[i]].lower_bound(x[i]);
            add(x[i],*next(it),0);
            add(*prev(it),x[i],0);
            add(*prev(it),*next(it),1);
            st[t[i]].erase(it);
            cnt[t[i]]--;
            if(!cnt[t[i]]) total--;
//            cout<<"DEL "<<t[i]<<' '<<x[i]<<endl;
        }
        else{
            int i=z[1];
            if(!cnt[t[i]]) total++;
            cnt[t[i]]++;
            st[t[i]].insert(x[i]);
//            cout<<"BLY "<<t[i]<<' '<<x[i]<<endl;
            auto it=st[t[i]].lower_bound(x[i]);
            add(*prev(it),*next(it),0);
            add(x[i],*next(it),1);
            add(*prev(it),x[i],1);
        }
    }
    for(auto &z : ans)
        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:101:10: warning: variable 'stupid' set but not used [-Wunused-but-set-variable]
  101 |     auto stupid=[&](array<int,3> z){
      |          ^~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 134084 KB Output is correct
2 Correct 55 ms 134084 KB Output is correct
3 Correct 56 ms 134180 KB Output is correct
4 Correct 56 ms 134120 KB Output is correct
5 Correct 57 ms 134248 KB Output is correct
6 Correct 59 ms 134212 KB Output is correct
7 Correct 59 ms 134364 KB Output is correct
8 Correct 60 ms 134456 KB Output is correct
9 Correct 58 ms 134344 KB Output is correct
10 Correct 61 ms 134340 KB Output is correct
11 Correct 58 ms 134240 KB Output is correct
12 Correct 59 ms 134192 KB Output is correct
13 Correct 57 ms 134244 KB Output is correct
14 Correct 58 ms 134248 KB Output is correct
15 Correct 58 ms 134228 KB Output is correct
16 Correct 59 ms 134268 KB Output is correct
17 Correct 58 ms 134192 KB Output is correct
18 Correct 58 ms 134468 KB Output is correct
19 Correct 58 ms 134276 KB Output is correct
20 Correct 59 ms 134212 KB Output is correct
21 Correct 58 ms 134276 KB Output is correct
22 Correct 57 ms 134340 KB Output is correct
23 Correct 72 ms 134336 KB Output is correct
24 Correct 58 ms 134304 KB Output is correct
25 Correct 60 ms 134320 KB Output is correct
26 Correct 60 ms 134184 KB Output is correct
27 Correct 58 ms 134196 KB Output is correct
28 Correct 58 ms 134212 KB Output is correct
29 Correct 57 ms 134244 KB Output is correct
30 Correct 58 ms 134136 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 134084 KB Output is correct
2 Correct 55 ms 134084 KB Output is correct
3 Correct 56 ms 134180 KB Output is correct
4 Correct 56 ms 134120 KB Output is correct
5 Correct 57 ms 134248 KB Output is correct
6 Correct 59 ms 134212 KB Output is correct
7 Correct 59 ms 134364 KB Output is correct
8 Correct 60 ms 134456 KB Output is correct
9 Correct 58 ms 134344 KB Output is correct
10 Correct 61 ms 134340 KB Output is correct
11 Correct 58 ms 134240 KB Output is correct
12 Correct 59 ms 134192 KB Output is correct
13 Correct 57 ms 134244 KB Output is correct
14 Correct 58 ms 134248 KB Output is correct
15 Correct 58 ms 134228 KB Output is correct
16 Correct 59 ms 134268 KB Output is correct
17 Correct 58 ms 134192 KB Output is correct
18 Correct 58 ms 134468 KB Output is correct
19 Correct 58 ms 134276 KB Output is correct
20 Correct 59 ms 134212 KB Output is correct
21 Correct 58 ms 134276 KB Output is correct
22 Correct 57 ms 134340 KB Output is correct
23 Correct 72 ms 134336 KB Output is correct
24 Correct 58 ms 134304 KB Output is correct
25 Correct 60 ms 134320 KB Output is correct
26 Correct 60 ms 134184 KB Output is correct
27 Correct 58 ms 134196 KB Output is correct
28 Correct 58 ms 134212 KB Output is correct
29 Correct 57 ms 134244 KB Output is correct
30 Correct 58 ms 134136 KB Output is correct
31 Correct 2387 ms 180444 KB Output is correct
32 Correct 185 ms 139800 KB Output is correct
33 Correct 994 ms 146940 KB Output is correct
34 Correct 2285 ms 157276 KB Output is correct
35 Correct 1917 ms 171992 KB Output is correct
36 Correct 1018 ms 154880 KB Output is correct
37 Correct 737 ms 140892 KB Output is correct
38 Correct 537 ms 139832 KB Output is correct
39 Correct 496 ms 139188 KB Output is correct
40 Correct 474 ms 139104 KB Output is correct
41 Correct 854 ms 139648 KB Output is correct
42 Correct 852 ms 139688 KB Output is correct
43 Correct 145 ms 142060 KB Output is correct
44 Correct 830 ms 139664 KB Output is correct
45 Correct 715 ms 139252 KB Output is correct
46 Correct 587 ms 139376 KB Output is correct
47 Correct 368 ms 139168 KB Output is correct
48 Correct 346 ms 139072 KB Output is correct
49 Correct 477 ms 139152 KB Output is correct
50 Correct 635 ms 139256 KB Output is correct
51 Correct 476 ms 139120 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5057 ms 401848 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 5059 ms 324744 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 134084 KB Output is correct
2 Correct 55 ms 134084 KB Output is correct
3 Correct 56 ms 134180 KB Output is correct
4 Correct 56 ms 134120 KB Output is correct
5 Correct 57 ms 134248 KB Output is correct
6 Correct 59 ms 134212 KB Output is correct
7 Correct 59 ms 134364 KB Output is correct
8 Correct 60 ms 134456 KB Output is correct
9 Correct 58 ms 134344 KB Output is correct
10 Correct 61 ms 134340 KB Output is correct
11 Correct 58 ms 134240 KB Output is correct
12 Correct 59 ms 134192 KB Output is correct
13 Correct 57 ms 134244 KB Output is correct
14 Correct 58 ms 134248 KB Output is correct
15 Correct 58 ms 134228 KB Output is correct
16 Correct 59 ms 134268 KB Output is correct
17 Correct 58 ms 134192 KB Output is correct
18 Correct 58 ms 134468 KB Output is correct
19 Correct 58 ms 134276 KB Output is correct
20 Correct 59 ms 134212 KB Output is correct
21 Correct 58 ms 134276 KB Output is correct
22 Correct 57 ms 134340 KB Output is correct
23 Correct 72 ms 134336 KB Output is correct
24 Correct 58 ms 134304 KB Output is correct
25 Correct 60 ms 134320 KB Output is correct
26 Correct 60 ms 134184 KB Output is correct
27 Correct 58 ms 134196 KB Output is correct
28 Correct 58 ms 134212 KB Output is correct
29 Correct 57 ms 134244 KB Output is correct
30 Correct 58 ms 134136 KB Output is correct
31 Correct 2387 ms 180444 KB Output is correct
32 Correct 185 ms 139800 KB Output is correct
33 Correct 994 ms 146940 KB Output is correct
34 Correct 2285 ms 157276 KB Output is correct
35 Correct 1917 ms 171992 KB Output is correct
36 Correct 1018 ms 154880 KB Output is correct
37 Correct 737 ms 140892 KB Output is correct
38 Correct 537 ms 139832 KB Output is correct
39 Correct 496 ms 139188 KB Output is correct
40 Correct 474 ms 139104 KB Output is correct
41 Correct 854 ms 139648 KB Output is correct
42 Correct 852 ms 139688 KB Output is correct
43 Correct 145 ms 142060 KB Output is correct
44 Correct 830 ms 139664 KB Output is correct
45 Correct 715 ms 139252 KB Output is correct
46 Correct 587 ms 139376 KB Output is correct
47 Correct 368 ms 139168 KB Output is correct
48 Correct 346 ms 139072 KB Output is correct
49 Correct 477 ms 139152 KB Output is correct
50 Correct 635 ms 139256 KB Output is correct
51 Correct 476 ms 139120 KB Output is correct
52 Correct 845 ms 193800 KB Output is correct
53 Correct 844 ms 165464 KB Output is correct
54 Correct 2151 ms 202192 KB Output is correct
55 Correct 946 ms 157780 KB Output is correct
56 Correct 915 ms 167060 KB Output is correct
57 Correct 928 ms 145260 KB Output is correct
58 Correct 1049 ms 157984 KB Output is correct
59 Correct 1014 ms 166896 KB Output is correct
60 Correct 1016 ms 145260 KB Output is correct
61 Correct 195 ms 154992 KB Output is correct
62 Correct 865 ms 193856 KB Output is correct
63 Correct 1638 ms 189956 KB Output is correct
64 Correct 1954 ms 180796 KB Output is correct
65 Correct 2009 ms 152996 KB Output is correct
66 Correct 978 ms 140384 KB Output is correct
67 Correct 520 ms 143412 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 134084 KB Output is correct
2 Correct 55 ms 134084 KB Output is correct
3 Correct 56 ms 134180 KB Output is correct
4 Correct 56 ms 134120 KB Output is correct
5 Correct 57 ms 134248 KB Output is correct
6 Correct 59 ms 134212 KB Output is correct
7 Correct 59 ms 134364 KB Output is correct
8 Correct 60 ms 134456 KB Output is correct
9 Correct 58 ms 134344 KB Output is correct
10 Correct 61 ms 134340 KB Output is correct
11 Correct 58 ms 134240 KB Output is correct
12 Correct 59 ms 134192 KB Output is correct
13 Correct 57 ms 134244 KB Output is correct
14 Correct 58 ms 134248 KB Output is correct
15 Correct 58 ms 134228 KB Output is correct
16 Correct 59 ms 134268 KB Output is correct
17 Correct 58 ms 134192 KB Output is correct
18 Correct 58 ms 134468 KB Output is correct
19 Correct 58 ms 134276 KB Output is correct
20 Correct 59 ms 134212 KB Output is correct
21 Correct 58 ms 134276 KB Output is correct
22 Correct 57 ms 134340 KB Output is correct
23 Correct 72 ms 134336 KB Output is correct
24 Correct 58 ms 134304 KB Output is correct
25 Correct 60 ms 134320 KB Output is correct
26 Correct 60 ms 134184 KB Output is correct
27 Correct 58 ms 134196 KB Output is correct
28 Correct 58 ms 134212 KB Output is correct
29 Correct 57 ms 134244 KB Output is correct
30 Correct 58 ms 134136 KB Output is correct
31 Correct 2387 ms 180444 KB Output is correct
32 Correct 185 ms 139800 KB Output is correct
33 Correct 994 ms 146940 KB Output is correct
34 Correct 2285 ms 157276 KB Output is correct
35 Correct 1917 ms 171992 KB Output is correct
36 Correct 1018 ms 154880 KB Output is correct
37 Correct 737 ms 140892 KB Output is correct
38 Correct 537 ms 139832 KB Output is correct
39 Correct 496 ms 139188 KB Output is correct
40 Correct 474 ms 139104 KB Output is correct
41 Correct 854 ms 139648 KB Output is correct
42 Correct 852 ms 139688 KB Output is correct
43 Correct 145 ms 142060 KB Output is correct
44 Correct 830 ms 139664 KB Output is correct
45 Correct 715 ms 139252 KB Output is correct
46 Correct 587 ms 139376 KB Output is correct
47 Correct 368 ms 139168 KB Output is correct
48 Correct 346 ms 139072 KB Output is correct
49 Correct 477 ms 139152 KB Output is correct
50 Correct 635 ms 139256 KB Output is correct
51 Correct 476 ms 139120 KB Output is correct
52 Execution timed out 5057 ms 401848 KB Time limit exceeded
53 Halted 0 ms 0 KB -