oj.uz

Submission #746999

# Submission time Handle Problem Language Result Execution time Memory
746999 2023-05-23T11:26:22 Z grogu The Potion of Great Power (CEOI20_potion) C++14
56 / 100
 3000 ms 24668 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];
ll c = 75;
bool tu[maxn];
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++;
        v[x].pb({i,y});
        v[y].pb({i,x});
        if(si(v[x])%c==0){
            vector<ll> ans;
            ll e = si(w[x])-1;
            for(ll z : w[x][e]) tu[z] = 1;
            for(ll i = e*c;i<si(v[x]);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<si(v[x]);i++){
                ll y = v[x][i].sc;
                if(tu[y]) ans.pb(y),tu[y] = 0;
            }
            for(ll x : ans) tu[x] = 0;
            w[x].pb(ans);
        }
        swap(x,y);
        if(si(v[x])%c==0){
            vector<ll> ans;
            ll e = si(w[x])-1;
            for(ll z : w[x][e]) tu[z] = 1;
            for(ll i = e*c;i<si(v[x]);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<si(v[x]);i++){
                ll y = v[x][i].sc;
                if(tu[y]) ans.pb(y),tu[y] = 0;
            }
            for(ll x : ans) tu[x] = 0;
            w[x].pb(ans);
        }
    }
}
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;
}
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 7 ms 9680 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9720 KB Output is correct
2 Correct 6 ms 9680 KB Output is correct
3 Correct 6 ms 9680 KB Output is correct
4 Correct 24 ms 13704 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 21492 KB Output is correct
2 Correct 195 ms 21476 KB Output is correct
3 Correct 200 ms 19324 KB Output is correct
4 Correct 1707 ms 18448 KB Output is correct
5 Correct 377 ms 17124 KB Output is correct
6 Execution timed out 3071 ms 24336 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 21412 KB Output is correct
2 Correct 1311 ms 24316 KB Output is correct
3 Correct 733 ms 22652 KB Output is correct
4 Correct 1435 ms 24492 KB Output is correct
5 Correct 276 ms 21804 KB Output is correct
6 Correct 1520 ms 24668 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 10448 KB Output is correct
2 Correct 91 ms 10448 KB Output is correct
3 Correct 187 ms 10340 KB Output is correct
4 Correct 999 ms 10680 KB Output is correct
5 Correct 990 ms 10712 KB Output is correct
6 Correct 122 ms 10064 KB Output is correct
7 Correct 814 ms 10452 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9680 KB Output is correct
2 Correct 8 ms 9720 KB Output is correct
3 Correct 6 ms 9680 KB Output is correct
4 Correct 6 ms 9680 KB Output is correct
5 Correct 24 ms 13704 KB Output is correct
6 Correct 176 ms 21492 KB Output is correct
7 Correct 195 ms 21476 KB Output is correct
8 Correct 200 ms 19324 KB Output is correct
9 Correct 1707 ms 18448 KB Output is correct
10 Correct 377 ms 17124 KB Output is correct
11 Execution timed out 3071 ms 24336 KB Time limit exceeded
12 Halted 0 ms 0 KB -