제출 #927757

#제출 시각아이디문제언어결과실행 시간메모리
927757cadmiumskySegments (IZhO18_segments)C++17
7 / 100
5082 ms26372 KiB
#include <bits/stdc++.h> #define all(x) (x).begin(),(x).end() using namespace std; using ll = long long; using ld = long double; //#define int ll #define sz(x) ((int)(x).size()) using pii = pair<int,int>; using tii = tuple<int,int,int>; const int nmax = 2e5 + 5; pii segments[nmax]; struct Oper { int type; int a, b; int k; }; namespace Precalc { multiset<pii> actives; void rebatch(vector<Oper> opqueue) { for(auto [t, a, b, k] : opqueue) { if(t == 1) actives.insert(pii{a, b}); else if(t == 2) actives.erase(actives.find(segments[a])); } return; } struct Item { int link, sum, own; }; #warning theyre out here saying ca daca le tii in map direct e O(N) toata chestia #warning poate e doar Bmax sau ceva (700) (pt MLE sau cv) set<pii> fwrpoz; set<pii> bckwpoz; int freq[nmax]; Item fwr[nmax], bckw[nmax]; pii atrf[nmax], atrb[nmax]; map<int, int> norm_Ks; vector<int> currKs; int n; void contextualize(vector<int> Ks) { norm_Ks.clear(); for(auto x : Ks) norm_Ks[x]; int ptrnrm = 0; for(auto &[a, b] : norm_Ks) b = ptrnrm++; fwrpoz.clear(), bckwpoz.clear(); for(auto x : Ks) freq[norm_Ks[x]] = 0; { // forward links map<pii, int> nrm; for(auto [a, b] : actives) { int k = b - a + 1; if(k < Ks[0]) continue; nrm[pii{a, b}]; } vector<int> counter_app(sz(Ks)); n = 0; for(auto &[a, b] : nrm) b = ++n, atrf[b] = a, fwr[b].sum = fwr[b].own = 0; for(auto [a, b] : actives) fwr[nrm[pii{a, b}]].own++; map<int, int> for_links; for(int i = n, atrcoef = sz(Ks) - 1; i > 0; atrcoef = (atrcoef == 0? sz(Ks) - 1 : atrcoef - 1), i--) { auto [a, b] = atrf[i]; int poz = distance(begin(Ks), prev(upper_bound(all(Ks), b - a + 1))); counter_app[poz] += fwr[i].own; fwr[i].link = atrcoef; fwr[i].sum = counter_app[atrcoef]; fwrpoz.emplace(pii{a, i}); //cerr << a << ' ' << b << '\t' << fwr[i].link << ' ' << ; } } // ---- { // backward links auto cmp = [](const pii& a, const pii& b) -> bool { return a.second < b.second || (a.second == b.second && a.first < b.first); }; map<pii, int, decltype(cmp)> nrm(cmp); for(auto [a, b] : actives) { int k = b - a + 1; if(k < Ks[0]) continue; nrm[pii{a, b}]; } vector<int> counter_app(sz(Ks)); n = 0; for(auto &[a, b] : nrm) b = ++n, atrb[b] = a, bckw[b].sum = bckw[b].own = 0; for(auto [a, b] : actives) bckw[nrm[pii{a, b}]].own++; map<int, int> for_links; for(int i = 1, atrcoef = sz(Ks) - 1; i <= n; atrcoef = (atrcoef == 0? sz(Ks) - 1 : atrcoef - 1), i++) { auto [a, b] = atrb[i]; int poz = distance(begin(Ks), prev(upper_bound(all(Ks), b - a + 1))); counter_app[poz] += bckw[i].own; bckw[i].link = atrcoef; bckw[i].sum = counter_app[atrcoef]; bckwpoz.emplace(pii{b, i}); } } for(auto [a, b] : actives) { int k = b - a + 1; if(k < Ks[0]) continue; freq[distance(begin(Ks), prev(upper_bound(all(Ks), k)))]++; } for(int i = sz(Ks) - 2; i >= 0; i--) freq[i] += freq[i + 1]; currKs = move(Ks); } int query_K(int k) { return freq[norm_Ks[k]]; } int query_L(int L, int k) { k = norm_Ks[k]; auto it = bckwpoz.upper_bound(pii{L + 1, - 1}); if(it == bckwpoz.begin()) return 0; int poz = prev(it) -> second; int rez = 0; while(k < sz(currKs) && poz > 0) { if(bckw[poz].link == k) { rez += bckw[poz].sum; k++; } if(k < sz(currKs) && currKs[k] <= atrb[poz].second - atrb[poz].first + 1) rez += bckw[poz].own; poz--; } return rez; } int query_R(int R, int k) { k = norm_Ks[k]; auto it = fwrpoz.upper_bound(pii{R, - 1}); if(it == fwrpoz.end()) return 0; int poz = it -> second; int rez = 0; while(k < sz(currKs) && poz <= n) { if(fwr[poz].link == k) { rez += fwr[poz].sum; k++; } if(k < sz(currKs) && currKs[k] <= atrf[poz].second - atrf[poz].first + 1) rez += fwr[poz].own; poz++; } return rez; } } //#error in loc sa ai pozitii care corespund unor segmente bune, doar pune suma partiala a alora congruenti cu (-pozitia) mod sz(Ks) int segmpoz = 1; int unitValue(int l, int r, int a, int b, int k) { return min(r, b) - max(l, a) + 1 >= k; } signed main() { cin.tie(0) -> sync_with_stdio(0); int n, t_offline; cin >> n >> t_offline; const int idealBuck = min(5., ceil(sqrt(n * log2(n)))); const ll worstInner = (ll)ceil(idealBuck / 2) * ceil(idealBuck / 2) + 5; vector<Oper> operation_queue; int lastans = 0; auto flush_queue = [&]() { vector<int> Ks; for(auto [t, a, b, k] : operation_queue) if(t == 3) Ks.emplace_back(k); if(sz(Ks) == 0) return; sort(all(Ks)); Ks.erase(unique(all(Ks)), Ks.end()); Precalc::contextualize(Ks); for(int i = 0; i < sz(operation_queue); i++) { auto &[ti, ai, bi, ki] = operation_queue[i]; if(ti == 1 || ti == 3) { ai = ai ^ (t_offline * lastans); bi = bi ^ (t_offline * lastans); if(ai > bi) swap(ai, bi); } if(ti == 1) segments[segmpoz++] = pii{ai, bi}; if(ti == 3) { if(bi - ai + 1 < ki) { lastans = 0; } else { int rez = Precalc::query_K(ki) - Precalc::query_R(bi - ki + 1 + 1, ki) - Precalc::query_L(ai + ki - 1 - 1, ki); for(int j = i - 1; j >= 0; j--) { auto &[tj, aj, bj, kj] = operation_queue[j]; if(tj == 3) continue; else if(tj == 2) rez -= unitValue(ai, bi, segments[aj].first, segments[aj].second, ki); else rez += unitValue(ai, bi, aj, bj, ki); } lastans = rez; } cout << lastans << '\n'; } } Precalc::rebatch(operation_queue); operation_queue.clear(); }; int cnt[2] = {1, 0}; for(int t, a, b, k, tc = 0; tc < n; tc++) { cin >> t; if(t == 1) { cin >> a >> b; operation_queue.emplace_back(Oper{t, a, b, -1}); cnt[0]++; } if(t == 2) { cin >> a; operation_queue.emplace_back(Oper{t, a, -1, -1}); cnt[0]++; } if(t == 3) { cin >> a >> b >> k; operation_queue.emplace_back(Oper{t, a, b, k}); cnt[1]++; } if(tc == n - 1 || sz(operation_queue) >= idealBuck) { flush_queue(); cnt[0] = 1; cnt[1] = 0; } } return 0; } /** Anul asta nu se da centroid -- Rugaciunile mele */

컴파일 시 표준 에러 (stderr) 메시지

segments.cpp:42:4: warning: #warning theyre out here saying ca daca le tii in map direct e O(N) toata chestia [-Wcpp]
   42 |   #warning theyre out here saying ca daca le tii in map direct e O(N) toata chestia
      |    ^~~~~~~
segments.cpp:43:4: warning: #warning poate e doar Bmax sau ceva (700) (pt MLE sau cv) [-Wcpp]
   43 |   #warning poate e doar Bmax sau ceva (700) (pt MLE sau cv)
      |    ^~~~~~~
segments.cpp: In function 'int main()':
segments.cpp:197:12: warning: unused variable 'worstInner' [-Wunused-variable]
  197 |   const ll worstInner = (ll)ceil(idealBuck / 2) * ceil(idealBuck / 2) + 5;
      |            ^~~~~~~~~~
#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...