oj.uz

Submission #746991

# Submission time Handle Problem Language Result Execution time Memory
746991 2023-05-23T11:16:03 Z grogu The Potion of Great Power (CEOI20_potion) C++14
56 / 100
 3000 ms 50040 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 = 60;
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 13 ms 19024 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19208 KB Output is correct
2 Correct 11 ms 19280 KB Output is correct
3 Correct 11 ms 19280 KB Output is correct
4 Correct 29 ms 23312 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 49936 KB Output is correct
2 Correct 379 ms 49752 KB Output is correct
3 Correct 211 ms 28988 KB Output is correct
4 Correct 1926 ms 39156 KB Output is correct
5 Correct 586 ms 45076 KB Output is correct
6 Execution timed out 3057 ms 41040 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 49808 KB Output is correct
2 Correct 1422 ms 35208 KB Output is correct
3 Correct 978 ms 38428 KB Output is correct
4 Correct 1621 ms 41228 KB Output is correct
5 Correct 456 ms 50040 KB Output is correct
6 Correct 1892 ms 41428 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 20816 KB Output is correct
2 Correct 111 ms 19924 KB Output is correct
3 Correct 182 ms 19792 KB Output is correct
4 Correct 1000 ms 20552 KB Output is correct
5 Correct 1016 ms 20924 KB Output is correct
6 Correct 130 ms 20348 KB Output is correct
7 Correct 833 ms 20060 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19024 KB Output is correct
2 Correct 12 ms 19208 KB Output is correct
3 Correct 11 ms 19280 KB Output is correct
4 Correct 11 ms 19280 KB Output is correct
5 Correct 29 ms 23312 KB Output is correct
6 Correct 363 ms 49936 KB Output is correct
7 Correct 379 ms 49752 KB Output is correct
8 Correct 211 ms 28988 KB Output is correct
9 Correct 1926 ms 39156 KB Output is correct
10 Correct 586 ms 45076 KB Output is correct
11 Execution timed out 3057 ms 41040 KB Time limit exceeded
12 Halted 0 ms 0 KB -