oj.uz

Submission #1112575

# Submission time Handle Problem Language Result Execution time Memory
1112575 2024-11-14T10:59:25 Z Pioneer New Home (APIO18_new_home) C++17
57 / 100
 5000 ms 652580 KB 
#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
// #pragma GCC target("avx2")

#define ll long long
// #define int ll
#define all(v) v.begin(),v.end()
#define sz(s) ((int)s.size())
#define pb push_back
#define F first
#define S second
#define pii pair<int,int>
#define ppb pop_back
#define lb lower_bound
#define ub upper_bound

using namespace std;

const int inf=1e8;
const int MAX=1e6+10;
const int mod=1e9+7;

int binpow(int a,int n){
    if(!n)return 1;
    if(n%2==1)return a*binpow(a,n-1)%mod;
    int k=binpow(a,n/2);
    return k*k%mod;
}

int n,k,q,m;
int a[MAX],b[MAX],x[MAX],t[MAX];
int l[MAX],y[MAX];
vector<int> events[MAX+MAX],zap[MAX+MAX];
multiset<int> st[MAX];
vector<int> tim,pos;

struct segtree{
    multiset<int> t[4*2*MAX];
    int mx[4*2*MAX];

    segtree(){
        memset(mx,-1,sizeof(mx));
    }

    void add(int v,int tl,int tr,int pos,int x){
        pos+=m;
        t[pos].insert(x);
        mx[pos]=*t[pos].rbegin();
        while(pos>1){
            pos/=2;
            mx[pos]=max(mx[2*pos],mx[2*pos+1]);
        }
    }

    void del(int v,int tl,int tr,int pos,int x){
        pos+=m;
        t[pos].erase(t[pos].find(x));
        mx[pos]=(t[pos].empty()?-1:*t[pos].rbegin());
        while(pos>1){
            pos/=2;
            mx[pos]=max(mx[2*pos],mx[2*pos+1]);
        }
    }

    int get(int v,int tl,int tr,int l,int r){
        l+=m,r+=m+1;
        int res=0;
        while(l<r){
            if(l&1){
                res=max(res,mx[l++]);
            }
            if(r&1){
                res=max(res,mx[--r]);
            }
            l/=2,r/=2;
        }
        return res;
    }
}tree;

int cnt[MAX],col;

int getx(int x){
    return lb(all(pos),x)-pos.begin();
}

void add(int id){
    if(cnt[t[id]]==0)col++;
    cnt[t[id]]++;
    if(st[t[id]].count(x[id]))st[t[id]].insert(x[id]);
    else{
        auto l=--st[t[id]].lb(x[id]);
        auto r=st[t[id]].lb(x[id]);
        int LL=getx(*l+1);
        if(!(*l==-1&&*r==inf+1))tree.del(1,0,m-1,LL,*r-1);
        tree.add(1,0,m-1,LL,x[id]-1);
        tree.add(1,0,m-1,getx(x[id]+1),*r-1);
        st[t[id]].insert(x[id]);
    }
}

void del(int id){
    id=-id;
    cnt[t[id]]--;
    if(cnt[t[id]]==0)col--;
    st[t[id]].erase(st[t[id]].find(x[id]));
    if(!st[t[id]].count(x[id])){
        auto l=--st[t[id]].lb(x[id]);
        auto r=st[t[id]].lb(x[id]);
        int LL=getx(*l+1);
        tree.del(1,0,m-1,LL,x[id]-1);
        tree.del(1,0,m-1,getx(x[id]+1),*r-1);
        if(!(*l==-1&&*r==inf+1))tree.add(1,0,m-1,LL,*r-1);
    }
}

bool check(int l,int r){
    l=max(l,0);
    r=min(r,inf);
    l=ub(all(pos),l)-pos.begin()-1;
    // cout<<0<<" "<<l<<" "<<tree.get(1,0,m-1,0,l)<<"\n";
    if(tree.get(1,0,m-1,0,l)>=r)return 0;
    return 1;
}

int ans[MAX];

