Submission #160186

#TimeUsernameProblemLanguageResultExecution timeMemory
160186pink_bitternSegments (IZhO18_segments)C++14
7 / 100
5079 ms16976 KiB
#include <bits/stdc++.h> #define pb push_back #define pll pair <ll, ll> #define MOMI using namespace std; #define mp make_pair #define pyshnapyshnakaa ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0); #pragma optimize("TKACHENKO-GORYACHENKO") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") typedef long long ll; typedef long double ld; using namespace std; const ll inf = 1e15; const ll maxn = 3e5; const ll block = 2e3; /// cnt_of_blocks // const ll block_sz = 5e3 + 10; const ll block_sz = (maxn + block - 1) / block; ll n, m, k, t; struct seg{ ll l; ll r; ll sz; ll i; }; bool operator==(seg a, seg b) { return a.i == b.i; } vector <seg> S; vector <seg> segs; vector <seg> lasts; bool cmp(seg a, seg b) { return (a.r - a.l) < (b.r - b.l); } bool cmpl(seg a, seg b) { return a.l < b.l; } bool cmpr(seg a, seg b) { return a.r < b.r; } ll LASTL[block]; ll LASTR[block]; vector <seg> R[block]; vector <seg> L[block]; set <ll> L1[block]; set <ll> R1[block]; map <ll, ll> LS[block]; map <ll, ll> RS[block]; ll MNL[block]; ll MXL[block]; ll MNR[block]; ll MXR[block]; ll IL[maxn]; ll IR[maxn]; bool used[maxn]; void buildL(ll q) { ll w; LS[q].clear(); L1[q].clear(); MNL[q] = inf; MXL[q] = -inf; for (w = 0; w < L[q].size(); w++) { MNL[q] = min(MNL[q], L[q][w].l); MXL[q] = max(MXL[q], L[q][w].l); LS[q][L[q][w].sz]++; L1[q].insert(L[q][w].sz); } ll s = 0; for (auto p : LS[q]) { LS[q][p.first] += s; s = LS[q][p.first]; } } void buildR(ll q) { ll w; MNR[q] = -inf; MXR[q] = inf; RS[q].clear(); R1[q].clear(); for (w = 0; w < R[q].size(); w++) { MNR[q] = min(MNR[q], R[q][w].r); MXR[q] = max(MXR[q], R[q][w].r); // cout << R[q][w].sz << " "; RS[q][R[q][w].sz] += 1; R1[q].insert(R[q][w].sz); } // cout << endl; ll s = 0; for (auto p : RS[q]){ RS[q][p.first] += s; s = RS[q][p.first]; } // for (auto p: RS[q]) { // cout << p.first << " " << p.second << endl; // } // cout << endl << endl; } void rebuild() { // cout << "VSEM PIZDEC " << endl << endl << endl; ll q, w; lasts.clear(); ll blocki = 0; sort(segs.begin(), segs.end(), cmpl); for (q = 0; q < block; q++) { R[q].clear(); L[q].clear(); } for (q = 0; q < segs.size(); q++) { if (used[segs[q].i]) { continue; } if (q != 0) { if (L[blocki].size() > block_sz) { blocki++; } } //cout << "BLOCKI " << blocki << " " << segs[q].l << endl; // MNL[blocki] = min(MNL[blocki], segs[q].l); // MXL[blocki] = max(MXL[blocki], segs[q].l); IL[segs[q].i] = blocki; L[blocki].pb(segs[q]); } sort(segs.begin(), segs.end(), cmpr); for (q = 0; q < segs.size(); q++) { if (used[segs[q].i]) { continue; } // cout << "NOT USED " << segs[q].i << endl; if (q != 0) { if (R[blocki].size() > block_sz) { blocki++; } } // MNR[blocki] = min(MNR[blocki], segs[q].r); // MXR[blocki] = max(MXR[blocki], segs[q].r); IR[segs[q].i] = blocki; R[blocki].pb(segs[q]); } // cout << "SZ UMOM " << R[0].size() << endl; for (q = 0; q < block; q++) { buildL(q); } for (q = 0; q < block; q++) { buildR(q); } } void add(seg a) { lasts.pb(a); S.pb(a); segs.pb(a); IL[a.i] = IR[a.i] = -1; } void del(seg b) { // cout << b.i << " I" << endl; ll il = IL[b.i], ir = IR[b.i]; used[b.i] = 1; if (il == -1) { return; } // cout << il << " " << ir << endl; // ll sz = R[ir].size(); //cout << "IR " << ir << " " << sz << endl; L[il].erase(find(L[il].begin(), L[il].end(), b)); R[ir].erase(find(R[ir].begin(), R[ir].end(), b)); buildL(il); buildR(ir); // cout << "NEW SZ " << R[ir].size() << endl << endl; // if (R[ir].size() == sz) { // cout << "UH SYKA" << endl; // } } ll slowL(ll i, ll x, ll l) { //cout << "SLOW CARS" << endl; ll q; ll ans = 0; for (q = 0; q < L[i].size(); q++) { if (L[i][q].l >= l && L[i][q].sz >= x) { ans++; } } return ans; } ll slowR(ll i, ll x, ll r) { ll q; ll ans = 0; for (q = 0; q < R[i].size(); q++) { if (R[i][q].r <= r && R[i][q].sz >= x) { ans++; } } return ans; } ll fastL(ll i, ll x) { auto j = L1[i].lower_bound(x); if (j == L1[i].begin()) { return L[i].size(); } // for (ll q = 0; q < L[i].size(); q++) { // cout << L[i][q].sz << " "; // } // cout << endl; // cout << endl << endl; j--; ll ind = (*j); ll dans = LS[i][ind]; ll ans = L[i].size() - dans; //cout << ans << endl; return ans; } ll fastR(ll i, ll x) { auto j = R1[i].lower_bound(x); if (j == R1[i].begin()) { return R[i].size(); } // for (ll q = 0; q < L[i].size(); q++) { // cout << L[i][q].sz << " "; // } // cout << endl; // cout << endl << endl; j--; ll ind = (*j); // cout << "IND " << ind << endl; ll dans = RS[i][ind]; ll ans = R[i].size() - dans; return ans; } ll getansL(ll x, ll l) { ll q; // cout << "L " << l << endl; ll ans = 0; for (q = 0; q < block; q++) { // if (MNL[q] != inf)cout << MNL[q] << " " << MXL[q] << " " << q << " MNL" << endl; if (MNL[q] == inf) { continue; } if (MNL[q] >= l) { ans += fastL(q, x); continue; } if (MXL[q] < l) { // cout << "UMOM " << endl; continue; } if (MNL[q] < l) { ans += slowL(q, x, l); } } // if (ans != 0) { // exit(-1); // } for (q = 0; q < lasts.size(); q++) { if (used[lasts[q].i]) { continue; } if (lasts[q].l >= l && lasts[q].sz >= x) { ans++; } } return ans; } ll getansR(ll x, ll r) { ll q; //cout << "X R " << x << " " << r << endl; ll ans = 0; for (q = 0; q < block; q++) { // if (R[q].size() != 0)cout << "SZ " << R[q].size() << " " << q << endl; if (MNR[q] == inf) { continue; } if (MXR[q] <= r) { ll dans = fastR(q, x); // if (dans != 0)cout << "DANS1 " << q << " " << dans << endl; ans += dans; continue; } if (MNR[q] > r) { continue; } if (MXR[q] > r) { ll dans = slowR(q, x, r); // if (dans != 0)cout << "DANS2 " << q << " " << dans << endl; ans += dans; } } for (q = 0; q < lasts.size(); q++) { if (used[lasts[q].i]) { continue; } if (lasts[q].r <= r && lasts[q].sz >= x) { // cout << "DANS3 " << lasts[q].i << " " << 1 << endl; ans++; } } // cout << "ANS " << ans << endl << endl; return ans; } ll answer(seg c, ll k) { if (c.sz < k) { return 0; } ll q, w; ll ans = 0; // for (q = 0; q < lasts.size(); q++) { // if (used[lasts[q].i]) { // continue; // } // ll li = max(lasts[q].l, c.l), ri = min(lasts[q].r, c.r); // if (ri - li + 1 >= k) { // ans++; // } // } // return ans; ll lk = c.r - k + 2, rk = c.l + k - 2; ll allans = getansR(k, inf); ll dansl = getansL(k, lk); // cout << "SMERT" << endl; ll dansr = getansR(k, rk); // cout << "DEBUG " << allans << " " << dansl << " " << dansr << endl; ans = allans - dansr - dansl; return ans; } signed main() { ll q, w, e, a, b, c; // cout << "BLOCKSZ " << block_sz << endl; cin >> n >> t; ll lastans = 0; for (q = 0; q < n; q++) { ll comm; if (q % block_sz == 0) { rebuild(); } cin >> comm; ll l, r; seg x; if (comm == 1) { cin >> l >> r; l ^= (lastans * t); r ^= (lastans * t); if (l > r) { swap(l, r); } x.l = l; x.r = r; x.sz = r - l + 1; x.i = segs.size(); add(x); } if (comm == 2) { cin >> a; a--; del(S[a]); } if (comm == 3) { cin >> l >> r; l ^= (lastans * t); r ^= (lastans * t); if (l > r) { swap(l, r); } x.l = l; x.r = r; x.sz = x.r - x.l + 1; cin >> c; lastans = answer(x, c); cout << lastans << endl; } // cout << "Q " << q << endl; } return 0; }

