Submission #50903

#TimeUsernameProblemLanguageResultExecution timeMemory
50903NicksechkoSegments (IZhO18_segments)C++14
0 / 100
930 ms7656 KiB
#ifndef LOCAL #pragma GCC optimize "-O3" #endif #include <bits/stdc++.h> typedef long long ll; typedef long long llong; typedef long double ld; typedef unsigned long long ull; using namespace std; /* ll pw(ll a, ll b) { ll ans = 1; while (b) { while (!(b & 1)) b >>= 1, a = (a * a) % MOD; ans = (ans * a) % MOD, --b; } return ans; } */ const ll INF = 1e10; const int MAXN = 210000; const int SQ = 500; const int MX = SQ * 2; const int BL = MAXN / SQ + 2; const int UPD = SQ; struct seg { ll l, r, k; int gl, gr, gk; int ds; }; seg arr[MAXN]; int cid; vector<int> gkk[BL]; vector<int> gll[BL]; vector<int> grr[BL]; ll sgl[BL]; ll sgr[BL]; ll sgk[BL]; int gks[BL]; int gls[BL]; int grs[BL]; int glr[BL][BL]; int glk[BL][BL]; int grl[BL][BL]; int grk[BL][BL]; int gkl[BL][BL]; int gkr[BL][BL]; int n, t; int bl; bool cmpl(int a, int b) { return arr[a].l > arr[b].l; } bool cmpr(int a, int b) { return arr[a].r < arr[b].r; } bool cmpk(int a, int b) { return arr[a].k > arr[b].k; } int sum = 0; void rebuild() { int start = clock(); int cnt = 0; vector<int> vv; for (int i = 0; i < cid; ++i) if (!arr[i].ds) ++cnt, vv.push_back(i); for (int i = 0; i < bl; ++i) { gkk[i].clear(), gll[i].clear(), grr[i].clear(); sgk[i] = sgl[i] = sgr[i] = INF; gks[i] = gls[i] = grs[i] = 0; for (int j = 0; j < bl; ++j) glr[i][j] = glk[i][j] = grl[i][j] = grk[i][j] = gkl[i][j] = gkr[i][j] = 0; } bl = (cnt + SQ - 1) / SQ; for (int i = 0; i < bl; ++i) { sgk[i] = sgl[i] = sgr[i] = INF; } sort(vv.begin(), vv.end(), cmpl); for (int i = 0; i < vv.size(); ++i) { arr[vv[i]].gl = i / SQ; } sort(vv.begin(), vv.end(), cmpr); for (int i = 0; i < vv.size(); ++i) { arr[vv[i]].gr = i / SQ; } sort(vv.begin(), vv.end(), cmpk); for (int i = 0; i < vv.size(); ++i) { arr[vv[i]].gk = i / SQ; } for (int i = 0; i < cid; ++i) { if (arr[i].ds) continue; gll[arr[i].gl].push_back(i); grr[arr[i].gr].push_back(i); gkk[arr[i].gk].push_back(i); ++gls[arr[i].gl]; ++grs[arr[i].gr]; ++gks[arr[i].gk]; sgl[arr[i].gl] = min(sgl[arr[i].gl], -arr[i].l); sgr[arr[i].gr] = min(sgr[arr[i].gr], arr[i].r); sgk[arr[i].gk] = min(sgk[arr[i].gk], -arr[i].k); int a = arr[i].gl; int b = arr[i].gr; int c = arr[i].gk; ++glr[a][b], ++glk[a][c], ++grl[b][a], ++grk[b][c], ++gkl[c][a], ++gkr[c][b]; } for (int i = 0; i < bl; ++i) { for (int j = 0; j < bl - 1; ++j) { glr[i][j + 1] += glr[i][j]; glk[i][j + 1] += glk[i][j]; grl[i][j + 1] += grl[i][j]; grk[i][j + 1] += grk[i][j]; gkl[i][j + 1] += gkl[i][j]; gkr[i][j + 1] += gkr[i][j]; } } sgk[0] = sgl[0] = sgr[0] = -INF; bl = max(1, bl); sum += clock() - start; } int main() { scanf("%d%d", &n, &t); int curans = 0; int fll = 1; for (int i = 0; i < n; ++i) { if (fll) { fll = 0; rebuild(); } int tp; scanf("%d", &tp); if (tp == 1) { ll l, r; scanf("%lld%lld", &l, &r); l = l ^ (t * curans); r = r ^ (t * curans); if (l > r) swap(l, r); ++r; ll k = r - l; arr[cid].l = l; arr[cid].r = r; arr[cid].k = r - l; int a = 0, b = 0, c = 0; while (a < bl && sgl[a] <= -l) ++a; while (b < bl && sgr[b] <= r) ++b; while (c < bl && sgk[c] <= -k) ++c; a = max(0, a - 1), b = max(0, b - 1), c = max(0, c - 1); arr[cid].gl = a; arr[cid].gr = b; arr[cid].gk = c; ++gls[a]; ++grs[b]; ++gks[c]; gll[a].push_back(cid); grr[b].push_back(cid); gkk[c].push_back(cid); for (int i = b; i < bl; ++i) ++glr[a][i]; for (int i = c; i < bl; ++i) ++glk[a][i]; for (int i = a; i < bl; ++i) ++grl[b][i]; for (int i = c; i < bl; ++i) ++grk[b][i]; for (int i = a; i < bl; ++i) ++gkl[c][i]; for (int i = b; i < bl; ++i) ++gkr[c][i]; ++cid; } else if (tp == 2) { int id; scanf("%d", &id); --id; arr[id].ds = 1; int a = arr[id].gl; int b = arr[id].gr; int c = arr[id].gk; --gls[a]; --grs[b]; --gks[c]; for (int i = b; i < bl; ++i) --glr[a][i]; for (int i = c; i < bl; ++i) --glk[a][i]; for (int i = a; i < bl; ++i) --grl[b][i]; for (int i = c; i < bl; ++i) --grk[b][i]; for (int i = a; i < bl; ++i) --gkl[c][i]; for (int i = b; i < bl; ++i) --gkr[c][i]; } else { ll x, y, k; scanf("%lld%lld%lld", &x, &y, &k); x = (x ^ (t * curans)); y = (y ^ (t * curans)); if (x > y) swap(x, y); ++y; if (y - x < k) { curans = 0; printf("0\n"); continue; } int a = 0, b = 0, c = 0; int ans = 0; while (c < bl && sgk[c] <= -k) ++c; while (b < bl && sgr[b] < x + k) ++b; while (a < bl && sgl[a] < k - y) ++a; --a; --b; --c; for (int i = 0; i < c; ++i) { ans += gks[i]; if (a > 0) ans -= gkl[i][a - 1]; if (b > 0) ans -= gkr[i][b - 1]; } if (gkk[c].size() > MX) fll = 1; if (gll[a].size() > MX) fll = 1; if (grr[b].size() > MX) fll = 1; for (int id: gkk[c]) { if (arr[id].ds || arr[id].r < x + k || arr[id].l > y - k || arr[id].k < k) continue; ++ans; } for (int id: gll[a]) { if (!arr[id].ds && arr[id].l > y - k && arr[id].gk < c) --ans; } if (b < bl) { for (int id: grr[b]) { if (!arr[id].ds && arr[id].r < x + k && arr[id].gk < c) --ans; } } printf("%d\n", ans); curans = ans; } } cerr << ld(sum) / CLOCKS_PER_SEC << "\n"; return 0; }

Compilation message (stderr)

segments.cpp: In function 'void rebuild()':
segments.cpp:93:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vv.size(); ++i) {
                  ~~^~~~~~~~~~~
segments.cpp:97:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vv.size(); ++i) {
                  ~~^~~~~~~~~~~
segments.cpp:101:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vv.size(); ++i) {
                  ~~^~~~~~~~~~~
segments.cpp: In function 'int main()':
segments.cpp:139:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &t);
  ~~~~~^~~~~~~~~~~~~~~~
segments.cpp:148:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &tp);
   ~~~~~^~~~~~~~~~~
segments.cpp:151:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld%lld", &l, &r);
    ~~~~~^~~~~~~~~~~~~~~~~~~~
segments.cpp:194:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &id);
    ~~~~~^~~~~~~~~~~
segments.cpp:218:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld%lld%lld", &x, &y, &k);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...