oj.uz

Submission #638358

# Submission time Handle Problem Language Result Execution time Memory
638358 2022-09-05T15:41:05 Z jiahng The Potion of Great Power (CEOI20_potion) C++14
38 / 100
 1859 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
//#define int ll
typedef pair<int32_t, int32_t> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 200010
#define INF (ll)1e9
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;

int H[maxn], N, D;
unordered_set <int> st[maxn][2];
vpi updates[maxn];
void init(int N, int D, int H[]) {
    ::N = N; ::D = D;
    FOR(i,0,N-1) ::H[i] = H[i];
    FOR(i,0,N-1) updates[i].pb(pi(-1,-1));
}

void curseChanges(int U, int A[], int B[]) {
    FOR(i,0,U-1){
        if (updates[A[i]].back() != pi(-1,-1)) aFOR(j, st[updates[A[i]].back().f][updates[A[i]].back().s]) st[i][0].insert(j);
        if (updates[B[i]].back() != pi(-1,-1)) aFOR(j, st[updates[B[i]].back().f][updates[B[i]].back().s]) st[i][1].insert(j);

        if (st[i][0].find(B[i]) == st[i][0].end()) st[i][0].insert(B[i]);
        else st[i][0].erase(B[i]);

        if (st[i][1].find(A[i]) == st[i][1].end()) st[i][1].insert(A[i]);
        else st[i][1].erase(A[i]);

        updates[A[i]].pb(pi(i,0)); updates[B[i]].pb(pi(i,1));
    }


}

int question(int x, int y, int v) {
    pi xidx = *(--ubd(updates[x], pi(v-1, 2)));
    pi yidx = *(--ubd(updates[y], pi(v-1, 2)));

    set <int> xst, yst;
    if (xidx.f != -1) aFOR(i, st[xidx.f][xidx.s]) xst.insert(H[i]);
    if (yidx.f != -1) aFOR(i, st[yidx.f][yidx.s]) yst.insert(H[i]);

    // xst.insert(H[x]); yst.insert(H[y]);
    int ans = INF;
    aFOR(i, xst){
        auto it = yst.lower_bound(i);
        if (it != yst.end()) ans = min(ans, *it - i);
        if (it != yst.begin()) ans = min(ans, abs(*(--it) - i));
    }
    //cout << "ASD" << ans << '\n';
    return ans;

}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 26832 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 27344 KB Output is correct
2 Correct 16 ms 27284 KB Output is correct
3 Correct 16 ms 27344 KB Output is correct
4 Correct 37 ms 31116 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 508 ms 117500 KB Output is correct
2 Correct 505 ms 117560 KB Output is correct
3 Correct 514 ms 200884 KB Output is correct
4 Runtime error 527 ms 262144 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 117604 KB Output is correct
2 Runtime error 501 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 30960 KB Output is correct
2 Correct 146 ms 35692 KB Output is correct
3 Correct 253 ms 36748 KB Output is correct
4 Correct 1859 ms 85824 KB Output is correct
5 Correct 1788 ms 72424 KB Output is correct
6 Correct 235 ms 36968 KB Output is correct
7 Correct 1468 ms 77248 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 26832 KB Output is correct
2 Correct 18 ms 27344 KB Output is correct
3 Correct 16 ms 27284 KB Output is correct
4 Correct 16 ms 27344 KB Output is correct
5 Correct 37 ms 31116 KB Output is correct
6 Correct 508 ms 117500 KB Output is correct
7 Correct 505 ms 117560 KB Output is correct
8 Correct 514 ms 200884 KB Output is correct
9 Runtime error 527 ms 262144 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -