oj.uz

Submission #578173

# Submission time Handle Problem Language Result Execution time Memory
578173 2022-06-16T06:46:24 Z talant117408 The Potion of Great Power (CEOI20_potion) C++17
17 / 100
 3000 ms 27748 KB 
#include <bits/stdc++.h>

#ifndef EVAL
#include "grader.cpp"
#endif

using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define long                unsigned long 
#define pb                  push_back
#define mp                  make_pair
#define all(v)              (v).begin(),(v).end()
#define rall(v)             (v).rbegin(),(v).rend()
#define lb                  lower_bound
#define ub                  upper_bound
#define sz(v)               int((v).size())
#define do_not_disturb      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                '\n'

const int N = 2e5+7;
int n, d, h[N], u, a[N], b[N];
set <int> trusted[N/2];
bool subtask4 = 0;

void init(int N, int D, int H[]) {
    n = N; d = D;
    int flag = 0;
    for (int i = 0; i < N; i++) {
        h[i] = H[i];
        flag |= h[i];
    }
    if (flag < 2) {
        subtask4 = 1;
    }
}

void curseChanges(int U, int A[], int B[]) {
    u = U;
    for (int i = 0; i < u; i++) {
        a[i] = A[i]; b[i] = B[i];
        {
            auto last = sz(trusted[a[i]]);
            trusted[a[i]].insert(b[i]);
            if (sz(trusted[a[i]]) == last) 
                trusted[a[i]].erase(trusted[a[i]].find(b[i]));
        }
        {
            auto last = sz(trusted[b[i]]);
            trusted[b[i]].insert(a[i]);
            if (sz(trusted[b[i]]) == last) 
                trusted[b[i]].erase(trusted[b[i]].find(a[i]));
        }
    }
}

int question(int x, int y, int v) {
    vector <pii> friends;
    set <int> thief = trusted[x], evil_shaman = trusted[y];
    for (int i = u-1; i >= v; i--) {
        if (a[i] == x) {
            auto last = sz(thief);
            thief.insert(b[i]);
            if (sz(thief) == last) thief.erase(thief.find(b[i]));
        }
        else if (b[i] == x) {
            auto last = sz(thief);
            thief.insert(a[i]);
            if (sz(thief) == last) thief.erase(thief.find(a[i]));
        }
        if (a[i] == y) {
            auto last = sz(evil_shaman);
            evil_shaman.insert(b[i]);
            if (sz(evil_shaman) == last) evil_shaman.erase(evil_shaman.find(b[i]));
        }
        else if (b[i] == y) {
            auto last = sz(evil_shaman);
            evil_shaman.insert(a[i]);
            if (sz(evil_shaman) == last) evil_shaman.erase(evil_shaman.find(a[i]));
        }
    }
    set <int> tt, ss;
    for (auto to : thief) tt.insert(h[to]);
    for (auto to : evil_shaman) ss.insert(h[to]);
    
    vector <int> t, s;
    for (auto to : tt) t.pb(to);
    for (auto to : ss) s.pb(to);
    int mn = 1e9;
    int last = -1;
    for (auto to : s) {
        while (last + 1 < sz(t) && t[last+1] <= to) {
            last++;
        }
        if (last > -1) {
            mn = min(mn, abs(t[last]-to));
        }
    }
    reverse(all(t));
    reverse(all(s));
    last = -1;
    for (auto to : s) {
        while (last + 1 < sz(t) && t[last+1] >= to) {
            last++;
        }
        if (last > -1) {
            mn = min(mn, abs(t[last]-to));
        }
    }
    
    
    return mn;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5072 KB Output is correct
2 Correct 5 ms 5072 KB Output is correct
3 Correct 5 ms 5072 KB Output is correct
4 Correct 17 ms 5868 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 27668 KB Output is correct
2 Correct 386 ms 27748 KB Output is correct
3 Correct 249 ms 8980 KB Output is correct
4 Execution timed out 3063 ms 17544 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3080 ms 27668 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 6204 KB Output is correct
2 Correct 767 ms 5328 KB Output is correct
3 Execution timed out 3086 ms 5280 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 5 ms 5072 KB Output is correct
3 Correct 5 ms 5072 KB Output is correct
4 Correct 5 ms 5072 KB Output is correct
5 Correct 17 ms 5868 KB Output is correct
6 Correct 410 ms 27668 KB Output is correct
7 Correct 386 ms 27748 KB Output is correct
8 Correct 249 ms 8980 KB Output is correct
9 Execution timed out 3063 ms 17544 KB Time limit exceeded
10 Halted 0 ms 0 KB -