oj.uz

Submission #487810

# Submission time Handle Problem Language Result Execution time Memory
487810 2021-11-16T17:37:04 Z leaked New Home (APIO18_new_home) C++14
47 / 100
 5000 ms 353284 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;
bool del[5*N];
struct segtree{
    priority_queue<pii> st[2*N+1];
    void add(int l,int r,int tp,pii x,int v,int tl,int tr){
        l+=N,r+=N;
        r++;
        while(l<r) {
            if (l&1) st[l++].push(x);
            if (r&1) st[--r].push(x);
            l>>=1;r>>=1;
        }
    }
    int get(int id){
        int ans=-1e9;
        id+=N;
        while(id>0){
            while(sz(st[id]) && del[st[id].top().s]) st[id].pop();
            if(sz(st[id])) umax(ans,st[id].top().f);
            id>>=1;
        }
        return ans;
    }
}lft,rgt;
vec<int> kek;
map<pii,int>mp;
int tmr;
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,int tp){
    if(l==r) return;
    int mid=(l+r)>>1;
    if(!t){
        del[mp[{l,tp}]]=1;
        return;
    }
    mp[{l,tp}]=tmr;
    if(gl(mid)>=0){
        lft.add(gl(l),gl(mid),t,{-l,tmr},1,0,sz(kek)-1);
    }
    if(gl(mid)+1<=gl(r))
        rgt.add(gl(mid)+1,gl(r),t,{r,tmr},1,0,sz(kek)-1);
    ++tmr;
}
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)+l[z[1]];
        int si=rgt.get(x)-l[z[1]];
        return max(fe,si);
    };
    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<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,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]);
        }
    }
    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:99:10: warning: variable 'stupid' set but not used [-Wunused-but-set-variable]
   99 |     auto stupid=[&](array<int,3> z){
      |          ^~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 58956 KB Output is correct
2 Correct 29 ms 59040 KB Output is correct
3 Correct 26 ms 58936 KB Output is correct
4 Correct 27 ms 58912 KB Output is correct
5 Correct 30 ms 59028 KB Output is correct
6 Correct 29 ms 59104 KB Output is correct
7 Correct 28 ms 59340 KB Output is correct
8 Correct 28 ms 59212 KB Output is correct
9 Correct 28 ms 59348 KB Output is correct
10 Correct 29 ms 59188 KB Output is correct
11 Correct 32 ms 59188 KB Output is correct
12 Correct 32 ms 59156 KB Output is correct
13 Correct 28 ms 59208 KB Output is correct
14 Correct 30 ms 59128 KB Output is correct
15 Correct 30 ms 59212 KB Output is correct
16 Correct 29 ms 59172 KB Output is correct
17 Correct 30 ms 59200 KB Output is correct
18 Correct 28 ms 59216 KB Output is correct
19 Correct 29 ms 59204 KB Output is correct
20 Correct 30 ms 59136 KB Output is correct
21 Correct 29 ms 59104 KB Output is correct
22 Correct 29 ms 59296 KB Output is correct
23 Correct 29 ms 59264 KB Output is correct
24 Correct 31 ms 59224 KB Output is correct
25 Correct 29 ms 59116 KB Output is correct
26 Correct 28 ms 59200 KB Output is correct
27 Correct 29 ms 59096 KB Output is correct
28 Correct 31 ms 59144 KB Output is correct
29 Correct 28 ms 59084 KB Output is correct
30 Correct 30 ms 59076 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 58956 KB Output is correct
2 Correct 29 ms 59040 KB Output is correct
3 Correct 26 ms 58936 KB Output is correct
4 Correct 27 ms 58912 KB Output is correct
5 Correct 30 ms 59028 KB Output is correct
6 Correct 29 ms 59104 KB Output is correct
7 Correct 28 ms 59340 KB Output is correct
8 Correct 28 ms 59212 KB Output is correct
9 Correct 28 ms 59348 KB Output is correct
10 Correct 29 ms 59188 KB Output is correct
11 Correct 32 ms 59188 KB Output is correct
12 Correct 32 ms 59156 KB Output is correct
13 Correct 28 ms 59208 KB Output is correct
14 Correct 30 ms 59128 KB Output is correct
15 Correct 30 ms 59212 KB Output is correct
16 Correct 29 ms 59172 KB Output is correct
17 Correct 30 ms 59200 KB Output is correct
18 Correct 28 ms 59216 KB Output is correct
19 Correct 29 ms 59204 KB Output is correct
20 Correct 30 ms 59136 KB Output is correct
21 Correct 29 ms 59104 KB Output is correct
22 Correct 29 ms 59296 KB Output is correct
23 Correct 29 ms 59264 KB Output is correct
24 Correct 31 ms 59224 KB Output is correct
25 Correct 29 ms 59116 KB Output is correct
26 Correct 28 ms 59200 KB Output is correct
27 Correct 29 ms 59096 KB Output is correct
28 Correct 31 ms 59144 KB Output is correct
29 Correct 28 ms 59084 KB Output is correct
30 Correct 30 ms 59076 KB Output is correct
31 Correct 987 ms 102244 KB Output is correct
32 Correct 140 ms 66700 KB Output is correct
33 Correct 726 ms 84524 KB Output is correct
34 Correct 933 ms 102116 KB Output is correct
35 Correct 897 ms 96492 KB Output is correct
36 Correct 708 ms 84836 KB Output is correct
37 Correct 500 ms 86212 KB Output is correct
38 Correct 419 ms 79644 KB Output is correct
39 Correct 371 ms 81372 KB Output is correct
40 Correct 355 ms 79648 KB Output is correct
41 Correct 710 ms 88368 KB Output is correct
42 Correct 675 ms 94136 KB Output is correct
43 Correct 104 ms 68464 KB Output is correct
44 Correct 706 ms 87804 KB Output is correct
45 Correct 689 ms 84308 KB Output is correct
46 Correct 663 ms 80724 KB Output is correct
47 Correct 324 ms 88536 KB Output is correct
48 Correct 324 ms 86840 KB Output is correct
49 Correct 389 ms 89336 KB Output is correct
50 Correct 428 ms 94744 KB Output is correct
51 Correct 410 ms 87248 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5074 ms 353284 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 5076 ms 315492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 58956 KB Output is correct
2 Correct 29 ms 59040 KB Output is correct
3 Correct 26 ms 58936 KB Output is correct
4 Correct 27 ms 58912 KB Output is correct
5 Correct 30 ms 59028 KB Output is correct
6 Correct 29 ms 59104 KB Output is correct
7 Correct 28 ms 59340 KB Output is correct
8 Correct 28 ms 59212 KB Output is correct
9 Correct 28 ms 59348 KB Output is correct
10 Correct 29 ms 59188 KB Output is correct
11 Correct 32 ms 59188 KB Output is correct
12 Correct 32 ms 59156 KB Output is correct
13 Correct 28 ms 59208 KB Output is correct
14 Correct 30 ms 59128 KB Output is correct
15 Correct 30 ms 59212 KB Output is correct
16 Correct 29 ms 59172 KB Output is correct
17 Correct 30 ms 59200 KB Output is correct
18 Correct 28 ms 59216 KB Output is correct
19 Correct 29 ms 59204 KB Output is correct
20 Correct 30 ms 59136 KB Output is correct
21 Correct 29 ms 59104 KB Output is correct
22 Correct 29 ms 59296 KB Output is correct
23 Correct 29 ms 59264 KB Output is correct
24 Correct 31 ms 59224 KB Output is correct
25 Correct 29 ms 59116 KB Output is correct
26 Correct 28 ms 59200 KB Output is correct
27 Correct 29 ms 59096 KB Output is correct
28 Correct 31 ms 59144 KB Output is correct
29 Correct 28 ms 59084 KB Output is correct
30 Correct 30 ms 59076 KB Output is correct
31 Correct 987 ms 102244 KB Output is correct
32 Correct 140 ms 66700 KB Output is correct
33 Correct 726 ms 84524 KB Output is correct
34 Correct 933 ms 102116 KB Output is correct
35 Correct 897 ms 96492 KB Output is correct
36 Correct 708 ms 84836 KB Output is correct
37 Correct 500 ms 86212 KB Output is correct
38 Correct 419 ms 79644 KB Output is correct
39 Correct 371 ms 81372 KB Output is correct
40 Correct 355 ms 79648 KB Output is correct
41 Correct 710 ms 88368 KB Output is correct
42 Correct 675 ms 94136 KB Output is correct
43 Correct 104 ms 68464 KB Output is correct
44 Correct 706 ms 87804 KB Output is correct
45 Correct 689 ms 84308 KB Output is correct
46 Correct 663 ms 80724 KB Output is correct
47 Correct 324 ms 88536 KB Output is correct
48 Correct 324 ms 86840 KB Output is correct
49 Correct 389 ms 89336 KB Output is correct
50 Correct 428 ms 94744 KB Output is correct
51 Correct 410 ms 87248 KB Output is correct
52 Correct 626 ms 125464 KB Output is correct
53 Correct 644 ms 121464 KB Output is correct
54 Correct 724 ms 114308 KB Output is correct
55 Correct 705 ms 102184 KB Output is correct
56 Correct 697 ms 104212 KB Output is correct
57 Correct 705 ms 93720 KB Output is correct
58 Correct 680 ms 101232 KB Output is correct
59 Correct 690 ms 105572 KB Output is correct
60 Correct 700 ms 96244 KB Output is correct
61 Correct 165 ms 83232 KB Output is correct
62 Correct 716 ms 112148 KB Output is correct
63 Correct 704 ms 110516 KB Output is correct
64 Correct 713 ms 108140 KB Output is correct
65 Correct 750 ms 103308 KB Output is correct
66 Correct 740 ms 91848 KB Output is correct
67 Correct 254 ms 77428 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 58956 KB Output is correct
2 Correct 29 ms 59040 KB Output is correct
3 Correct 26 ms 58936 KB Output is correct
4 Correct 27 ms 58912 KB Output is correct
5 Correct 30 ms 59028 KB Output is correct
6 Correct 29 ms 59104 KB Output is correct
7 Correct 28 ms 59340 KB Output is correct
8 Correct 28 ms 59212 KB Output is correct
9 Correct 28 ms 59348 KB Output is correct
10 Correct 29 ms 59188 KB Output is correct
11 Correct 32 ms 59188 KB Output is correct
12 Correct 32 ms 59156 KB Output is correct
13 Correct 28 ms 59208 KB Output is correct
14 Correct 30 ms 59128 KB Output is correct
15 Correct 30 ms 59212 KB Output is correct
16 Correct 29 ms 59172 KB Output is correct
17 Correct 30 ms 59200 KB Output is correct
18 Correct 28 ms 59216 KB Output is correct
19 Correct 29 ms 59204 KB Output is correct
20 Correct 30 ms 59136 KB Output is correct
21 Correct 29 ms 59104 KB Output is correct
22 Correct 29 ms 59296 KB Output is correct
23 Correct 29 ms 59264 KB Output is correct
24 Correct 31 ms 59224 KB Output is correct
25 Correct 29 ms 59116 KB Output is correct
26 Correct 28 ms 59200 KB Output is correct
27 Correct 29 ms 59096 KB Output is correct
28 Correct 31 ms 59144 KB Output is correct
29 Correct 28 ms 59084 KB Output is correct
30 Correct 30 ms 59076 KB Output is correct
31 Correct 987 ms 102244 KB Output is correct
32 Correct 140 ms 66700 KB Output is correct
33 Correct 726 ms 84524 KB Output is correct
34 Correct 933 ms 102116 KB Output is correct
35 Correct 897 ms 96492 KB Output is correct
36 Correct 708 ms 84836 KB Output is correct
37 Correct 500 ms 86212 KB Output is correct
38 Correct 419 ms 79644 KB Output is correct
39 Correct 371 ms 81372 KB Output is correct
40 Correct 355 ms 79648 KB Output is correct
41 Correct 710 ms 88368 KB Output is correct
42 Correct 675 ms 94136 KB Output is correct
43 Correct 104 ms 68464 KB Output is correct
44 Correct 706 ms 87804 KB Output is correct
45 Correct 689 ms 84308 KB Output is correct
46 Correct 663 ms 80724 KB Output is correct
47 Correct 324 ms 88536 KB Output is correct
48 Correct 324 ms 86840 KB Output is correct
49 Correct 389 ms 89336 KB Output is correct
50 Correct 428 ms 94744 KB Output is correct
51 Correct 410 ms 87248 KB Output is correct
52 Execution timed out 5074 ms 353284 KB Time limit exceeded
53 Halted 0 ms 0 KB -