oj.uz

답안 #578166

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
578166 2022-06-16T06:35:39 Z talant117408 The Potion of Great Power (CEOI20_potion) C++17
17 / 100
 3000 ms 27732 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]));
        }
    }
    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

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

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 5032 KB Output is correct
2 Correct 5 ms 5072 KB Output is correct
3 Correct 5 ms 5072 KB Output is correct
4 Correct 19 ms 5940 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 290 ms 27620 KB Output is correct
2 Correct 307 ms 27592 KB Output is correct
3 Correct 186 ms 8964 KB Output is correct
4 Execution timed out 3031 ms 17524 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3089 ms 27732 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 397 ms 6096 KB Output is correct
2 Correct 683 ms 5328 KB Output is correct
3 Execution timed out 3079 ms 5200 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 5 ms 5032 KB Output is correct
3 Correct 5 ms 5072 KB Output is correct
4 Correct 5 ms 5072 KB Output is correct
5 Correct 19 ms 5940 KB Output is correct
6 Correct 290 ms 27620 KB Output is correct
7 Correct 307 ms 27592 KB Output is correct
8 Correct 186 ms 8964 KB Output is correct
9 Execution timed out 3031 ms 17524 KB Time limit exceeded
10 Halted 0 ms 0 KB -