oj.uz

Submission #578158

# Submission time Handle Problem Language Result Execution time Memory
578158 2022-06-16T06:25:27 Z talant117408 The Potion of Great Power (CEOI20_potion) C++17
17 / 100
 3000 ms 4240 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];
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];
    }
}

int question(int x, int y, int v) {
    vector <pii> friends;
    set <int> thief, evil_shaman;
    for (int i = 0; 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]));
        }
    }
    for (auto to : thief) friends.pb(mp(h[to], x));
    for (auto to : evil_shaman) friends.pb(mp(h[to], y));
    int mn = 1e9;
    sort(all(friends));
    int last = -1e9;
    for (int i = 0; i < sz(friends); i++) {
        auto t = friends[i];
        if (t.second == x) last = t.first;
        else mn = min(mn, abs(t.first-last));
    }
    reverse(all(friends));
    last = -1e9;
    for (int i = 0; i < sz(friends); i++) {
        auto t = friends[i];
        if (t.second == x) last = t.first;
        else mn = min(mn, abs(t.first-last));
    }
    return mn;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 3 ms 336 KB Output is correct
4 Correct 14 ms 1048 KB Output is correct

Subtask #3
0 / 14.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 464 KB Output is correct
2 Correct 688 ms 544 KB Output is correct
3 Execution timed out 3054 ms 492 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 3 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 3 ms 336 KB Output is correct
5 Correct 14 ms 1048 KB Output is correct
6 Execution timed out 3031 ms 4240 KB Time limit exceeded
7 Halted 0 ms 0 KB -