Submission #710692

#	Time	Username	Problem	Language	Result	Execution time	Memory
710692		lam	New Home (APIO18_new_home)	C++14	5 / 100	5064 ms	284384 KiB

new_home

#include <bits/stdc++.h>
#define int long long
using namespace std;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
typedef pair<int,int> ii;
typedef pair<ii,int> iii;
typedef pair<ii,ii> iiii;
#define ff first
#define ss second
const int maxn = 3e5+10;
int n,k,m,o;
map<int,int> mp;
multiset<int> ms[maxn];
int b[maxn];
vector <iiii> d;
int res[maxn];
struct node
{
    int wt, key, sz;
    node *l, *r;
    node (int x)
    {
        l=r=0;
        sz = 1;
        key = x; sz = 1;
        wt = rng();
    }
};
inline int get_sz(node *&x)
{
    return (x)?x->sz:0;
}
inline void update(node *&x)
{
    x->sz = 1 + get_sz(x->l) + get_sz(x->r);
}

void split(node *x, node *&l, node *&r, int k)
{
    if (!x)
    {
        l=r=0;
        return;
    }
    if (get_sz(x->l)>=k)
    {
        split(x->l,l,x->l,k);
        r=x;
    }
    else
    {
        split(x->r,x->r,r,k-1-get_sz(x->l));
        l=x;
    }
    update(x);
}

void split_key(node *x, node *&l, node *&r, int key)
{
    if (!x)
    {
        l=r=0;
        return;
    }
    if (x->key > key)
    {
        split_key(x->l,l,x->l,key);
        r=x;
    }
    else
    {
        split_key(x->r,x->r,r,key);
        l=x;
    }
    update(x);
}

void merg(node *&x, node *l, node *r)
{
    if (!l||!r)
    {
        if (!l) x=r;
        else x=l;
        return;
    }
    if (l->wt > r->wt)
    {
        merg(l->r,l->r,r);
        x=l;
    }
    else
    {
        merg(r->l,l,r->l);
        x=r;
    }
    update(x);
}

void ins(node *&treap, int val)
{
    node *a,*b;
    split_key(treap,treap,a,val);
    b = new node(val);
    merg(treap,treap,b);
    merg(treap,treap,a);
}

void dbg(node *&x)
{
    if (!x) return;
    dbg(x->l);
    cerr<<x->key<<" :: ";
    dbg(x->r);
}
void xoa(node *&treap, int val)
{
    node *a, *b;
//    cerr<<"xoa "<<val<<endl;
//    dbg(treap); cerr<<endl;
    split_key(treap,treap,a,val-1);
    split(a,b,a,1);
    merg(treap,treap,a);
//    dbg(treap); cerr<<endl;
//    cerr<<"------------"<<endl;
    delete(b);
}


int lbound(node *&treap, int r)
{
    node *a,*b;
//    cerr<<"dbg "; dbg(treap); cerr<<endl;
    split_key(treap,treap,a,r);
    int ans = get_sz(a);
    merg(treap,treap,a);
//    cerr<<r<<" --> "<<ans<<endl;
    return ans;
}

node* f[4*maxn];

int get(int x, int lx, int rx, int l, int r)
{
    if (b[lx]>r||b[rx]<l) return 0;
    if (b[lx]>=l&&b[rx]<=r)
    {
//        cerr<<"??? "<<x<<' '<<b[lx]<<' '<<b[rx]<<endl;
        return lbound(f[x],r);
    }
    int mid=(lx+rx)/2;
    return get(2*x,lx,mid,l,r) + get(2*x+1,mid+1,rx,l,r);
}

void add(int x, int lx, int rx, int idx, int val)
{
//    cerr<<"+ "<<x<<' '<<b[lx]<<' '<<b[rx]<<" = "<<idx<<' '<<val<<endl;
    ins(f[x],val);
//    cerr<<" :) "<<endl;
    if (lx==rx) return;
    int mid=(lx+rx)/2;
    if (idx<=b[mid]) add(2*x,lx,mid,idx,val);
    else add(2*x+1,mid+1,rx,idx,val);
}
void er(int x, int lx, int rx, int idx, int val)
{
//    cerr<<"- "<<x<<' '<<b[lx]<<' '<<b[rx]<<" = "<<idx<<' '<<val<<endl;
    xoa(f[x],val);
//    cerr<<" :< "<<endl;
    if (lx==rx) return;
    int mid=(lx+rx)/2;
    if (idx<=b[mid]) er(2*x,lx,mid,idx,val);
    else er(2*x+1,mid+1,rx,idx,val);
}

