Submission #349208

#	Time	Username	Problem	Language	Result	Execution time	Memory
349208		dolphingarlic	The Potion of Great Power (CEOI20_potion)	C++14	38 / 100	3089 ms	40940 KiB

potion

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9, C = 50;

int H[100000];
bool odd[100000];
map<int, vector<int>> trust[100000];
map<int, vector<pair<int, int>>> updates[100000];

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

vector<int> playback(int shaman, int time) {
    vector<int> v = prev(trust[shaman].upper_bound(time))->second;
    vector<pair<int, int>> u = prev(updates[shaman].upper_bound(time))->second;
    for (int i : v) odd[i] ^= 1;
    for (pair<int, int> i : u) {
        if (i.first >= time) break;
        odd[i.second] ^= 1;
    }
    vector<int> ret;
    for (int i : v) if (odd[i]) ret.push_back(i), odd[i] = 0;
    for (pair<int, int> i : u) {
        if (i.first >= time) break;
        if (odd[i.second]) ret.push_back(i.second), odd[i.second] = 0;
    }
    return ret;
}

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

bool cmp(int a, int b) { return tie(H[a], a) < tie(H[b], b); }

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

Compilation message (stderr)

potion.cpp: In function 'int question(int, int, int)':
potion.cpp:59:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int xptr = 0, yptr = 0; xptr != sx.size() && yptr != sy.size(); xptr++) {
      |                                  ~~~~~^~~~~~~~~~~~
potion.cpp:59:60: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int xptr = 0, yptr = 0; xptr != sx.size() && yptr != sy.size(); xptr++) {
      |                                                       ~~~~~^~~~~~~~~~~~
potion.cpp:60:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         while (yptr != sy.size() - 1 && H[sy[yptr + 1]] < H[sx[xptr]]) yptr++;
      |                ~~~~~^~~~~~~~~~~~~~~~
potion.cpp:62:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         if (yptr != sy.size() - 1) ans = min(ans, abs(H[sx[xptr]] - H[sy[yptr + 1]]));
      |             ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 17 / 17
• Subtask 3: 0 / 14
• Subtask 4: 0 / 18
• Subtask 5: 21 / 21
• Subtask 6: 0 / 30