Submission #644556

#TimeUsernameProblemLanguageResultExecution timeMemory
644556Markomafko972Abracadabra (CEOI22_abracadabra)C++14
35 / 100
466 ms119000 KiB
#include <bits/stdc++.h> #define X first #define Y second #define pb push_back #define pii pair<int, int> typedef long long ll; using namespace std; const int MOD = 1e9 + 7; const ll INF = 1e18; const int OFF = (1 << 20); int n, q, koji = 0, vri, w; int a[200005]; int veci[200005]; int gdje[200005]; stack< pair<int, int> > st; set< pair< pair<int, int>, pair<int, int> > > s; set< pair< pair<int, int>, pair<int, int> > > :: iterator it; vector< pair< pair<int, int>, pair<int, int> > > v; vector< pair<int, int> > kad[200005]; int sol[1000005]; int t[2*OFF+5]; void update(int x, int y) { x += OFF; t[x] = y; x /= 2; while (x > 0) { t[x] = t[x*2] + t[x*2+1]; x /= 2; } } void ispis() { int pot = 2; for (int i = 1; i < 2*OFF; i++) { if (i == pot) { cout << endl; pot *= 2; } cout << t[i] << " "; } cout << endl; } int query(int x, int y) { if (x >= OFF) { int prva = v[x-OFF].Y.X; return a[prva+y-1]; } if (t[x*2] >= y) return query(x*2, y); else return query(x*2+1, y-t[x*2]); } int main () { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> q; for (int i = 0; i < n; i++) { cin >> a[i]; veci[i] = n; } for (int i = n-1; i >= 0; i--) { while (st.size() > 0 && st.top().X <= a[i]) { st.pop(); } if (st.size() > 0) veci[i] = st.top().Y; st.push({a[i], i}); } int pos = 0; while (pos < n) { s.insert({{a[pos], koji}, {pos, veci[pos]-1}}); v.push_back({{a[pos], koji}, {pos, veci[pos]-1}}); koji++; pos = veci[pos]; } int d = n; for (int i = 0; i < n; i++) { while (1) { it = s.end(); it--; if (d+(*it).Y.X-(*it).Y.Y-1 < n/2) break; else { d = d+(*it).Y.X-(*it).Y.Y-1; s.erase(it); } } //cout << i << ": " << d << endl; if (d > n/2) { it = s.end(); it--; pos = (*it).Y.X; int kr = (*it).Y.Y; d -= (kr-pos+1); s.erase(it); int dod = n/2 - d; s.insert({{a[pos], koji}, {pos, pos+dod-1}}); v.push_back({{a[pos], koji}, {pos, pos+dod-1}}); d += dod; //cout << "novi: " << pos << " " << pos+dod-1 << endl; koji++; pos += dod; while (pos <= kr) { s.insert({{a[pos], koji}, {pos, min(veci[pos]-1, kr)}}); v.push_back({{a[pos], koji}, {pos, min(veci[pos]-1, kr)}}); d += min(veci[pos]-1, kr) - pos + 1; //cout << "novi: " << pos << " " << min(veci[pos]-1, kr) << endl; koji++; pos = veci[pos]; } } } sort(v.begin(), v.end()); for (int i = 0; i < v.size(); i++) { gdje[v[i].X.Y] = i; //cout << v[i].Y.X << " " << v[i].Y.Y << " | " << v[i].X.X << endl; } // gotov precompute s.clear(); pos = 0; koji = 0; while (pos < n) { s.insert({{a[pos], koji}, {pos, veci[pos]-1}}); update(gdje[koji], veci[pos]-pos); //ispis(); koji++; pos = veci[pos]; } for (int i = 0; i < q; i++) { cin >> vri >> w; kad[min(n, vri)].push_back({w, i}); } d = n; for (int i = 0; i <= n; i++) { //ispis(); for (int j = 0; j < (int)kad[i].size(); j++) { int trenrj = query(1, kad[i][j].X); sol[kad[i][j].Y] = trenrj; } if (i == n) break; while (1) { it = s.end(); it--; if (d+(*it).Y.X-(*it).Y.Y-1 < n/2) break; else { d = d+(*it).Y.X-(*it).Y.Y-1; //update(gdje[(*it).X.Y], 0); s.erase(it); } } if (d > n/2) { it = s.end(); it--; pos = (*it).Y.X; int kr = (*it).Y.Y; d -= (kr-pos+1); update(gdje[(*it).X.Y], 0); s.erase(it); int dod = n/2 - d; s.insert({{a[pos], koji}, {pos, pos+dod-1}}); update(gdje[koji], dod); d += dod; koji++; pos += dod; while (pos <= kr) { s.insert({{a[pos], koji}, {pos, min(veci[pos]-1, kr)}}); update(gdje[koji], min(veci[pos]-1, kr)-pos+1); d += min(veci[pos]-1, kr) - pos + 1; koji++; pos = veci[pos]; } } } for (int i = 0; i < q; i++) cout << sol[i] << "\n"; return 0; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:130:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |  for (int i = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...