oj.uz

답안 #746985

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
746985 2023-05-23T11:01:13 Z grogu The Potion of Great Power (CEOI20_potion) C++14
38 / 100
 3000 ms 49700 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;
}
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;
    }
    set<ll> cur;
    ll e = (rez+1)/c;
    for(ll z : w[x][e]) cur.insert(z);
    for(ll i = e*c;i<=rez;i++){
        ll y = v[x][i].sc;
        if(cur.count(y)) cur.erase(y);
        else cur.insert(y);
    }
    vector<ll> ans;
    for(ll x : cur) ans.pb(x);
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 19152 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 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 32 ms 23096 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 370 ms 49700 KB Output is correct
2 Correct 377 ms 49680 KB Output is correct
3 Correct 416 ms 28856 KB Output is correct
4 Execution timed out 3096 ms 40344 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 355 ms 49668 KB Output is correct
2 Execution timed out 3069 ms 36336 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 20872 KB Output is correct
2 Correct 231 ms 19896 KB Output is correct
3 Correct 415 ms 19792 KB Output is correct
4 Correct 2029 ms 20592 KB Output is correct
5 Correct 2161 ms 20936 KB Output is correct
6 Correct 233 ms 20432 KB Output is correct
7 Correct 1601 ms 20064 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 19152 KB Output is correct
2 Correct 12 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 32 ms 23096 KB Output is correct
6 Correct 370 ms 49700 KB Output is correct
7 Correct 377 ms 49680 KB Output is correct
8 Correct 416 ms 28856 KB Output is correct
9 Execution timed out 3096 ms 40344 KB Time limit exceeded
10 Halted 0 ms 0 KB -