oj.uz

Submission #487797

# Submission time Handle Problem Language Result Execution time Memory
487797 2021-11-16T16:36:11 Z leaked New Home (APIO18_new_home) C++14
47 / 100
 5000 ms 394668 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));
            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);
    }
    int get(int id,int v,int tl,int tr){
        int ans=-1e9;
        if(sz(st[v])) ans=*st[v].rbegin();
        if(tl==tr){
            return ans;
        }
        int tm=(tl+tr)>>1;
        if(tm>=id)
            return max(ans,get(id,2*v,tl,tm));
        else
            return max(ans,get(id,2*v+1,tm+1,tr));
    }
}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){
        int x=l[z[1]];
        x=gl(x);
        int fe=lft.get(x,1,0,sz(kek)-1)+l[z[1]];
        int si=rgt.get(x,1,0,sz(kek)-1)-l[z[1]];
        return max(fe,si);
    };
    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){
            if(total!=k){
                ans[z[1]]=-1;
                continue;
            }
            int rio=solve(z);
            ans[z[1]]=rio;
        }
        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--;
        }
        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);
            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:94:10: warning: variable 'stupid' set but not used [-Wunused-but-set-variable]
   94 |     auto stupid=[&](array<int,3> z){
      |          ^~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 134180 KB Output is correct
2 Correct 60 ms 134212 KB Output is correct
3 Correct 62 ms 134108 KB Output is correct
4 Correct 62 ms 134112 KB Output is correct
5 Correct 70 ms 134212 KB Output is correct
6 Correct 63 ms 134256 KB Output is correct
7 Correct 57 ms 134288 KB Output is correct
8 Correct 58 ms 134436 KB Output is correct
9 Correct 57 ms 134384 KB Output is correct
10 Correct 60 ms 134472 KB Output is correct
11 Correct 64 ms 134148 KB Output is correct
12 Correct 60 ms 134144 KB Output is correct
13 Correct 57 ms 134224 KB Output is correct
14 Correct 57 ms 134228 KB Output is correct
15 Correct 59 ms 134280 KB Output is correct
16 Correct 60 ms 134376 KB Output is correct
17 Correct 60 ms 134168 KB Output is correct
18 Correct 69 ms 134316 KB Output is correct
19 Correct 62 ms 134368 KB Output is correct
20 Correct 59 ms 134196 KB Output is correct
21 Correct 59 ms 134312 KB Output is correct
22 Correct 58 ms 134456 KB Output is correct
23 Correct 64 ms 134324 KB Output is correct
24 Correct 60 ms 134380 KB Output is correct
25 Correct 63 ms 134196 KB Output is correct
26 Correct 67 ms 134240 KB Output is correct
27 Correct 59 ms 134228 KB Output is correct
28 Correct 59 ms 134132 KB Output is correct
29 Correct 57 ms 134132 KB Output is correct
30 Correct 59 ms 134180 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 134180 KB Output is correct
2 Correct 60 ms 134212 KB Output is correct
3 Correct 62 ms 134108 KB Output is correct
4 Correct 62 ms 134112 KB Output is correct
5 Correct 70 ms 134212 KB Output is correct
6 Correct 63 ms 134256 KB Output is correct
7 Correct 57 ms 134288 KB Output is correct
8 Correct 58 ms 134436 KB Output is correct
9 Correct 57 ms 134384 KB Output is correct
10 Correct 60 ms 134472 KB Output is correct
11 Correct 64 ms 134148 KB Output is correct
12 Correct 60 ms 134144 KB Output is correct
13 Correct 57 ms 134224 KB Output is correct
14 Correct 57 ms 134228 KB Output is correct
15 Correct 59 ms 134280 KB Output is correct
16 Correct 60 ms 134376 KB Output is correct
17 Correct 60 ms 134168 KB Output is correct
18 Correct 69 ms 134316 KB Output is correct
19 Correct 62 ms 134368 KB Output is correct
20 Correct 59 ms 134196 KB Output is correct
21 Correct 59 ms 134312 KB Output is correct
22 Correct 58 ms 134456 KB Output is correct
23 Correct 64 ms 134324 KB Output is correct
24 Correct 60 ms 134380 KB Output is correct
25 Correct 63 ms 134196 KB Output is correct
26 Correct 67 ms 134240 KB Output is correct
27 Correct 59 ms 134228 KB Output is correct
28 Correct 59 ms 134132 KB Output is correct
29 Correct 57 ms 134132 KB Output is correct
30 Correct 59 ms 134180 KB Output is correct
31 Correct 2495 ms 180444 KB Output is correct
32 Correct 186 ms 139740 KB Output is correct
33 Correct 1061 ms 146800 KB Output is correct
34 Correct 2478 ms 157144 KB Output is correct
35 Correct 2050 ms 171708 KB Output is correct
36 Correct 1085 ms 154852 KB Output is correct
37 Correct 823 ms 140888 KB Output is correct
38 Correct 581 ms 139864 KB Output is correct
39 Correct 510 ms 139104 KB Output is correct
40 Correct 487 ms 139056 KB Output is correct
41 Correct 903 ms 139540 KB Output is correct
42 Correct 924 ms 139600 KB Output is correct
43 Correct 130 ms 142076 KB Output is correct
44 Correct 886 ms 139496 KB Output is correct
45 Correct 743 ms 139232 KB Output is correct
46 Correct 639 ms 139288 KB Output is correct
47 Correct 372 ms 139088 KB Output is correct
48 Correct 351 ms 139132 KB Output is correct
49 Correct 477 ms 139072 KB Output is correct
50 Correct 687 ms 139268 KB Output is correct
51 Correct 479 ms 139120 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5116 ms 394668 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 5106 ms 318944 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 134180 KB Output is correct
2 Correct 60 ms 134212 KB Output is correct
3 Correct 62 ms 134108 KB Output is correct
4 Correct 62 ms 134112 KB Output is correct
5 Correct 70 ms 134212 KB Output is correct
6 Correct 63 ms 134256 KB Output is correct
7 Correct 57 ms 134288 KB Output is correct
8 Correct 58 ms 134436 KB Output is correct
9 Correct 57 ms 134384 KB Output is correct
10 Correct 60 ms 134472 KB Output is correct
11 Correct 64 ms 134148 KB Output is correct
12 Correct 60 ms 134144 KB Output is correct
13 Correct 57 ms 134224 KB Output is correct
14 Correct 57 ms 134228 KB Output is correct
15 Correct 59 ms 134280 KB Output is correct
16 Correct 60 ms 134376 KB Output is correct
17 Correct 60 ms 134168 KB Output is correct
18 Correct 69 ms 134316 KB Output is correct
19 Correct 62 ms 134368 KB Output is correct
20 Correct 59 ms 134196 KB Output is correct
21 Correct 59 ms 134312 KB Output is correct
22 Correct 58 ms 134456 KB Output is correct
23 Correct 64 ms 134324 KB Output is correct
24 Correct 60 ms 134380 KB Output is correct
25 Correct 63 ms 134196 KB Output is correct
26 Correct 67 ms 134240 KB Output is correct
27 Correct 59 ms 134228 KB Output is correct
28 Correct 59 ms 134132 KB Output is correct
29 Correct 57 ms 134132 KB Output is correct
30 Correct 59 ms 134180 KB Output is correct
31 Correct 2495 ms 180444 KB Output is correct
32 Correct 186 ms 139740 KB Output is correct
33 Correct 1061 ms 146800 KB Output is correct
34 Correct 2478 ms 157144 KB Output is correct
35 Correct 2050 ms 171708 KB Output is correct
36 Correct 1085 ms 154852 KB Output is correct
37 Correct 823 ms 140888 KB Output is correct
38 Correct 581 ms 139864 KB Output is correct
39 Correct 510 ms 139104 KB Output is correct
40 Correct 487 ms 139056 KB Output is correct
41 Correct 903 ms 139540 KB Output is correct
42 Correct 924 ms 139600 KB Output is correct
43 Correct 130 ms 142076 KB Output is correct
44 Correct 886 ms 139496 KB Output is correct
45 Correct 743 ms 139232 KB Output is correct
46 Correct 639 ms 139288 KB Output is correct
47 Correct 372 ms 139088 KB Output is correct
48 Correct 351 ms 139132 KB Output is correct
49 Correct 477 ms 139072 KB Output is correct
50 Correct 687 ms 139268 KB Output is correct
51 Correct 479 ms 139120 KB Output is correct
52 Correct 895 ms 193748 KB Output is correct
53 Correct 885 ms 165544 KB Output is correct
54 Correct 2231 ms 202104 KB Output is correct
55 Correct 1048 ms 157868 KB Output is correct
56 Correct 992 ms 166976 KB Output is correct
57 Correct 999 ms 145012 KB Output is correct
58 Correct 1205 ms 157984 KB Output is correct
59 Correct 1092 ms 167028 KB Output is correct
60 Correct 1053 ms 145220 KB Output is correct
61 Correct 198 ms 154944 KB Output is correct
62 Correct 885 ms 193860 KB Output is correct
63 Correct 1683 ms 189904 KB Output is correct
64 Correct 2021 ms 180732 KB Output is correct
65 Correct 2175 ms 153060 KB Output is correct
66 Correct 970 ms 140380 KB Output is correct
67 Correct 524 ms 143388 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 134180 KB Output is correct
2 Correct 60 ms 134212 KB Output is correct
3 Correct 62 ms 134108 KB Output is correct
4 Correct 62 ms 134112 KB Output is correct
5 Correct 70 ms 134212 KB Output is correct
6 Correct 63 ms 134256 KB Output is correct
7 Correct 57 ms 134288 KB Output is correct
8 Correct 58 ms 134436 KB Output is correct
9 Correct 57 ms 134384 KB Output is correct
10 Correct 60 ms 134472 KB Output is correct
11 Correct 64 ms 134148 KB Output is correct
12 Correct 60 ms 134144 KB Output is correct
13 Correct 57 ms 134224 KB Output is correct
14 Correct 57 ms 134228 KB Output is correct
15 Correct 59 ms 134280 KB Output is correct
16 Correct 60 ms 134376 KB Output is correct
17 Correct 60 ms 134168 KB Output is correct
18 Correct 69 ms 134316 KB Output is correct
19 Correct 62 ms 134368 KB Output is correct
20 Correct 59 ms 134196 KB Output is correct
21 Correct 59 ms 134312 KB Output is correct
22 Correct 58 ms 134456 KB Output is correct
23 Correct 64 ms 134324 KB Output is correct
24 Correct 60 ms 134380 KB Output is correct
25 Correct 63 ms 134196 KB Output is correct
26 Correct 67 ms 134240 KB Output is correct
27 Correct 59 ms 134228 KB Output is correct
28 Correct 59 ms 134132 KB Output is correct
29 Correct 57 ms 134132 KB Output is correct
30 Correct 59 ms 134180 KB Output is correct
31 Correct 2495 ms 180444 KB Output is correct
32 Correct 186 ms 139740 KB Output is correct
33 Correct 1061 ms 146800 KB Output is correct
34 Correct 2478 ms 157144 KB Output is correct
35 Correct 2050 ms 171708 KB Output is correct
36 Correct 1085 ms 154852 KB Output is correct
37 Correct 823 ms 140888 KB Output is correct
38 Correct 581 ms 139864 KB Output is correct
39 Correct 510 ms 139104 KB Output is correct
40 Correct 487 ms 139056 KB Output is correct
41 Correct 903 ms 139540 KB Output is correct
42 Correct 924 ms 139600 KB Output is correct
43 Correct 130 ms 142076 KB Output is correct
44 Correct 886 ms 139496 KB Output is correct
45 Correct 743 ms 139232 KB Output is correct
46 Correct 639 ms 139288 KB Output is correct
47 Correct 372 ms 139088 KB Output is correct
48 Correct 351 ms 139132 KB Output is correct
49 Correct 477 ms 139072 KB Output is correct
50 Correct 687 ms 139268 KB Output is correct
51 Correct 479 ms 139120 KB Output is correct
52 Execution timed out 5116 ms 394668 KB Time limit exceeded
53 Halted 0 ms 0 KB -