Submission #588874

#	Time	Username	Problem	Language	Result	Execution time	Memory
588874		radal	The Potion of Great Power (CEOI20_potion)	C++17	17 / 100	3055 ms	262144 KiB

potion

#include <bits/stdc++.h>
//#pragma GCC target("sse,sse2,sse4,avx2")
//#pragma GCC optimize("unroll-loops,O2")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 2e5+10,mod = 1e9+7,inf = 1e9+10,sq = 2000;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k >>= 1;
    } 
    return z; 
}
int n,d,h[N],a[N],b[N],u;
vector<set<int> > st[N];
set<int> st1,st2;
vector<pair<int,bool> > ve;
void init(int N, int D, int H[]) {
    n = N;
    d = D;
    rep(i,0,n) h[i] = H[i];
}

void curseChanges(int U, int A[], int B[]) {
    u = U;
    rep(i,0,U){
        a[i+1] = A[i];
        b[i+1] = B[i];
        if ((i+1)%sq == 0){
            int j = (i+1)/sq;
            if (j != 1){
                rep(k,0,n) st[k].pb(st[k].back());
            }
            else{
                rep(k,0,n) st[k].resize(1);
            }
            int l = i-sq+1;
            rep(k,l,i+1){
                if (st[A[k]][j-1].find(B[k]) != st[A[k]][j-1].end()){
                    st[A[k]][j-1].erase(B[k]);
                    st[B[k]][j-1].erase(A[k]);
                }
                else{
                    st[A[k]][j-1].insert(B[k]);
                    st[B[k]][j-1].insert(A[k]);
                }
            }
        }
    }
}

int question(int x, int y, int v) {
    if (!v) return 1000000000;
    int d = 0;
    if (v >= sq){
        int j = v/sq;
        d = j*sq;
        st1 = st[x][j-1];
        st2 = st[y][j-1];
    }
    else{
        st1.clear();
        st2.clear();
    }
    rep(i,d+1,v+1){
        if (a[i] == x){
            if (st1.find(b[i]) != st1.end())
                st1.erase(b[i]);
            else
                st1.insert(b[i]);
        }
        if (a[i] == y){
            if (st2.find(b[i]) != st2.end())
                st2.erase(b[i]);
            else
                st2.insert(b[i]);
        }
        if (b[i] == x){
            if (st1.find(a[i]) != st1.end())
                st1.erase(a[i]);
            else
                st1.insert(a[i]);
        }
        if (b[i] == y){
            if (st2.find(a[i]) != st2.end())
                st2.erase(a[i]);
            else
                st2.insert(a[i]);
        }
    }
    if (st1.empty() || st2.empty()) return 1000000000;
    ve.clear();
    for (int x : st1) ve.pb({h[x],0});
    for (int x : st2) ve.pb({h[x],1});
    sort(all(ve));
    int sz = ve.size(),ans = 1000000000;
    rep(i,1,sz){
        while(i < sz && ve[i].Y == ve[i-1].Y) i++;
        if (i == sz) break;
        ans = min(ans,ve[i].X-ve[i-1].X);
    }
    return ans;
}

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