oj.uz

Submission #746989

# Submission time Handle Problem Language Result Execution time Memory
746989 2023-05-23T11:14:51 Z grogu The Potion of Great Power (CEOI20_potion) C++14
56 / 100
 3000 ms 49988 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19024 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19280 KB Output is correct
2 Correct 11 ms 19280 KB Output is correct
3 Correct 12 ms 19280 KB Output is correct
4 Correct 28 ms 23244 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 49984 KB Output is correct
2 Correct 360 ms 49732 KB Output is correct
3 Correct 223 ms 28964 KB Output is correct
4 Correct 1826 ms 40332 KB Output is correct
5 Correct 615 ms 45240 KB Output is correct
6 Execution timed out 3052 ms 42212 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 49740 KB Output is correct
2 Correct 1467 ms 36228 KB Output is correct
3 Correct 919 ms 39236 KB Output is correct
4 Correct 1593 ms 42448 KB Output is correct
5 Correct 461 ms 49988 KB Output is correct
6 Correct 1769 ms 42724 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 20828 KB Output is correct
2 Correct 119 ms 19888 KB Output is correct
3 Correct 184 ms 19908 KB Output is correct
4 Correct 988 ms 20564 KB Output is correct
5 Correct 1022 ms 20936 KB Output is correct
6 Correct 123 ms 20304 KB Output is correct
7 Correct 818 ms 20084 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19024 KB Output is correct
2 Correct 10 ms 19280 KB Output is correct
3 Correct 11 ms 19280 KB Output is correct
4 Correct 12 ms 19280 KB Output is correct
5 Correct 28 ms 23244 KB Output is correct
6 Correct 359 ms 49984 KB Output is correct
7 Correct 360 ms 49732 KB Output is correct
8 Correct 223 ms 28964 KB Output is correct
9 Correct 1826 ms 40332 KB Output is correct
10 Correct 615 ms 45240 KB Output is correct
11 Execution timed out 3052 ms 42212 KB Time limit exceeded
12 Halted 0 ms 0 KB -