oj.uz

Submission #798584

# Submission time Handle Problem Language Result Execution time Memory
798584 2023-07-30T21:05:12 Z kingfran1907 Segments (IZhO18_segments) C++14
7 / 100
 2123 ms 4808 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 = 450;

int n, t;
int cnt = 0;
vector< int > lef[block], rig[block];
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);
			
			++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);
			
			lastans = 0;
			for (int i = 0; i < inds.size(); i += block) {
				int tr = i / block;
				int las = min((int)inds.size(), i + block) - 1;
				
				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) - rig[tr].begin();
					lastans -= ind;
					ind = upper_bound(lef[tr].begin(), lef[tr].end(), r - k) - lef[tr].begin();
					lastans -= 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 < 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 += block) {
				int tr = i / block;
				for (int j = 0; j < block; j++) {
					if (i + j >= inds.size()) break;
					lef[tr].push_back(L[inds[i + j]]);
					rig[tr].push_back(R[inds[i + j]]);
				}
				sort(lef[tr].begin(), lef[tr].end());
				sort(rig[tr].begin(), rig[tr].end());
			}
		}
	}
	return 0;
}

Compilation message

segments.cpp: In function 'int main()':
segments.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |    for (int i = 0; i < inds.size(); i += block) {
      |                    ~~^~~~~~~~~~~~~
segments.cpp:68:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |       if (i + j >= inds.size()) break;
      |           ~~~~~~^~~~~~~~~~~~~~
segments.cpp:99:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |    for (int i = 0; i < inds.size(); i += block) {
      |                    ~~^~~~~~~~~~~~~
segments.cpp:102:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |      if (i + j >= inds.size()) break;
      |          ~~~~~~^~~~~~~~~~~~~~
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:45:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |    scanf("%d", &x);
      |    ~~~~~^~~~~~~~~~
segments.cpp:49:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |    scanf("%d%d%d", &l, &r, &k);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 2 ms 448 KB Output is correct
5 Correct 7 ms 584 KB Output is correct
6 Correct 8 ms 468 KB Output is correct
7 Correct 4 ms 472 KB Output is correct
8 Correct 6 ms 468 KB Output is correct
9 Correct 6 ms 468 KB Output is correct
10 Correct 8 ms 580 KB Output is correct
11 Correct 8 ms 468 KB Output is correct
12 Correct 8 ms 464 KB Output is correct
13 Correct 6 ms 468 KB Output is correct
14 Correct 6 ms 468 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 3 ms 468 KB Output is correct
17 Correct 5 ms 468 KB Output is correct
18 Correct 6 ms 468 KB Output is correct
19 Correct 5 ms 464 KB Output is correct
20 Correct 7 ms 468 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1894 ms 4548 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 2652 KB Output is correct
2 Correct 43 ms 2560 KB Output is correct
3 Correct 53 ms 2660 KB Output is correct
4 Correct 44 ms 2640 KB Output is correct
5 Incorrect 2123 ms 4480 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 2840 KB Output is correct
2 Correct 44 ms 2928 KB Output is correct
3 Correct 54 ms 2776 KB Output is correct
4 Correct 48 ms 2852 KB Output is correct
5 Incorrect 2074 ms 4808 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 2 ms 448 KB Output is correct
5 Correct 7 ms 584 KB Output is correct
6 Correct 8 ms 468 KB Output is correct
7 Correct 4 ms 472 KB Output is correct
8 Correct 6 ms 468 KB Output is correct
9 Correct 6 ms 468 KB Output is correct
10 Correct 8 ms 580 KB Output is correct
11 Correct 8 ms 468 KB Output is correct
12 Correct 8 ms 464 KB Output is correct
13 Correct 6 ms 468 KB Output is correct
14 Correct 6 ms 468 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 3 ms 468 KB Output is correct
17 Correct 5 ms 468 KB Output is correct
18 Correct 6 ms 468 KB Output is correct
19 Correct 5 ms 464 KB Output is correct
20 Correct 7 ms 468 KB Output is correct
21 Incorrect 1894 ms 4548 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 2 ms 448 KB Output is correct
5 Correct 7 ms 584 KB Output is correct
6 Correct 8 ms 468 KB Output is correct
7 Correct 4 ms 472 KB Output is correct
8 Correct 6 ms 468 KB Output is correct
9 Correct 6 ms 468 KB Output is correct
10 Correct 8 ms 580 KB Output is correct
11 Correct 8 ms 468 KB Output is correct
12 Correct 8 ms 464 KB Output is correct
13 Correct 6 ms 468 KB Output is correct
14 Correct 6 ms 468 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 3 ms 468 KB Output is correct
17 Correct 5 ms 468 KB Output is correct
18 Correct 6 ms 468 KB Output is correct
19 Correct 5 ms 464 KB Output is correct
20 Correct 7 ms 468 KB Output is correct
21 Incorrect 1894 ms 4548 KB Output isn't correct
22 Halted 0 ms 0 KB -