oj.uz

Submission #349235

# Submission time Handle Problem Language Result Execution time Memory
349235 2021-01-17T07:30:51 Z dolphingarlic The Potion of Great Power (CEOI20_potion) C++14
100 / 100
 1827 ms 59500 KB 
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9, C = 20;

int H[100000];
bool odd[100000];
vector<int> u_times[100000];
vector<vector<int>> trust[100000];
struct cmp {
    bool operator()(pair<int, int> a, pair<int, int> b) const {
        return tie(H[a.second], a.first) < tie(H[b.second], b.first);
    }
};
vector<set<pair<int, int>, cmp>> updates[100000];

void init(int N, int D, int H[]) {
    for (int i = 0; i < N; i++) {
        trust[i].push_back({});
        updates[i].push_back({});
        u_times[i].push_back(0);
        ::H[i] = H[i];
    }
}

vector<int> playback(int s, int t) {
    int ub = upper_bound(u_times[s].begin(), u_times[s].end(), t) - u_times[s].begin() - 1;
    vector<int> orig = trust[s][ub];
    set<pair<int, int>, cmp> upd = updates[s][ub];
    for (int i : orig) odd[i] ^= 1;
    for (pair<int, int> i : upd) {
        if (i.first >= t) continue;
        odd[i.second] ^= 1;
    }
    vector<int> ret1, ret2;
    for (int i : orig) if (odd[i]) ret1.push_back(i), odd[i] = 0;
    for (pair<int, int> i : upd) {
        if (i.first >= t) continue;
        if (odd[i.second]) ret2.push_back(i.second), odd[i.second] = 0;
    }
    vector<int> mrg;
    int ptr1 = 0, ptr2 = 0;
    while (ptr1 < ret1.size() && ptr2 < ret2.size()) {
        if (H[ret1[ptr1]] < H[ret2[ptr2]]) mrg.push_back(ret1[ptr1++]);
        else mrg.push_back(ret2[ptr2++]);
    }
    while (ptr1 < ret1.size()) mrg.push_back(ret1[ptr1++]);
    while (ptr2 < ret2.size()) mrg.push_back(ret2[ptr2++]);
    return mrg;
}

void curseChanges(int U, int A[], int B[]) {
    for (int i = 0; i < U; i++) {
        updates[A[i]].back().insert({i, B[i]});
        updates[B[i]].back().insert({i, A[i]});
        if (updates[A[i]].back().size() == C) {
            trust[A[i]].push_back(playback(A[i], i + 1));
            updates[A[i]].push_back({});
            u_times[A[i]].push_back(i + 1);
        }
        if (updates[B[i]].back().size() == C) {
            trust[B[i]].push_back(playback(B[i], i + 1));
            updates[B[i]].push_back({});
            u_times[B[i]].push_back(i + 1);
        }
    }
}

int question(int x, int y, int v) {
    vector<int> sx = playback(x, v);
    vector<int> sy = playback(y, v);
    int ans = INF;
    for (int xptr = 0, yptr = 0; xptr != sx.size() && yptr != sy.size();) {
        ans = min(ans, abs(H[sx[xptr]] - H[sy[yptr]]));
        if (H[sx[xptr]] <= H[sy[yptr]]) xptr++;
        else yptr++;
    }
    return ans;
}

Compilation message

potion.cpp: In function 'std::vector<int> playback(int, int)':
potion.cpp:43:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     while (ptr1 < ret1.size() && ptr2 < ret2.size()) {
      |            ~~~~~^~~~~~~~~~~~~
potion.cpp:43:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     while (ptr1 < ret1.size() && ptr2 < ret2.size()) {
      |                                  ~~~~~^~~~~~~~~~~~~
potion.cpp:47:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     while (ptr1 < ret1.size()) mrg.push_back(ret1[ptr1++]);
      |            ~~~~~^~~~~~~~~~~~~
potion.cpp:48:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     while (ptr2 < ret2.size()) mrg.push_back(ret2[ptr2++]);
      |            ~~~~~^~~~~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:73:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for (int xptr = 0, yptr = 0; xptr != sx.size() && yptr != sy.size();) {
      |                                  ~~~~~^~~~~~~~~~~~
potion.cpp:73:60: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for (int xptr = 0, yptr = 0; xptr != sx.size() && yptr != sy.size();) {
      |                                                       ~~~~~^~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7404 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7660 KB Output is correct
2 Correct 8 ms 7660 KB Output is correct
3 Correct 7 ms 7660 KB Output is correct
4 Correct 52 ms 20972 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 41196 KB Output is correct
2 Correct 482 ms 41196 KB Output is correct
3 Correct 464 ms 44396 KB Output is correct
4 Correct 950 ms 44908 KB Output is correct
5 Correct 744 ms 33644 KB Output is correct
6 Correct 1593 ms 59500 KB Output is correct
7 Correct 754 ms 44524 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 472 ms 41196 KB Output is correct
2 Correct 1327 ms 59372 KB Output is correct
3 Correct 1024 ms 51052 KB Output is correct
4 Correct 1463 ms 59372 KB Output is correct
5 Correct 553 ms 42676 KB Output is correct
6 Correct 1593 ms 59484 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 9708 KB Output is correct
2 Correct 246 ms 9836 KB Output is correct
3 Correct 277 ms 9836 KB Output is correct
4 Correct 559 ms 10220 KB Output is correct
5 Correct 535 ms 10092 KB Output is correct
6 Correct 228 ms 8812 KB Output is correct
7 Correct 502 ms 10092 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7404 KB Output is correct
2 Correct 8 ms 7660 KB Output is correct
3 Correct 8 ms 7660 KB Output is correct
4 Correct 7 ms 7660 KB Output is correct
5 Correct 52 ms 20972 KB Output is correct
6 Correct 516 ms 41196 KB Output is correct
7 Correct 482 ms 41196 KB Output is correct
8 Correct 464 ms 44396 KB Output is correct
9 Correct 950 ms 44908 KB Output is correct
10 Correct 744 ms 33644 KB Output is correct
11 Correct 1593 ms 59500 KB Output is correct
12 Correct 754 ms 44524 KB Output is correct
13 Correct 472 ms 41196 KB Output is correct
14 Correct 1327 ms 59372 KB Output is correct
15 Correct 1024 ms 51052 KB Output is correct
16 Correct 1463 ms 59372 KB Output is correct
17 Correct 553 ms 42676 KB Output is correct
18 Correct 1593 ms 59484 KB Output is correct
19 Correct 78 ms 9708 KB Output is correct
20 Correct 246 ms 9836 KB Output is correct
21 Correct 277 ms 9836 KB Output is correct
22 Correct 559 ms 10220 KB Output is correct
23 Correct 535 ms 10092 KB Output is correct
24 Correct 228 ms 8812 KB Output is correct
25 Correct 502 ms 10092 KB Output is correct
26 Correct 802 ms 48748 KB Output is correct
27 Correct 1149 ms 51052 KB Output is correct
28 Correct 1192 ms 49900 KB Output is correct
29 Correct 1101 ms 44908 KB Output is correct
30 Correct 1827 ms 59372 KB Output is correct
31 Correct 1565 ms 59500 KB Output is correct
32 Correct 1720 ms 59488 KB Output is correct