Submission #808673

#	Time	Username	Problem	Language	Result	Execution time	Memory
808673		DJeniUp	The Potion of Great Power (CEOI20_potion)	C++17	0 / 100	3062 ms	94792 KiB

potion

#include "bits/stdc++.h"

using namespace std;

typedef int ll;
typedef pair<ll,ll>pairll;

#define N1 100007
#define INF 1000000000
#define pb push_back
#define fr first
#define sc second

ll n,m,h[N1],h1;

vector<pairll>p[N1];

queue<ll>h2;

map<ll,ll>mp;

struct T{
    ll l,r,s;
}t[80*N1];

struct D{
    ll n,h;
}d[N1];

bool mcp(D d1,D d2){
    return d1.h<d2.h;
}

void init(int N, int D, int H[]) {
    n=N;
    m=D;
    for(int i=0;i<n;i++){
        h[i]=H[i];
        p[i].pb({0,0});
        d[i]={i,h[i]};
    }

    sort(d,d+n,mcp);
    sort(h,h+n);
    for(int i=0;i<n;i++){
        mp[d[i].n]=i;
    }
    return ;
}

void Add(ll x,ll y,ll l,ll r,ll tl){

    if(r<tl || tl<l)return ;
    if(l==r){
        t[x].s^=1;
        return ;
    }
    ll m1=(l+r)/2;
    if(tl<=m1){
        ll k=0;
        if(t[y].l==0){
            h1++;
            k=h1;
        }else k=t[y].l;
        t[k]=t[t[y].l];
        t[x].l=k;
        Add(t[x].l,t[y].l,l,m1,tl);
    }else{
        ll k=0;
        if(t[y].r==0){
            h1++;
            k=h1;
        }else k=t[y].r;
        t[k]=t[t[y].r];
        t[x].r=k;
        Add(t[x].r,t[y].r,m1+1,r,tl);
    }
    t[x].s=t[t[x].l].s+t[t[x].r].s;
    if(t[t[x].l].s==0 && t[x].l!=0){
        h2.push(t[x].l);
        t[x].l=0;
    }

    if(t[t[x].r].s==0 && t[x].r!=0){
        h2.push(t[x].r);
        t[x].r=0;
    }
   // cout<<"?! "<<x<<" "<<l<<" "<<r<<" "<<tl<<" "<<t[x].s<<endl;
    return ;
}

void curseChanges(int U, int A[], int B[]) {
    for(int i=0;i<U;i++){
        h1++;
        A[i]=mp[A[i]];
        B[i]=mp[B[i]];
        t[h1]=t[p[A[i]].back().sc];
        p[A[i]].pb({i,h1});
        Add(h1,p[A[i]][p[A[i]].size()-2].sc,0,n-1,B[i]);

        h1++;
        t[h1]=t[p[B[i]].back().sc];
        p[B[i]].pb({i,h1});
        Add(h1,p[B[i]][p[B[i]].size()-2].sc,0,n-1,A[i]);
    }
    return ;
}

ll R(ll x,ll l,ll r,ll tl){
    //cout<<"? "<<x<<" "<<l<<" "<<r<<" "<<tl<<" "<<t[x].s<<endl;
    if(r<tl || t[x].s==0)return INF;
    if(l==r)return l;
    ll m1=(l+r)/2;
    ll r1=INF;
    if(tl<=m1)r1=R(t[x].l,l,m1,tl);
    if(r1!=INF)return r1;
    return R(t[x].r,m1+1,r,tl);
}

int question(int x, int y, int v) {
    x=mp[x];
    y=mp[y];
    ll res=INF;
    ll l=0;
    ll r=p[x].size()-1;
    while(l<r){
        ll m1=(l+r+1)/2;
        if(p[x][m1].fr>=v)r=m1-1;
        else l=m1;
    }

    ll l1=0;
    ll r1=p[y].size()-1;
    while(l1<r1){
        ll m1=(l1+r1+1)/2;
        if(p[y][m1].fr>=v)r1=m1-1;
        else l1=m1;
    }
    //cout<<"! "<<l<<" "<<l1<<endl;
    ll a=-1;
    while(1){
        a=R(p[x][l].sc,0,n-1,a+1);
        if(a==INF)break;
        ll b=R(p[y][l1].sc,0,n-1,a);
        if(b==INF)break;
        res=min(res,abs(h[a]-h[b]));
        if(res==0)break;
        //cout<<a<<" "<<b<<endl;
    }
    a=-1;
    while(1){
        a=R(p[y][l1].sc,0,n-1,a+1);
        if(a==INF)break;
        ll b=R(p[x][l].sc,0,n-1,a);
        if(b==INF)break;
        res=min(res,abs(h[a]-h[b]));
        if(res==0)break;
        //cout<<a<<" "<<b<<endl;

    }
    return res;
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 17
• Subtask 3: 0 / 14
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 30