oj.uz

Submission #1112551

# Submission time Handle Problem Language Result Execution time Memory
1112551 2024-11-14T10:13:32 Z Pioneer New Home (APIO18_new_home) C++17
57 / 100
 5000 ms 721580 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=3e5+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*8*MAX];
    int mx[4*8*MAX],L[4*8*MAX],R[4*8*MAX];
    int cnt=1;

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

    void add(int v,int tl,int tr,int pos,int x){
        if(tl==tr){
            t[v].insert(x);
            mx[v]=*t[v].rbegin();
            return;
        }
        int tm=(tl+tr)/2;
        if(pos<=tm){
            if(!L[v])L[v]=++cnt;
            add(L[v],tl,tm,pos,x);
        }
        else{
            if(!R[v])R[v]=++cnt;
            add(R[v],tm+1,tr,pos,x);
        }
        mx[v]=max(mx[L[v]],mx[R[v]]);
    }

    void del(int v,int tl,int tr,int pos,int x){
        if(tl==tr){
            t[v].erase(t[v].find(x));
            if(t[v].empty())mx[v]=-1;
            else mx[v]=*t[v].rbegin();
            return;
        }
        int tm=(tl+tr)/2;
        if(pos<=tm){
            del(L[v],tl,tm,pos,x);
        }
        else{
            del(R[v],tm+1,tr,pos,x);
        }
        mx[v]=max(mx[L[v]],mx[R[v]]);
    }

    int get(int v,int tl,int tr,int l,int r){
        if(l>r||tl>r||l>tr)return 0;
        if(l<=tl&&tr<=r)return mx[v];
        int tm=(tl+tr)/2;
        int res=0;
        if(L[v])res=max(res,get(L[v],tl,tm,l,r));
        if(R[v])res=max(res,get(R[v],tm+1,tr,l,r));
        return res;
    }
}tree;

int L[MAX],R[MAX];
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]);
        if(!(*l==-1&&*r==inf+1))tree.del(1,0,m-1,getx(*l+1),*r-1);
        tree.add(1,0,m-1,getx(*l+1),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]);
        tree.del(1,0,m-1,getx(*l+1),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,getx(*l+1),*r-1);
    }
}

bool check(int l,int r){
    l=max(l,0);
    r=min(r,inf);
    l=ub(all(pos),l)-pos.begin()-1;
    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]);
        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 358 ms 607816 KB Output is correct
