제출 #798600

#제출 시각아이디문제언어결과실행 시간메모리
798600kingfran1907Segments (IZhO18_segments)C++14
75 / 100
5071 ms14324 KiB
#include <bits/stdc++.h> #define X first #define Y second using namespace std; typedef long long llint; const int maxn = 2e5+10; const int block = 500; int n, t; int cnt = 0; vector< int > lef[maxn], rig[maxn]; int L[maxn], R[maxn]; int bio[maxn]; vector< pair<int, int> > v; vector< int > inds; bool cmp(int x, int y) { return R[x] - L[x] < R[y] - L[y]; } int inter(int ax, int ay, int bx, int by) { return min(ay, by) - max(ax, bx) + 1; } int main() { scanf("%d%d", &n, &t); int lastans = 0; while (n--) { int type; scanf("%d", &type); if (type == 1) { int l, r; scanf("%d%d", &l, &r); l = l ^ (t * lastans); r = r ^ (t * lastans); if (l > r) swap(l, r); //printf("adding: %d %d\n", l, r); ++cnt; v.push_back({cnt, 1}); L[cnt] = l, R[cnt] = r; } else if (type == 2) { int x; scanf("%d", &x); v.push_back({x, -1}); } else { int l, r, k; scanf("%d%d%d", &l, &r, &k); l = l ^ (t * lastans); r = r ^ (t * lastans); if (l > r) swap(l, r); //printf("query: %d %d\n", l, r); lastans = 0; for (int i = 0; i < inds.size(); i += block) { int tr = i / block; int las = min((int)inds.size(), i + block) - 1; /*printf("block: "); for (int j = 0; j < block; j++) { if (i + j >= inds.size()) break; printf("(%d %d) ", L[inds[i + j]], R[inds[i + j]]); } printf("\n");*/ if (R[inds[las]] - L[inds[las]] + 1 < k) continue; if (R[inds[i]] - L[inds[i]] + 1 >= k) { lastans += las - i + 1; int ind = lower_bound(rig[tr].begin(), rig[tr].end(), l + k - 1) - rig[tr].begin(); //printf("removing: %d\n", ind); lastans -= ind; ind = upper_bound(lef[tr].begin(), lef[tr].end(), r - k + 1) - lef[tr].begin(); lastans -= lef[tr].size() - ind; //printf("removing: %d\n", lef[tr].size() - ind); } else { for (int j = 0; j < block; j++) { if (i + j >= inds.size()) break; lastans += (inter(l, r, L[inds[i + j]], R[inds[i + j]]) >= k); } } } for (auto iter : v) { int ind = iter.X; int cost = iter.Y; if (inter(l, r, L[ind], R[ind]) >= k) lastans += cost; } printf("%d\n", lastans); } if (n % block == 0) { for (int i = 0; i < maxn / block; i++) { lef[i].clear(); rig[i].clear(); } for (auto iter : v) { bio[iter.X] += iter.Y; } v.clear(); inds.clear(); for (int i = 1; i <= cnt; i++) { if (bio[i]) inds.push_back(i); } sort(inds.begin(), inds.end(), cmp); for (int i = 0; i < inds.size(); i++) { int tr = i / block; lef[tr].push_back(L[inds[i]]); rig[tr].push_back(R[inds[i]]); } for (int i = 0; i < maxn / block; i++) { sort(lef[i].begin(), lef[i].end()); sort(rig[i].begin(), rig[i].end()); } } } return 0; }

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

segments.cpp: In function 'int main()':
segments.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |    for (int i = 0; i < inds.size(); i += block) {
      |                    ~~^~~~~~~~~~~~~
segments.cpp:79:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |       if (i + j >= inds.size()) break;
      |           ~~~~~~^~~~~~~~~~~~~~
segments.cpp:110:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |    for (int i = 0; i < inds.size(); i++) {
      |                    ~~^~~~~~~~~~~~~
segments.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |  scanf("%d%d", &n, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~
segments.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |   scanf("%d", &type);
      |   ~~~~~^~~~~~~~~~~~~
segments.cpp:35:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |    scanf("%d%d", &l, &r);
      |    ~~~~~^~~~~~~~~~~~~~~~
segments.cpp:46:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |    scanf("%d", &x);
      |    ~~~~~^~~~~~~~~~
segments.cpp:50:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |    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...