Submission #634378

#TimeUsernameProblemLanguageResultExecution timeMemory
634378lovrotSegments (IZhO18_segments)C++11
7 / 100
968 ms4652 KiB
#include <bits/stdc++.h> #define pii pair<int, int> #define X first #define Y second #define pb push_back using namespace std; const int SQR = 450; const int N = 4 * 1e5 + 10; int n, xr, lastans, pos[N]; int b_cnt; //num. of buckets int cnt; //num of diff. intervals bool ban[N]; pii intv[N]; vector<vector<int>> lft, rgt; vector<pii> bkt, bkt2, add; vector<int> vl, vr, rem; int intersect(pii a, pii b){ if(b.X > a.Y || a.X > b.Y) return 0; return min(a.Y, b.Y) - max(a.X, b.X) + 1; } void bucket(){ for(int x : rem) ban[x] = true; int p1 = 0, p2 = 0; sort(add.begin(), add.end()); bkt2.clear(); while(p1 < add.size() || p2 < bkt.size()){ if(p1 < add.size() && p2 < bkt.size()){ if(add[p1].X < bkt[p2].X){ bkt2.pb(add[p1]); p1++; } else { bkt2.pb(bkt[p2]); p2++; } } else if(p1 < add.size()){ bkt2.pb(add[p1]); p1++; } else { bkt2.pb(bkt[p2]); p2++; } } bkt.clear(); for(pii x : bkt2){ if(!ban[x.Y]) bkt.pb(x); } lft.clear(); rgt.clear(); for(pii x : bkt){ vl.pb(intv[x.Y].X); vr.pb(intv[x.Y].Y); if(vl.size() >= SQR){ sort(vl.begin(), vl.end()); sort(vr.begin(), vr.end()); lft.pb(vl); rgt.pb(vr); vl.clear(); vr.clear(); } } if(!vl.empty()){ sort(vl.begin(), vl.end()); sort(vr.begin(), vr.end()); lft.pb(vl); rgt.pb(vr); vl.clear(); vr.clear(); } for(int x : rem) ban[x] = false; rem.clear(); add.clear(); b_cnt = lft.size(); } void output(int x){ cout << x << "\n"; lastans = x; return; } int main(){ for(int i = 0; i < N; i++) pos[i] = i / SQR; scanf("%d%d", &n, &xr); for(int i = 0; i < n; i++){ int t; cin >> t; if(t == 1){ int l, r; scanf("%d%d", &l, &r); l = l ^ (xr * lastans); r = r ^ (xr * lastans); if(l > r) swap(l, r); intv[++cnt] = {l, r}; add.pb({r - l + 1, cnt}); } else if(t == 2){ int ind; scanf("%d", &ind); rem.pb(ind); } else { int l, r, k, ans = 0; scanf("%d%d%d", &l, &r, &k); l = l ^ (xr * lastans); r = r ^ (xr * lastans); if(l > r) swap(l, r); for(int x : rem){ if(intersect(intv[x], {l, r}) >= k) ans--; } for(pii x : add){ if(intersect(intv[x.Y], {l, r}) >= k) ans++; } if(bkt.empty()){ output(ans); continue; } int lo = -1, hi = bkt.size() - 1; while(hi - lo > 1){ int mi = (lo + hi) / 2; if(bkt[mi].X < k) lo = mi; else hi = mi; } int b = pos[hi]; while(hi < bkt.size() && pos[hi] == b){ if(intersect(intv[bkt[hi].Y], {l, r}) >= k) ans++; hi++; } b++; for(b; b < b_cnt; b++){ ans += lft[b].size(); ans -= upper_bound(rgt[b].begin(), rgt[b].end(), l + k - 1) - rgt[b].begin(); ans -= lft[b].end() - upper_bound(lft[b].begin(), lft[b].end(), r - k + 1); } output(ans); } if(add.size() + rem.size() >= SQR){ bucket(); } } return 0; }

Compilation message (stderr)

segments.cpp: In function 'void bucket()':
segments.cpp:34:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  while(p1 < add.size() || p2 < bkt.size()){
      |        ~~~^~~~~~~~~~~~
segments.cpp:34:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  while(p1 < add.size() || p2 < bkt.size()){
      |                           ~~~^~~~~~~~~~~~
segments.cpp:35:9: 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 |   if(p1 < add.size() && p2 < bkt.size()){
      |      ~~~^~~~~~~~~~~~
segments.cpp:35:28: 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 |   if(p1 < add.size() && p2 < bkt.size()){
      |                         ~~~^~~~~~~~~~~~
segments.cpp:43:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   } else if(p1 < add.size()){
      |             ~~~^~~~~~~~~~~~
segments.cpp: In function 'int main()':
segments.cpp:144:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |    while(hi < bkt.size() && pos[hi] == b){
      |          ~~~^~~~~~~~~~~~
segments.cpp:149:8: warning: statement has no effect [-Wunused-value]
  149 |    for(b; b < b_cnt; b++){
      |        ^
segments.cpp:97:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |  scanf("%d%d", &n, &xr);
      |  ~~~~~^~~~~~~~~~~~~~~~~
segments.cpp:104:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |    scanf("%d%d", &l, &r);
      |    ~~~~~^~~~~~~~~~~~~~~~
segments.cpp:113:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |    scanf("%d", &ind);
      |    ~~~~~^~~~~~~~~~~~
segments.cpp:117:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |    scanf("%d%d%d", &l, &r, &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...