Submission #746989

#	Time	Username	Problem	Language	Result	Execution time	Memory
746989		grogu	The Potion of Great Power (CEOI20_potion)	C++14	56 / 100	3052 ms	49988 KiB

potion

#include <bits/stdc++.h>
#define ll int
#define pb push_back
#define fi first
#define sc second
#define pll pair<ll,ll>
#define endl '\n'
#define all(a) a.begin(),a.end()
#define llinf 1000000000
#define si(a) (ll)(a.size())
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}

using namespace std;
#define maxn 200005
ll n,d,m;
ll a[maxn];
void init(int N, int D, int H[]) {
	n = N;
	d = D;
	for(ll i = 1;i<=n;i++){
		a[i] = H[i-1];
	}
}
vector<pll> v[maxn];
vector<vector<ll> > w[maxn];
set<ll> s[maxn];
ll c = 50;
void curseChanges(int U, int A[], int B[]) {
    m = U;
    for(ll i = 1;i<=n;i++) w[i].pb({});
    for(ll i = 1;i<=m;i++){
        ll x = A[i-1],y = B[i-1];
        x++; y++;
        if(s[y].count(x)) s[y].erase(x);
        else s[y].insert(x);
        if(s[x].count(y)) s[x].erase(y);
        else s[x].insert(y);
        v[x].pb({i,y});
        v[y].pb({i,x});
        if(si(v[x])%c==0){
            w[x].pb({});
            for(ll z : s[x]) w[x][si(w[x])-1].pb(z);
        }
        swap(x,y);
        if(si(v[x])%c==0){
            w[x].pb({});
            for(ll z : s[x]) w[x][si(w[x])-1].pb(z);
        }
    }
}
bool cmp(ll x,ll y){return a[x]<a[y];}
vector<ll> vx,vy;

ll reshi(vector<ll> c,vector<ll> b){
    ll j = 0;
    ll ans = llinf;
    for(ll i = 0;i<si(c);i++){
        while(j<=si(b)-1&&a[b[j]]<a[c[i]]) j++;
        if(j==si(b)) break;
        ans = min(ans,a[b[j]]-a[c[i]]);
    }
    return ans;
}
bool tu[maxn];
vector<ll> get(ll x,ll j){
    ll l = 0,r = si(v[x])-1,rez = -1,mid;
    while(l<=r){
        mid = (l+r)/2;
        if(v[x][mid].fi<=j) rez = mid,l = mid+1;
        else r = mid-1;
    }
    vector<ll> ans;
    ll e = (rez+1)/c;
    for(ll z : w[x][e])  tu[z] = 1;
    for(ll i = e*c;i<=rez;i++){
        ll y = v[x][i].sc;
        tu[y]^=1;
    }
    for(ll z : w[x][e]) if(tu[z]) ans.pb(z),tu[z] = 0;
    for(ll i = e*c;i<=rez;i++){
        ll y = v[x][i].sc;
        if(tu[y]) ans.pb(y),tu[y] = 0;
    }
    for(ll x : ans) tu[x] = 0;
    return ans;
}
int question(int x, int y, int j) {
    x++; y++;
    vx.clear();
    vy.clear();
    vx = get(x,j);
    vy = get(y,j);
    sort(all(vx),cmp);
    sort(all(vy),cmp);
    return min(reshi(vx,vy),reshi(vy,vx));
}
/**
6 5 11 4
2 42 1000 54 68 234
0 1
2 0
3 4
3 5
3 5
1 3
5 3
0 5
3 0
1 3
3 5
0 3 4 26
3 0 8 0
0 5 5 1000000000
3 0 11 14
*/

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