void build(int x, int lx, int rx)
{
    f[x] = 0;
    if (lx==rx) return;
    int mid=(lx+rx)/2;
    build(2*x,lx,mid); build(2*x+1,mid+1,rx);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin>>n>>k>>m;
    for (int i=1; i<=n; i++)
    {
        int x,t,l,r; cin>>x>>t>>l>>r;
        mp[x] = 1;
        d.push_back({{l,-1},{x,t}});
        d.push_back({{r,1},{x,t}});
    }
    for (int i=1; i<=m; i++)
    {
        int x,l; cin>>x>>l;
        d.push_back({{l,0},{x,i}});
    }
    sort(d.begin(),d.end());
    int cnt = 0;
    o = 0;
    for (auto &c:mp) c.ss = ++o, b[o] = c.ff;
//    cerr<<o<<endl;
    build(1,1,o);
    for (iiii i:d)
    {
//        cerr<<" -- "<<i.ff.ff<<' '<<i.ff.ss<<' '<<i.ss.ff<<' '<<i.ss.ss<<" -- "<<endl;
        if (i.ff.ss == -1)
        {
            int x = i.ss.ff; int t = i.ss.ss;
//            cerr<<"pro "<<x<<endl;
            if (ms[t].empty()) cnt++;
            auto r = ms[t].upper_bound(x);
            auto l = r;
            if (l!=ms[t].begin())
            {
                l--;
                if (r!=ms[t].end())
                    er(1,1,o,(*l),(*r));
                else er(1,1,o,(*l),1e9);
                add(1,1,o,(*l),x);
            }
            if (r!=ms[t].end()) add(1,1,o,x,(*r));
            else add(1,1,o,x,1e9);
            ms[t].insert(x);
//            cerr<<"pri"<<endl;
        }
        else if (i.ff.ss == 1)
        {
            int x = i.ss.ff; int t = i.ss.ss;
            auto j = ms[t].lower_bound(x);
            auto l = j; auto r = j;
//            cerr<<"notpro "<<x<<endl;
            if (r==ms[t].end()) cerr<<" :@"<<endl;
            r++;
            if (l!=ms[t].begin())
            {
                l--;
                er(1,1,o,(*l),x);
                if (r!=ms[t].end()) add(1,1,o,(*l),(*r));
                else add(1,1,o,(*l),1e9);
            }
            if (r!=ms[t].end()) er(1,1,o,x,(*r));
            else er(1,1,o,x,1e9);
            ms[t].erase(ms[t].find(x));
//            cerr<<"notpri"<<endl;
            if (ms[t].empty()) cnt--;
        }
        else
        {
            int x = i.ss.ff; int id = i.ss.ss;
            if (cnt<k) res[id] = -1;
            else
            {
                int l,r;
//                cerr<<"? "<<x<<' '<<cnt<<" = "<<id<<endl;
                l = 0; r = max(x-1,100000000-x);
                int ans = -1;
                while (l<=r)
                {
                    int mid = l+(r-l)/2;
                    if (get(1,1,o,x-mid,x+mid)==k)
                    {
                        ans = mid;
                        r=mid-1;
                    }
                    else l=mid+1;
                }
                res[id] = ans;
            }
        }
    }
    for (int i=1; i<=m; i++) cout<<res[i]<<'\n';
}
/**
4 2 4
3 1 1 10
9 2 1 7
7 2 1 4
4 1 1 10
5 3
5 5
5 8
1 4
**/

Compilation message (stderr)

new_home.cpp: In function 'long long int lbound(node*&, long long int)':
new_home.cpp:131:14: warning: unused variable 'b' [-Wunused-variable]
  131 |     node *a,*b;
      |              ^

• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20