void solve(){
    cin>>n>>k>>q;
    pos.pb(0),pos.pb(inf);
    for(int i=1;i<=n;i++){
        cin>>x[i]>>t[i]>>a[i]>>b[i];
        tim.pb(a[i]);
        tim.pb(b[i]+1);
        pos.pb(x[i]+1);
        pos.pb(x[i]-1);
    }
    for(int i=1;i<=q;i++){
        cin>>l[i]>>y[i];
        tim.pb(y[i]);
    }
    sort(all(tim));
    tim.erase(unique(all(tim)),tim.end());
    sort(all(pos));
    pos.erase(unique(all(pos)),pos.end());
    for(int i=1;i<=n;i++){
        a[i]=lb(all(tim),a[i])-tim.begin();
        b[i]=lb(all(tim),b[i]+1)-tim.begin();
        events[a[i]].pb(i);
        events[b[i]].pb(-i);
    }
    for(int i=1;i<=q;i++){
        y[i]=lb(all(tim),y[i])-tim.begin();
        zap[y[i]].pb(i);
    }
    for(int i=1;i<=k;i++){
        st[i].insert(-1);
        st[i].insert(inf+1);
    }
    m=sz(pos);
    for(int i=0;i<sz(tim);i++){
        for(auto id:events[i]){
            if(id>0){
                add(id);
            }
            else{
                del(id);
            }
        }
        for(int id:zap[i]){
            if(col!=k){
                ans[id]=-1;
            }
            else{
                int L=0,R=inf,res=inf;
                while(L<=R){
                    int mid=(L+R)/2;
                    if(check(l[id]-mid,l[id]+mid)){
                        R=mid-1,res=mid;
                    }
                    else L=mid+1;
                }
                ans[id]=res;
            }
        }
    }
    for(int i=1;i<=q;i++)cout<<ans[i]<<"\n";
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 548732 KB Output is correct
2 Correct 302 ms 548940 KB Output is correct
3 Correct 304 ms 548680 KB Output is correct
4 Correct 303 ms 548680 KB Output is correct
5 Correct 304 ms 548980 KB Output is correct
6 Correct 309 ms 548936 KB Output is correct
7 Correct 278 ms 548936 KB Output is correct
8 Correct 284 ms 548936 KB Output is correct
9 Correct 283 ms 548936 KB Output is correct
10 Correct 299 ms 548856 KB Output is correct
11 Correct 274 ms 548888 KB Output is correct
12 Correct 267 ms 548784 KB Output is correct
13 Correct 294 ms 548936 KB Output is correct
14 Correct 314 ms 548932 KB Output is correct
15 Correct 301 ms 548912 KB Output is correct
16 Correct 301 ms 548936 KB Output is correct
17 Correct 308 ms 548804 KB Output is correct
18 Correct 302 ms 548936 KB Output is correct
19 Correct 325 ms 548936 KB Output is correct
20 Correct 315 ms 548884 KB Output is correct
21 Correct 309 ms 549064 KB Output is correct
22 Correct 324 ms 548940 KB Output is correct
23 Correct 305 ms 548860 KB Output is correct
24 Correct 333 ms 548880 KB Output is correct
25 Correct 307 ms 548788 KB Output is correct
26 Correct 326 ms 548936 KB Output is correct
27 Correct 315 ms 548936 KB Output is correct
28 Correct 309 ms 548940 KB Output is correct
29 Correct 306 ms 548872 KB Output is correct
30 Correct 306 ms 548792 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 548732 KB Output is correct
2 Correct 302 ms 548940 KB Output is correct
3 Correct 304 ms 548680 KB Output is correct
4 Correct 303 ms 548680 KB Output is correct
5 Correct 304 ms 548980 KB Output is correct
6 Correct 309 ms 548936 KB Output is correct
7 Correct 278 ms 548936 KB Output is correct
8 Correct 284 ms 548936 KB Output is correct
9 Correct 283 ms 548936 KB Output is correct
10 Correct 299 ms 548856 KB Output is correct
11 Correct 274 ms 548888 KB Output is correct
12 Correct 267 ms 548784 KB Output is correct
13 Correct 294 ms 548936 KB Output is correct
14 Correct 314 ms 548932 KB Output is correct
15 Correct 301 ms 548912 KB Output is correct
16 Correct 301 ms 548936 KB Output is correct
17 Correct 308 ms 548804 KB Output is correct
18 Correct 302 ms 548936 KB Output is correct
19 Correct 325 ms 548936 KB Output is correct
20 Correct 315 ms 548884 KB Output is correct
21 Correct 309 ms 549064 KB Output is correct
22 Correct 324 ms 548940 KB Output is correct
23 Correct 305 ms 548860 KB Output is correct
24 Correct 333 ms 548880 KB Output is correct
25 Correct 307 ms 548788 KB Output is correct
26 Correct 326 ms 548936 KB Output is correct
27 Correct 315 ms 548936 KB Output is correct
28 Correct 309 ms 548940 KB Output is correct
29 Correct 306 ms 548872 KB Output is correct
30 Correct 306 ms 548792 KB Output is correct
31 Correct 707 ms 563312 KB Output is correct
32 Correct 680 ms 553568 KB Output is correct
33 Correct 726 ms 559540 KB Output is correct
34 Correct 721 ms 559544 KB Output is correct
35 Correct 751 ms 563096 KB Output is correct
36 Correct 687 ms 563128 KB Output is correct
37 Correct 612 ms 559800 KB Output is correct
38 Correct 624 ms 557932 KB Output is correct
39 Correct 613 ms 557464 KB Output is correct
40 Correct 609 ms 557348 KB Output is correct
41 Correct 551 ms 557752 KB Output is correct
42 Correct 504 ms 557608 KB Output is correct
43 Correct 420 ms 556164 KB Output is correct
44 Correct 581 ms 557752 KB Output is correct
45 Correct 557 ms 557652 KB Output is correct
46 Correct 609 ms 557496 KB Output is correct
47 Correct 481 ms 557012 KB Output is correct
48 Correct 503 ms 557080 KB Output is correct
49 Correct 539 ms 557280 KB Output is correct
50 Correct 512 ms 557496 KB Output is correct
51 Correct 561 ms 557240 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1975 ms 614632 KB Output is correct
2 Correct 3198 ms 604688 KB Output is correct
3 Correct 2154 ms 650628 KB Output is correct
4 Correct 2211 ms 621912 KB Output is correct
5 Correct 2900 ms 604360 KB Output is correct
6 Correct 3045 ms 608220 KB Output is correct
7 Correct 2004 ms 652580 KB Output is correct
8 Correct 1814 ms 621972 KB Output is correct
9 Correct 2013 ms 612012 KB Output is correct
10 Correct 2628 ms 605420 KB Output is correct
11 Correct 1876 ms 604084 KB Output is correct
12 Correct 1887 ms 606976 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3054 ms 613908 KB Output is correct
2 Execution timed out 5067 ms 576876 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 548732 KB Output is correct
2 Correct 302 ms 548940 KB Output is correct
3 Correct 304 ms 548680 KB Output is correct
4 Correct 303 ms 548680 KB Output is correct
5 Correct 304 ms 548980 KB Output is correct
6 Correct 309 ms 548936 KB Output is correct
7 Correct 278 ms 548936 KB Output is correct
8 Correct 284 ms 548936 KB Output is correct
9 Correct 283 ms 548936 KB Output is correct
10 Correct 299 ms 548856 KB Output is correct
11 Correct 274 ms 548888 KB Output is correct
12 Correct 267 ms 548784 KB Output is correct
13 Correct 294 ms 548936 KB Output is correct
14 Correct 314 ms 548932 KB Output is correct
15 Correct 301 ms 548912 KB Output is correct
16 Correct 301 ms 548936 KB Output is correct
17 Correct 308 ms 548804 KB Output is correct
18 Correct 302 ms 548936 KB Output is correct
19 Correct 325 ms 548936 KB Output is correct
20 Correct 315 ms 548884 KB Output is correct
21 Correct 309 ms 549064 KB Output is correct
22 Correct 324 ms 548940 KB Output is correct
23 Correct 305 ms 548860 KB Output is correct
24 Correct 333 ms 548880 KB Output is correct
25 Correct 307 ms 548788 KB Output is correct
26 Correct 326 ms 548936 KB Output is correct
27 Correct 315 ms 548936 KB Output is correct
28 Correct 309 ms 548940 KB Output is correct
29 Correct 306 ms 548872 KB Output is correct
30 Correct 306 ms 548792 KB Output is correct
31 Correct 707 ms 563312 KB Output is correct
32 Correct 680 ms 553568 KB Output is correct
33 Correct 726 ms 559540 KB Output is correct
34 Correct 721 ms 559544 KB Output is correct
35 Correct 751 ms 563096 KB Output is correct
36 Correct 687 ms 563128 KB Output is correct
37 Correct 612 ms 559800 KB Output is correct
38 Correct 624 ms 557932 KB Output is correct
39 Correct 613 ms 557464 KB Output is correct
40 Correct 609 ms 557348 KB Output is correct
41 Correct 551 ms 557752 KB Output is correct
42 Correct 504 ms 557608 KB Output is correct
43 Correct 420 ms 556164 KB Output is correct
44 Correct 581 ms 557752 KB Output is correct
45 Correct 557 ms 557652 KB Output is correct
46 Correct 609 ms 557496 KB Output is correct
47 Correct 481 ms 557012 KB Output is correct
48 Correct 503 ms 557080 KB Output is correct
49 Correct 539 ms 557280 KB Output is correct
50 Correct 512 ms 557496 KB Output is correct
51 Correct 561 ms 557240 KB Output is correct
52 Correct 512 ms 571964 KB Output is correct
53 Correct 497 ms 567224 KB Output is correct
54 Correct 567 ms 566456 KB Output is correct
55 Correct 613 ms 563368 KB Output is correct
56 Correct 611 ms 564664 KB Output is correct
57 Correct 610 ms 559032 KB Output is correct
58 Correct 583 ms 562208 KB Output is correct
59 Correct 553 ms 564692 KB Output is correct
60 Correct 572 ms 558976 KB Output is correct
61 Correct 390 ms 567992 KB Output is correct
62 Correct 565 ms 571724 KB Output is correct
63 Correct 557 ms 569784 KB Output is correct
64 Correct 528 ms 564152 KB Output is correct
65 Correct 550 ms 559640 KB Output is correct
66 Correct 511 ms 559740 KB Output is correct
67 Correct 391 ms 554696 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 548732 KB Output is correct
2 Correct 302 ms 548940 KB Output is correct
3 Correct 304 ms 548680 KB Output is correct
4 Correct 303 ms 548680 KB Output is correct
5 Correct 304 ms 548980 KB Output is correct
6 Correct 309 ms 548936 KB Output is correct
7 Correct 278 ms 548936 KB Output is correct
8 Correct 284 ms 548936 KB Output is correct
9 Correct 283 ms 548936 KB Output is correct
10 Correct 299 ms 548856 KB Output is correct
11 Correct 274 ms 548888 KB Output is correct
12 Correct 267 ms 548784 KB Output is correct
13 Correct 294 ms 548936 KB Output is correct
14 Correct 314 ms 548932 KB Output is correct
15 Correct 301 ms 548912 KB Output is correct
16 Correct 301 ms 548936 KB Output is correct
17 Correct 308 ms 548804 KB Output is correct
18 Correct 302 ms 548936 KB Output is correct
19 Correct 325 ms 548936 KB Output is correct
20 Correct 315 ms 548884 KB Output is correct
21 Correct 309 ms 549064 KB Output is correct
22 Correct 324 ms 548940 KB Output is correct
23 Correct 305 ms 548860 KB Output is correct
24 Correct 333 ms 548880 KB Output is correct
25 Correct 307 ms 548788 KB Output is correct
26 Correct 326 ms 548936 KB Output is correct
27 Correct 315 ms 548936 KB Output is correct
28 Correct 309 ms 548940 KB Output is correct
29 Correct 306 ms 548872 KB Output is correct
30 Correct 306 ms 548792 KB Output is correct
31 Correct 707 ms 563312 KB Output is correct
32 Correct 680 ms 553568 KB Output is correct
33 Correct 726 ms 559540 KB Output is correct
34 Correct 721 ms 559544 KB Output is correct
35 Correct 751 ms 563096 KB Output is correct
36 Correct 687 ms 563128 KB Output is correct
37 Correct 612 ms 559800 KB Output is correct
38 Correct 624 ms 557932 KB Output is correct
39 Correct 613 ms 557464 KB Output is correct
40 Correct 609 ms 557348 KB Output is correct
41 Correct 551 ms 557752 KB Output is correct
42 Correct 504 ms 557608 KB Output is correct
43 Correct 420 ms 556164 KB Output is correct
44 Correct 581 ms 557752 KB Output is correct
45 Correct 557 ms 557652 KB Output is correct
46 Correct 609 ms 557496 KB Output is correct
47 Correct 481 ms 557012 KB Output is correct
48 Correct 503 ms 557080 KB Output is correct
49 Correct 539 ms 557280 KB Output is correct
50 Correct 512 ms 557496 KB Output is correct
51 Correct 561 ms 557240 KB Output is correct
52 Correct 1975 ms 614632 KB Output is correct
53 Correct 3198 ms 604688 KB Output is correct
54 Correct 2154 ms 650628 KB Output is correct
55 Correct 2211 ms 621912 KB Output is correct
56 Correct 2900 ms 604360 KB Output is correct
57 Correct 3045 ms 608220 KB Output is correct
58 Correct 2004 ms 652580 KB Output is correct
59 Correct 1814 ms 621972 KB Output is correct
60 Correct 2013 ms 612012 KB Output is correct
61 Correct 2628 ms 605420 KB Output is correct
62 Correct 1876 ms 604084 KB Output is correct
63 Correct 1887 ms 606976 KB Output is correct
64 Correct 3054 ms 613908 KB Output is correct
65 Execution timed out 5067 ms 576876 KB Time limit exceeded
66 Halted 0 ms 0 KB -