oj.uz

Submission #1112493

# Submission time Handle Problem Language Result Execution time Memory
1112493 2024-11-14T08:50:38 Z Pioneer New Home (APIO18_new_home) C++17
0 / 100
 3110 ms 214472 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;

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();
            mx[v]=x;
            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();
            mx[v]=-1;
            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;

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,inf,*l+1,*r-1);
        tree.add(1,0,inf,*l+1,x[id]-1);
        tree.add(1,0,inf,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,inf,*l+1,x[id]-1);
        tree.del(1,0,inf,x[id]+1,*r-1);
        if(!(*l==-1&&*r==inf+1))tree.add(1,0,inf,*l+1,*r-1);
    }
}

bool check(int l,int r){
    l=max(l,0);
    r=min(r,inf);
    if(tree.get(1,0,inf,0,l)>=r)return 0;
    return 1;
}

int ans[MAX];

void solve(){
    cin>>n>>k>>q;
    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);
    }
    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());
    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);
    }
    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 156364 KB Output is correct
2 Correct 32 ms 156232 KB Output is correct
3 Correct 26 ms 156240 KB Output is correct
4 Correct 25 ms 156488 KB Output is correct
5 Incorrect 22 ms 158288 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 156364 KB Output is correct
2 Correct 32 ms 156232 KB Output is correct
3 Correct 26 ms 156240 KB Output is correct
4 Correct 25 ms 156488 KB Output is correct
5 Incorrect 22 ms 158288 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2554 ms 214280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 3110 ms 214472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 156364 KB Output is correct
2 Correct 32 ms 156232 KB Output is correct
3 Correct 26 ms 156240 KB Output is correct
4 Correct 25 ms 156488 KB Output is correct
5 Incorrect 22 ms 158288 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 156364 KB Output is correct
2 Correct 32 ms 156232 KB Output is correct
3 Correct 26 ms 156240 KB Output is correct
4 Correct 25 ms 156488 KB Output is correct
5 Incorrect 22 ms 158288 KB Output isn't correct
6 Halted 0 ms 0 KB -