oj.uz

Submission #1112558

# Submission time Handle Problem Language Result Execution time Memory
1112558 2024-11-14T10:24:09 Z Pioneer New Home (APIO18_new_home) C++17
0 / 100
 3097 ms 231028 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*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){
        if(tl==tr){
            t[v].insert(x);
            mx[v]=*t[v].rbegin();
            return;
        }
        int tm=(tl+tr)/2;
        if(pos<=tm){
            add(2*v,tl,tm,pos,x);
        }
        else{
            add(2*v+1,tm+1,tr,pos,x);
        }
        mx[v]=max(mx[2*v],mx[2*v+1]);
    }

    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(2*v,tl,tm,pos,x);
        }
        else{
            del(2*v+1,tm+1,tr,pos,x);
        }
        mx[v]=max(mx[2*v],mx[2*v+1]);
    }

    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;
        return max(get(2*v,tl,tm,l,r),get(2*v+1,tm+1,tr,l,r));
    }
}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;
    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=max(x[id],inf-x[id]),res=max(x[id],inf-x[id]);
                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 95 ms 166468 KB Output is correct
2 Correct 86 ms 166472 KB Output is correct
3 Correct 91 ms 166464 KB Output is correct
4 Correct 94 ms 166528 KB Output is correct
5 Correct 97 ms 166472 KB Output is correct
6 Incorrect 105 ms 166472 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 166468 KB Output is correct
2 Correct 86 ms 166472 KB Output is correct
3 Correct 91 ms 166464 KB Output is correct
4 Correct 94 ms 166528 KB Output is correct
5 Correct 97 ms 166472 KB Output is correct
6 Incorrect 105 ms 166472 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 166468 KB Output is correct
2 Correct 86 ms 166472 KB Output is correct
3 Correct 91 ms 166464 KB Output is correct
4 Correct 94 ms 166528 KB Output is correct
5 Correct 97 ms 166472 KB Output is correct
6 Incorrect 105 ms 166472 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 166468 KB Output is correct
2 Correct 86 ms 166472 KB Output is correct
3 Correct 91 ms 166464 KB Output is correct
4 Correct 94 ms 166528 KB Output is correct
5 Correct 97 ms 166472 KB Output is correct
6 Incorrect 105 ms 166472 KB Output isn't correct
7 Halted 0 ms 0 KB -