2 Correct 360 ms 607680 KB Output is correct
3 Correct 340 ms 607856 KB Output is correct
4 Correct 328 ms 607820 KB Output is correct
5 Correct 340 ms 607816 KB Output is correct
6 Correct 340 ms 607952 KB Output is correct
7 Correct 332 ms 607816 KB Output is correct
8 Correct 382 ms 607832 KB Output is correct
9 Correct 355 ms 608024 KB Output is correct
10 Correct 356 ms 607924 KB Output is correct
11 Correct 339 ms 607816 KB Output is correct
12 Correct 362 ms 607816 KB Output is correct
13 Correct 353 ms 607816 KB Output is correct
14 Correct 369 ms 607816 KB Output is correct
15 Correct 349 ms 607952 KB Output is correct
16 Correct 337 ms 607820 KB Output is correct
17 Correct 366 ms 607916 KB Output is correct
18 Correct 362 ms 607912 KB Output is correct
19 Correct 359 ms 608072 KB Output is correct
20 Correct 373 ms 607816 KB Output is correct
21 Correct 372 ms 607816 KB Output is correct
22 Correct 350 ms 607916 KB Output is correct
23 Correct 362 ms 607816 KB Output is correct
24 Correct 360 ms 607816 KB Output is correct
25 Correct 347 ms 607756 KB Output is correct
26 Correct 333 ms 607816 KB Output is correct
27 Correct 323 ms 607928 KB Output is correct
28 Correct 388 ms 607816 KB Output is correct
29 Correct 381 ms 607948 KB Output is correct
30 Correct 361 ms 607816 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 607816 KB Output is correct
2 Correct 360 ms 607680 KB Output is correct
3 Correct 340 ms 607856 KB Output is correct
4 Correct 328 ms 607820 KB Output is correct
5 Correct 340 ms 607816 KB Output is correct
6 Correct 340 ms 607952 KB Output is correct
7 Correct 332 ms 607816 KB Output is correct
8 Correct 382 ms 607832 KB Output is correct
9 Correct 355 ms 608024 KB Output is correct
10 Correct 356 ms 607924 KB Output is correct
11 Correct 339 ms 607816 KB Output is correct
12 Correct 362 ms 607816 KB Output is correct
13 Correct 353 ms 607816 KB Output is correct
14 Correct 369 ms 607816 KB Output is correct
15 Correct 349 ms 607952 KB Output is correct
16 Correct 337 ms 607820 KB Output is correct
17 Correct 366 ms 607916 KB Output is correct
18 Correct 362 ms 607912 KB Output is correct
19 Correct 359 ms 608072 KB Output is correct
20 Correct 373 ms 607816 KB Output is correct
21 Correct 372 ms 607816 KB Output is correct
22 Correct 350 ms 607916 KB Output is correct
23 Correct 362 ms 607816 KB Output is correct
24 Correct 360 ms 607816 KB Output is correct
25 Correct 347 ms 607756 KB Output is correct
26 Correct 333 ms 607816 KB Output is correct
27 Correct 323 ms 607928 KB Output is correct
28 Correct 388 ms 607816 KB Output is correct
29 Correct 381 ms 607948 KB Output is correct
30 Correct 361 ms 607816 KB Output is correct
31 Correct 1000 ms 622264 KB Output is correct
32 Correct 796 ms 612500 KB Output is correct
33 Correct 995 ms 618680 KB Output is correct
34 Correct 932 ms 620472 KB Output is correct
35 Correct 946 ms 624536 KB Output is correct
36 Correct 969 ms 623704 KB Output is correct
37 Correct 823 ms 618520 KB Output is correct
38 Correct 868 ms 616632 KB Output is correct
39 Correct 805 ms 616664 KB Output is correct
40 Correct 833 ms 618188 KB Output is correct
41 Correct 817 ms 619004 KB Output is correct
42 Correct 653 ms 618168 KB Output is correct
43 Correct 472 ms 615868 KB Output is correct
44 Correct 787 ms 616888 KB Output is correct
45 Correct 804 ms 618164 KB Output is correct
46 Correct 765 ms 616632 KB Output is correct
47 Correct 571 ms 617400 KB Output is correct
48 Correct 597 ms 615864 KB Output is correct
49 Correct 676 ms 616632 KB Output is correct
50 Correct 656 ms 617912 KB Output is correct
51 Correct 735 ms 616332 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3571 ms 674196 KB Output is correct
2 Correct 4418 ms 666024 KB Output is correct
3 Correct 3477 ms 714852 KB Output is correct
4 Correct 3463 ms 678712 KB Output is correct
5 Correct 4719 ms 672392 KB Output is correct
6 Correct 4510 ms 675556 KB Output is correct
7 Correct 3223 ms 721580 KB Output is correct
8 Correct 3053 ms 692376 KB Output is correct
9 Correct 3080 ms 682144 KB Output is correct
10 Correct 4210 ms 676744 KB Output is correct
11 Correct 2796 ms 675084 KB Output is correct
12 Correct 2904 ms 676476 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4407 ms 681136 KB Output is correct
2 Execution timed out 5078 ms 635996 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 607816 KB Output is correct
2 Correct 360 ms 607680 KB Output is correct
3 Correct 340 ms 607856 KB Output is correct
4 Correct 328 ms 607820 KB Output is correct
5 Correct 340 ms 607816 KB Output is correct
6 Correct 340 ms 607952 KB Output is correct
7 Correct 332 ms 607816 KB Output is correct
8 Correct 382 ms 607832 KB Output is correct
9 Correct 355 ms 608024 KB Output is correct
10 Correct 356 ms 607924 KB Output is correct
11 Correct 339 ms 607816 KB Output is correct
12 Correct 362 ms 607816 KB Output is correct
13 Correct 353 ms 607816 KB Output is correct
14 Correct 369 ms 607816 KB Output is correct
15 Correct 349 ms 607952 KB Output is correct
16 Correct 337 ms 607820 KB Output is correct
17 Correct 366 ms 607916 KB Output is correct
18 Correct 362 ms 607912 KB Output is correct
19 Correct 359 ms 608072 KB Output is correct
20 Correct 373 ms 607816 KB Output is correct
21 Correct 372 ms 607816 KB Output is correct
22 Correct 350 ms 607916 KB Output is correct
23 Correct 362 ms 607816 KB Output is correct
24 Correct 360 ms 607816 KB Output is correct
25 Correct 347 ms 607756 KB Output is correct
26 Correct 333 ms 607816 KB Output is correct
27 Correct 323 ms 607928 KB Output is correct
28 Correct 388 ms 607816 KB Output is correct
29 Correct 381 ms 607948 KB Output is correct
30 Correct 361 ms 607816 KB Output is correct
31 Correct 1000 ms 622264 KB Output is correct
32 Correct 796 ms 612500 KB Output is correct
33 Correct 995 ms 618680 KB Output is correct
34 Correct 932 ms 620472 KB Output is correct
35 Correct 946 ms 624536 KB Output is correct
36 Correct 969 ms 623704 KB Output is correct
37 Correct 823 ms 618520 KB Output is correct
38 Correct 868 ms 616632 KB Output is correct
39 Correct 805 ms 616664 KB Output is correct
40 Correct 833 ms 618188 KB Output is correct
41 Correct 817 ms 619004 KB Output is correct
42 Correct 653 ms 618168 KB Output is correct
43 Correct 472 ms 615868 KB Output is correct
44 Correct 787 ms 616888 KB Output is correct
45 Correct 804 ms 618164 KB Output is correct
46 Correct 765 ms 616632 KB Output is correct
47 Correct 571 ms 617400 KB Output is correct
48 Correct 597 ms 615864 KB Output is correct
49 Correct 676 ms 616632 KB Output is correct
50 Correct 656 ms 617912 KB Output is correct
51 Correct 735 ms 616332 KB Output is correct
52 Correct 595 ms 630952 KB Output is correct
53 Correct 586 ms 628332 KB Output is correct
54 Correct 647 ms 624728 KB Output is correct
55 Correct 839 ms 624312 KB Output is correct
56 Correct 820 ms 623784 KB Output is correct
57 Correct 794 ms 620984 KB Output is correct
58 Correct 709 ms 621240 KB Output is correct
59 Correct 657 ms 626616 KB Output is correct
60 Correct 671 ms 619704 KB Output is correct
61 Correct 415 ms 628408 KB Output is correct
62 Correct 690 ms 632296 KB Output is correct
63 Correct 757 ms 627136 KB Output is correct
64 Correct 802 ms 624784 KB Output is correct
65 Correct 817 ms 620424 KB Output is correct
66 Correct 820 ms 616632 KB Output is correct
67 Correct 519 ms 614972 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 607816 KB Output is correct
2 Correct 360 ms 607680 KB Output is correct
3 Correct 340 ms 607856 KB Output is correct
4 Correct 328 ms 607820 KB Output is correct
5 Correct 340 ms 607816 KB Output is correct
6 Correct 340 ms 607952 KB Output is correct
7 Correct 332 ms 607816 KB Output is correct
8 Correct 382 ms 607832 KB Output is correct
9 Correct 355 ms 608024 KB Output is correct
10 Correct 356 ms 607924 KB Output is correct
11 Correct 339 ms 607816 KB Output is correct
12 Correct 362 ms 607816 KB Output is correct
13 Correct 353 ms 607816 KB Output is correct
14 Correct 369 ms 607816 KB Output is correct
15 Correct 349 ms 607952 KB Output is correct
16 Correct 337 ms 607820 KB Output is correct
17 Correct 366 ms 607916 KB Output is correct
18 Correct 362 ms 607912 KB Output is correct
19 Correct 359 ms 608072 KB Output is correct
20 Correct 373 ms 607816 KB Output is correct
21 Correct 372 ms 607816 KB Output is correct
22 Correct 350 ms 607916 KB Output is correct
23 Correct 362 ms 607816 KB Output is correct
24 Correct 360 ms 607816 KB Output is correct
25 Correct 347 ms 607756 KB Output is correct
26 Correct 333 ms 607816 KB Output is correct
27 Correct 323 ms 607928 KB Output is correct
28 Correct 388 ms 607816 KB Output is correct
29 Correct 381 ms 607948 KB Output is correct
30 Correct 361 ms 607816 KB Output is correct
31 Correct 1000 ms 622264 KB Output is correct
32 Correct 796 ms 612500 KB Output is correct
33 Correct 995 ms 618680 KB Output is correct
34 Correct 932 ms 620472 KB Output is correct
35 Correct 946 ms 624536 KB Output is correct
36 Correct 969 ms 623704 KB Output is correct
37 Correct 823 ms 618520 KB Output is correct
38 Correct 868 ms 616632 KB Output is correct
39 Correct 805 ms 616664 KB Output is correct
40 Correct 833 ms 618188 KB Output is correct
41 Correct 817 ms 619004 KB Output is correct
42 Correct 653 ms 618168 KB Output is correct
43 Correct 472 ms 615868 KB Output is correct
44 Correct 787 ms 616888 KB Output is correct
45 Correct 804 ms 618164 KB Output is correct
46 Correct 765 ms 616632 KB Output is correct
47 Correct 571 ms 617400 KB Output is correct
48 Correct 597 ms 615864 KB Output is correct
49 Correct 676 ms 616632 KB Output is correct
50 Correct 656 ms 617912 KB Output is correct
51 Correct 735 ms 616332 KB Output is correct
52 Correct 3571 ms 674196 KB Output is correct
53 Correct 4418 ms 666024 KB Output is correct
54 Correct 3477 ms 714852 KB Output is correct
55 Correct 3463 ms 678712 KB Output is correct
56 Correct 4719 ms 672392 KB Output is correct
57 Correct 4510 ms 675556 KB Output is correct
58 Correct 3223 ms 721580 KB Output is correct
59 Correct 3053 ms 692376 KB Output is correct
60 Correct 3080 ms 682144 KB Output is correct
61 Correct 4210 ms 676744 KB Output is correct
62 Correct 2796 ms 675084 KB Output is correct
63 Correct 2904 ms 676476 KB Output is correct
64 Correct 4407 ms 681136 KB Output is correct
65 Execution timed out 5078 ms 635996 KB Time limit exceeded
66 Halted 0 ms 0 KB -