Submission #1189103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189103		Warinchai	The Potion of Great Power (CEOI20_potion)	C++20	38 / 100	977 ms	327680 KiB

potion

#include<bits/stdc++.h>
using namespace std;

int n,d,h[200005];
vector<int>have[400005];
int inf=1e9;
int prv[200005];

void init(int N, int D, int H[]) {
    n=N,d=D;
    for(int i=0;i<n;i++){
        h[i]=H[i];
    }
    for(int i=0;i<n;i++)prv[i]=-1;
}

int cnt[200005];
vector<int>ids[200005];

void curseChanges(int U, int A[], int B[]) {
    for(int i=0;i<U;i++){
        cnt[A[i]]++;cnt[B[i]]++;
        int h=0;
        int id=i*2;
        if(prv[A[i]]!=-1){
            for(auto x:have[prv[A[i]]]){
                if(x==B[i])h=1;
                else have[id].push_back(x);
            }
        }
        if(h==0)have[id].push_back(B[i]);
        prv[A[i]]=id;
        ids[A[i]].push_back(id);

        h=0,id=i*2+1;
        if(prv[B[i]]!=-1){
            for(auto x:have[prv[B[i]]]){
                if(x==A[i])h=1;
                else have[id].push_back(x);
            }
        }
        if(h==0)have[id].push_back(A[i]);
        prv[B[i]]=id;
        ids[B[i]].push_back(id);
    }
    /*for(int i=0;i<U;i++){
        int id=i*2;
        cerr<<"have:"<<id<<"\n";
        for(auto x:have[id])cerr<<x<<" ";
        cerr<<"\n";
        id=i*2+1;
        cerr<<"have:"<<id<<"\n";
        for(auto x:have[id])cerr<<x<<" ";
        cerr<<"\n";
    }*/
}

int fans(vector<int>l,vector<int>r){
    int ll=-1,rr=-1;
    int ans=inf;
    if(l.size()==0||r.size()==0)return inf;
    while(1){
        if(ll==l.size()-1&&rr==r.size()-1)break;
        if(rr==r.size()-1)while(ll+1<l.size())ans=min(ans,abs(l[ll+1]-r[rr])),ll++;
        if(ll==l.size()-1)while(rr+1<r.size())ans=min(ans,abs(r[rr+1]-l[ll])),rr++;
        if(ll==l.size()-1&&rr==r.size()-1)break;
        if(l[ll+1]<r[rr+1]){
            if(rr>=0)ans=min(ans,abs(l[ll+1]-r[rr]));
            ll++;
        }else{
            if(ll>=0)ans=min(ans,abs(r[rr+1]-l[ll]));
            rr++;
        }
    }
    return ans;
}

int question(int x, int y, int v) {
    if(v==0)return inf;
    int idl=lower_bound(ids[x].begin(),ids[x].end(),v*2)-ids[x].begin()-1;
    if(idl==-1)return inf;
    int idr=lower_bound(ids[y].begin(),ids[y].end(),v*2)-ids[y].begin()-1;
    if(idr==-1)return inf;
    idl=ids[x][idl];
    idr=ids[y][idr];
    vector<int>l=have[idl],r=have[idr];
    //cerr<<"Q:"<<x<<" "<<y<<" "<<v<<"\n";
    //cerr<<idl<<" "<<idr<<"\n";
    for(auto &x:l)x=h[x];
    for(auto &x:r)x=h[x];
    sort(l.begin(),l.end());
    sort(r.begin(),r.end());
    return fans(l,r);
}

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