Submission #1189089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189089		Warinchai	The Potion of Great Power (CEOI20_potion)	C++20	17 / 100	3098 ms	18440 KiB

potion

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

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

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

void curseChanges(int U, int A[], int B[]) {
    for(int i=0;i<U;i++){
        op[A[i]].push_back({B[i],i+1});
        op[B[i]].push_back({A[i],i+1});
    }
}

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;
}

vector<int> small(int x,int v){
    //cerr<<"x,v:"<<x<<" "<<v<<"\n";
    map<pair<int,int>,int>mp;
    for(auto [id,day]:op[x]){
        if(day>v)break;
        mp[{h[id],id}]^=1;
    }
    vector<int>temp;
    for(auto x:mp){
        if(x.second==1){
            temp.push_back(x.first.first);
            //cerr<<x.first.second<<" ";
        }
    }
    //cerr<<"\n";
    return temp;
}

int question(int x, int y, int v) {
    if(v==0)return inf;
    return fans(small(x,v),small(y,v));
}

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