oj.uz

Submission #798593

# Submission time Handle Problem Language Result Execution time Memory
798593 2023-07-30T21:19:26 Z kingfran1907 Segments (IZhO18_segments) C++14
7 / 100
 5000 ms 10244 KB 
#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 = 1;

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(pair<int, int> a, pair<int, int> b) {
	return min(a.Y, b.Y) - max(a.X, b.X) + 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;
}

Compilation message

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);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9684 KB Output is correct
2 Correct 7 ms 9700 KB Output is correct
3 Correct 2628 ms 9816 KB Output is correct
4 Correct 2788 ms 9864 KB Output is correct
5 Correct 3838 ms 10152 KB Output is correct
6 Correct 3740 ms 10124 KB Output is correct
7 Correct 2735 ms 9868 KB Output is correct
8 Correct 3291 ms 10244 KB Output is correct
9 Correct 3306 ms 10068 KB Output is correct
10 Correct 3544 ms 10156 KB Output is correct
11 Correct 3206 ms 10096 KB Output is correct
12 Correct 3243 ms 10024 KB Output is correct
13 Correct 3586 ms 10240 KB Output is correct
14 Correct 3151 ms 10016 KB Output is correct
15 Correct 2440 ms 9740 KB Output is correct
16 Correct 2291 ms 9948 KB Output is correct
17 Correct 2840 ms 10044 KB Output is correct
18 Correct 3350 ms 10148 KB Output is correct
19 Correct 2958 ms 10044 KB Output is correct
20 Correct 3155 ms 10008 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5024 ms 10176 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5046 ms 9896 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5018 ms 9796 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9684 KB Output is correct
2 Correct 7 ms 9700 KB Output is correct
3 Correct 2628 ms 9816 KB Output is correct
4 Correct 2788 ms 9864 KB Output is correct
5 Correct 3838 ms 10152 KB Output is correct
6 Correct 3740 ms 10124 KB Output is correct
7 Correct 2735 ms 9868 KB Output is correct
8 Correct 3291 ms 10244 KB Output is correct
9 Correct 3306 ms 10068 KB Output is correct
10 Correct 3544 ms 10156 KB Output is correct
11 Correct 3206 ms 10096 KB Output is correct
12 Correct 3243 ms 10024 KB Output is correct
13 Correct 3586 ms 10240 KB Output is correct
14 Correct 3151 ms 10016 KB Output is correct
15 Correct 2440 ms 9740 KB Output is correct
16 Correct 2291 ms 9948 KB Output is correct
17 Correct 2840 ms 10044 KB Output is correct
18 Correct 3350 ms 10148 KB Output is correct
19 Correct 2958 ms 10044 KB Output is correct
20 Correct 3155 ms 10008 KB Output is correct
21 Execution timed out 5024 ms 10176 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9684 KB Output is correct
2 Correct 7 ms 9700 KB Output is correct
3 Correct 2628 ms 9816 KB Output is correct
4 Correct 2788 ms 9864 KB Output is correct
5 Correct 3838 ms 10152 KB Output is correct
6 Correct 3740 ms 10124 KB Output is correct
7 Correct 2735 ms 9868 KB Output is correct
8 Correct 3291 ms 10244 KB Output is correct
9 Correct 3306 ms 10068 KB Output is correct
10 Correct 3544 ms 10156 KB Output is correct
11 Correct 3206 ms 10096 KB Output is correct
12 Correct 3243 ms 10024 KB Output is correct
13 Correct 3586 ms 10240 KB Output is correct
14 Correct 3151 ms 10016 KB Output is correct
15 Correct 2440 ms 9740 KB Output is correct
16 Correct 2291 ms 9948 KB Output is correct
17 Correct 2840 ms 10044 KB Output is correct
18 Correct 3350 ms 10148 KB Output is correct
19 Correct 2958 ms 10044 KB Output is correct
20 Correct 3155 ms 10008 KB Output is correct
21 Execution timed out 5024 ms 10176 KB Time limit exceeded
22 Halted 0 ms 0 KB -