Submission #972532

#TimeUsernameProblemLanguageResultExecution timeMemory
972532RaresFelixThe Potion of Great Power (CEOI20_potion)C++17
100 / 100
2292 ms31272 KiB
#include <bits/stdc++.h> using namespace std; using vi = vector<int>; using ii = pair<int, int>; const int MN = 100000; int n; int H0[MN]; vector<pair<int, int> > Op[MN]; vi SnapId[MN]; vi Mare[400000]; int pma = 0; void init(int N, int D, int H[]) { n = N; for(int i = 0; i < n; ++i) H0[i] = H[i]; } int rad = 50; void curseChanges(int U, int A[], int B[]) { for(int i = 0; i < U; ++i) { Op[A[i]].push_back({i + 1, B[i]}); Op[B[i]].push_back({i + 1, A[i]}); } set<int> S; for(int i = 0; i < n; ++i) { S.clear(); SnapId[i].push_back(pma); ++pma; for(int j = 0; j < Op[i].size(); ++j) { if(j % rad == 0 && j) { SnapId[i].push_back(pma); Mare[pma].reserve(S.size()); for(auto it : S) Mare[pma].push_back(it); ++pma; } auto [t, v] = Op[i][j]; if(S.count(v)) S.erase(v); else S.insert(v); } } } const int INF = 1e9; vi get(int x, int v) { int st = 0, dr = int(Op[x].size()) - 1, mij; if(Op[x].empty() || Op[x][0].first > v) return vi(); while(st < dr) { mij = (st + dr + 1) / 2; if(Op[x][mij].first > v) dr = mij - 1; // e ok asa? else st = mij; } unordered_set<int> Fr; for(int i = st / rad * rad; i <= st; ++i) { auto [t, v] = Op[x][i]; if(Fr.count(v)) Fr.erase(v); else Fr.insert(v); } vi Re; for(auto it : Mare[SnapId[x][st / rad]]) { if(!Fr.count(it)) Re.push_back(H0[it]); else Fr.erase(it); } for(auto v : Fr) Re.push_back(H0[v]); sort(Re.begin(), Re.end()); return Re; } int question(int x, int y, int v) { auto VA = get(x, v), VB = get(y, v); int pa = 0, pb = 0; int re = INF; while(pa < VA.size() && pb < VB.size()) { re = min(re, abs(VA[pa] - VB[pb])); if(VA[pa] < VB[pb]) ++pa; else ++pb; } return re; }

Compilation message (stderr)

potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:35:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for(int j = 0; j < Op[i].size(); ++j) {
      |                        ~~^~~~~~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:79:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     while(pa < VA.size() && pb < VB.size()) {
      |           ~~~^~~~~~~~~~~
potion.cpp:79:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     while(pa < VA.size() && pb < VB.size()) {
      |                             ~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...