Compilation message (stderr)

segments.cpp:7:0: warning: ignoring #pragma optimize  [-Wunknown-pragmas]
 #pragma optimize("TKACHENKO-GORYACHENKO")
 
segments.cpp: In function 'void buildL(ll)':
segments.cpp:86:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (w = 0; w < L[q].size(); w++) {
              ~~^~~~~~~~~~~~~
segments.cpp: In function 'void buildR(ll)':
segments.cpp:105:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (w = 0; w < R[q].size(); w++) {
              ~~^~~~~~~~~~~~~
segments.cpp: In function 'void rebuild()':
segments.cpp:134:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (q = 0; q < segs.size(); q++) {
              ~~^~~~~~~~~~~~~
segments.cpp:150:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (q = 0; q < segs.size(); q++) {
              ~~^~~~~~~~~~~~~
segments.cpp:126:8: warning: unused variable 'w' [-Wunused-variable]
  ll q, w;
        ^
segments.cpp: In function 'll slowL(ll, ll, ll)':
segments.cpp:205:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (q = 0; q < L[i].size(); q++) {
              ~~^~~~~~~~~~~~~
segments.cpp: In function 'll slowR(ll, ll, ll)':
segments.cpp:216:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (q = 0; q < R[i].size(); q++) {
              ~~^~~~~~~~~~~~~
segments.cpp: In function 'll getansL(ll, ll)':
segments.cpp:285:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (q = 0; q < lasts.size(); q++) {
              ~~^~~~~~~~~~~~~~
segments.cpp: In function 'll getansR(ll, ll)':
segments.cpp:320:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (q = 0; q < lasts.size(); q++) {
              ~~^~~~~~~~~~~~~~
segments.cpp: In function 'll answer(seg, ll)':
segments.cpp:337:5: warning: unused variable 'q' [-Wunused-variable]
  ll q, w;
     ^
segments.cpp:337:8: warning: unused variable 'w' [-Wunused-variable]
  ll q, w;
        ^
segments.cpp: In function 'int main()':
segments.cpp:360:8: warning: unused variable 'w' [-Wunused-variable]
  ll q, w, e, a, b, c;
        ^
segments.cpp:360:11: warning: unused variable 'e' [-Wunused-variable]
  ll q, w, e, a, b, c;
           ^
segments.cpp:360:17: warning: unused variable 'b' [-Wunused-variable]
  ll q, w, e, a, b, c;
                 ^
#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...