Submission #1239098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239098		Malix	The Potion of Great Power (CEOI20_potion)	C++20	100 / 100	2857 ms	46544 KiB

potion

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) (x).begin(),(x).end()
 
ll INF=1000000000000000010;
int inf=1e9;
ll M=1e9+7;

vi h;
int n;
vector<vector<vector<pi>>> a;
vii b;
set<pi> st;

void init(int N, int D, int H[]) {
    n=N;
    h.resize(n);
    REP(i,0,n)h[i]=H[i];
    a.resize(n);
    b.resize(n);
}

void curseChanges(int U, int A[], int B[]) {
    REP(i,0,U){
        int x=A[i],y=B[i];
        if(x>y)swap(x,y);
        if(st.count({x,y})){
            REP(j,0,b[x].size())if(b[x][j]==y){
                b[x][j]=-1;
                a[x][j].PB({i,-1});
                break;
            }
            REP(j,0,b[y].size())if(b[y][j]==x){
                b[y][j]=-1;
                a[y][j].PB({i,-1});
                break;
            }
            st.erase({x,y});
        }
        else{
            bool f=1;
            REP(j,0,b[x].size())if(b[x][j]==-1){
                b[x][j]=y;
                a[x][j].PB({i,y});
                f=0;
                break;
            }
            if(f){
                b[x].PB(y);
                a[x].PB({{i,y}});
            }
            f=1;
            REP(j,0,b[y].size())if(b[y][j]==-1){
                b[y][j]=x;
                a[y][j].PB({i,x});
                f=0;
                break;
            }
            if(f){
                b[y].PB(x);
                a[y].PB({{i,x}});
            }
            st.insert({x,y});
        }
    }
}

int question(int x, int y, int v) {
    vi X,Y;
    REP(i,0,a[x].size())if(!a[x][i].empty()){
        auto it=lower_bound(all(a[x][i]),make_pair(v,-2));
        if(it==a[x][i].begin())continue;
        it--;
        if(it->S!=-1)X.PB(it->S);
    }
    REP(i,0,a[y].size())if(!a[y][i].empty()){
        auto it=lower_bound(all(a[y][i]),make_pair(v,-2));
        if(it==a[y][i].begin())continue;
        it--;
        if(it->S!=-1)Y.PB(it->S);
    }
    REP(i,0,X.size())X[i]=h[X[i]];
    REP(i,0,Y.size())Y[i]=h[Y[i]];
    sort(all(X));sort(all(Y));
    X.erase(unique(all(X)),X.end());
    Y.erase(unique(all(Y)),Y.end());
    int ans=inf;
    REP(i,0,X.size()){
        auto it=lower_bound(all(Y),X[i]);
        if(it!=Y.end())ans=min(ans,abs(*it-X[i]));
        if(it!=Y.begin()){
            it--;
            ans=min(ans,abs(*it-X[i]));
        }
    }
    return ans;
}

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