Submission #715858

#	Time	Username	Problem	Language	Result	Execution time	Memory
715858		PoonYaPat	The Potion of Great Power (CEOI20_potion)	C++14	0 / 100	442 ms	109892 KiB

potion

#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;

const ll inf=2e9+10;
struct node {
    ll mmin,mmax;
    short cnt;
    node *l, *r;

    node() : mmin(inf), mmax(-inf), cnt(0) {}
    node(int val, int c) : mmin(val), mmax(val), cnt(c) {}
    node(node *L, node *R) : l(L), r(R) {
        mmin=min(L->mmin,R->mmin);
        mmax=max(L->mmax,R->mmax);
        cnt=L->cnt+R->cnt;
    }
};

typedef node* pnode;

pnode build(int l, int r) {
    if (l==r) return new node();
    else {
        int mid=(l+r)/2;
        return new node(build(l,mid),build(mid+1,r));
    }
}

pnode update(int l, int r, int x, int val, int cnt, pnode t) {
    if (x>r || x<l) return t;
    if (l==r) {
        if (cnt==0) return new node();
        return new node(val,cnt);
    }
    int mid=(l+r)/2;
    return new node(update(l,mid,x,val,cnt,t->l),update(mid+1,r,x,val,cnt,t->r));
}

ll query(int l, int r, pnode a, pnode b, ll mi, ll ma) {

    if (a->cnt==0) return INT_MAX;
    if (l==r) {
        if (b->cnt==1) return 0;
        else return min(mi-a->mmin,a->mmin-ma);
    }
    int mid=(l+r)/2;
    return min(query(l,mid,a->l,b->l,min(mi,b->r->mmin),ma),query(mid+1,r,a->r,b->r,mi,max(ma,b->l->mmax)));
}

int n,mx;
vector<pnode> v;
vector<pii> vv[100001]; //day, order
vector<pii> cc;
map<pii,bool> mp;
pii pos[100001]; //pos,val

void init(int N, int D, int H[]) {
    n=N;
    for (int i=0; i<n; ++i) cc.push_back(pii(H[i],i));
    sort(cc.begin(),cc.end());
    for (int i=0; i<n; ++i) pos[cc[i].second]=pii(i+1,cc[i].first);

    v.push_back(build(1,n));
    for (int i=0; i<n; ++i) vv[i].push_back(pii(0,0));

}

void curseChanges(int U, int A[], int B[]) {
    for (int i=0; i<min(U,100000); ++i) {
        if (A[i]>B[i]) swap(A[i],B[i]);

        if (mp[pii(A[i],B[i])]) {
            mp[pii(A[i],B[i])]=false;

            //update A[i] with B[i]
            v.push_back(update(1,n,pos[B[i]].first,0,0,v[vv[A[i]].back().second]));
            vv[A[i]].push_back(pii(i+1,v.size()-1));
/*
            //update B[i] with A[i]
            v.push_back(update(1,n,pos[A[i]].first,0,0,v[vv[B[i]].back().second]));
            vv[B[i]].push_back(pii(i+1,v.size()-1)); */

        } else {
            mp[pii(A[i],B[i])]=true;

            //update A[i] with B[i]
            v.push_back(update(1,n,pos[B[i]].first,pos[B[i]].second,1,v[vv[A[i]].back().second]));
            vv[A[i]].push_back(pii(i+1,v.size()-1));
/*
            //update B[i] with A[i]
            v.push_back(update(1,n,pos[A[i]].first,pos[A[i]].second,1,v[vv[B[i]].back().second]));
            vv[B[i]].push_back(pii(i+1,v.size()-1)); */

        }
    }

}

int question(int x, int y, int day) {
    auto itx=upper_bound(vv[x].begin(),vv[x].end(),pii(day,INT_MAX)); --itx;
    auto ity=upper_bound(vv[y].begin(),vv[y].end(),pii(day,INT_MAX)); --ity;

    if (v[(*itx).second]->cnt==0 || v[(*ity).second]->cnt==0) return 1000000000;



    return query(1,n,v[(*itx).second],v[(*ity).second],inf,-inf);
}

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