oj.uz

Submission #798600

# Submission time Handle Problem Language Result Execution time Memory
798600 2023-07-30T21:27:02 Z kingfran1907 Segments (IZhO18_segments) C++14
75 / 100
 5000 ms 14324 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 = 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;
}

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 5 ms 9700 KB Output is correct
2 Correct 5 ms 9648 KB Output is correct
3 Correct 7 ms 9812 KB Output is correct
4 Correct 7 ms 9812 KB Output is correct
5 Correct 11 ms 9956 KB Output is correct
6 Correct 11 ms 9940 KB Output is correct
7 Correct 9 ms 9836 KB Output is correct
8 Correct 10 ms 9836 KB Output is correct
9 Correct 10 ms 9840 KB Output is correct
10 Correct 10 ms 9844 KB Output is correct
11 Correct 14 ms 9844 KB Output is correct
12 Correct 12 ms 9812 KB Output is correct
13 Correct 10 ms 9844 KB Output is correct
14 Correct 10 ms 9840 KB Output is correct
15 Correct 7 ms 9840 KB Output is correct
16 Correct 9 ms 9840 KB Output is correct
17 Correct 9 ms 9812 KB Output is correct
18 Correct 11 ms 9928 KB Output is correct
19 Correct 9 ms 9812 KB Output is correct
20 Correct 11 ms 9840 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1712 ms 13868 KB Output is correct
2 Correct 1728 ms 13860 KB Output is correct
3 Correct 1750 ms 14088 KB Output is correct
4 Correct 1803 ms 13916 KB Output is correct
5 Correct 1935 ms 14288 KB Output is correct
6 Correct 1946 ms 14288 KB Output is correct
7 Correct 1690 ms 13800 KB Output is correct
8 Correct 1691 ms 13924 KB Output is correct
9 Correct 1741 ms 13924 KB Output is correct
10 Correct 877 ms 13528 KB Output is correct
11 Correct 1151 ms 13652 KB Output is correct
12 Correct 1948 ms 14064 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 12020 KB Output is correct
2 Correct 46 ms 11956 KB Output is correct
3 Correct 60 ms 12060 KB Output is correct
4 Correct 46 ms 11904 KB Output is correct
5 Correct 1960 ms 13852 KB Output is correct
6 Correct 1875 ms 13648 KB Output is correct
7 Correct 1916 ms 13780 KB Output is correct
8 Correct 1893 ms 14240 KB Output is correct
9 Correct 1859 ms 14324 KB Output is correct
10 Correct 1706 ms 13556 KB Output is correct
11 Correct 171 ms 12108 KB Output is correct
12 Correct 1751 ms 13680 KB Output is correct
13 Correct 1565 ms 13476 KB Output is correct
14 Correct 950 ms 12720 KB Output is correct
15 Correct 830 ms 12564 KB Output is correct
16 Correct 582 ms 12516 KB Output is correct
17 Correct 1690 ms 13540 KB Output is correct
18 Correct 1701 ms 13632 KB Output is correct
19 Correct 1694 ms 13496 KB Output is correct
20 Correct 1687 ms 13536 KB Output is correct
21 Correct 239 ms 12468 KB Output is correct
22 Correct 1173 ms 12952 KB Output is correct
23 Correct 1450 ms 13168 KB Output is correct
24 Correct 1233 ms 12912 KB Output is correct
25 Correct 50 ms 11980 KB Output is correct
26 Correct 47 ms 11928 KB Output is correct
27 Correct 50 ms 12040 KB Output is correct
28 Correct 49 ms 12012 KB Output is correct
29 Correct 1524 ms 13352 KB Output is correct
30 Correct 1528 ms 13272 KB Output is correct
31 Correct 1840 ms 14128 KB Output is correct
32 Correct 1700 ms 13472 KB Output is correct
33 Correct 1617 ms 13500 KB Output is correct
34 Correct 798 ms 12556 KB Output is correct
35 Correct 1392 ms 13188 KB Output is correct
36 Correct 1638 ms 13568 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 12236 KB Output is correct
2 Correct 49 ms 12168 KB Output is correct
3 Correct 48 ms 12168 KB Output is correct
4 Correct 52 ms 12204 KB Output is correct
5 Correct 1954 ms 14064 KB Output is correct
6 Correct 682 ms 13156 KB Output is correct
7 Correct 1945 ms 14096 KB Output is correct
8 Correct 920 ms 13560 KB Output is correct
9 Correct 1137 ms 12788 KB Output is correct
10 Correct 1760 ms 13244 KB Output is correct
11 Correct 513 ms 12140 KB Output is correct
12 Correct 1837 ms 13540 KB Output is correct
13 Correct 1603 ms 11980 KB Output is correct
14 Correct 1033 ms 10964 KB Output is correct
15 Correct 1839 ms 11912 KB Output is correct
16 Correct 1659 ms 11296 KB Output is correct
17 Correct 1681 ms 11208 KB Output is correct
18 Correct 1677 ms 11160 KB Output is correct
19 Correct 1689 ms 11204 KB Output is correct
20 Correct 1685 ms 11080 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9700 KB Output is correct
2 Correct 5 ms 9648 KB Output is correct
3 Correct 7 ms 9812 KB Output is correct
4 Correct 7 ms 9812 KB Output is correct
5 Correct 11 ms 9956 KB Output is correct
6 Correct 11 ms 9940 KB Output is correct
7 Correct 9 ms 9836 KB Output is correct
8 Correct 10 ms 9836 KB Output is correct
9 Correct 10 ms 9840 KB Output is correct
10 Correct 10 ms 9844 KB Output is correct
11 Correct 14 ms 9844 KB Output is correct
12 Correct 12 ms 9812 KB Output is correct
13 Correct 10 ms 9844 KB Output is correct
14 Correct 10 ms 9840 KB Output is correct
15 Correct 7 ms 9840 KB Output is correct
16 Correct 9 ms 9840 KB Output is correct
17 Correct 9 ms 9812 KB Output is correct
18 Correct 11 ms 9928 KB Output is correct
19 Correct 9 ms 9812 KB Output is correct
20 Correct 11 ms 9840 KB Output is correct
21 Correct 1712 ms 13868 KB Output is correct
22 Correct 1728 ms 13860 KB Output is correct
23 Correct 1750 ms 14088 KB Output is correct
24 Correct 1803 ms 13916 KB Output is correct
25 Correct 1935 ms 14288 KB Output is correct
26 Correct 1946 ms 14288 KB Output is correct
27 Correct 1690 ms 13800 KB Output is correct
28 Correct 1691 ms 13924 KB Output is correct
29 Correct 1741 ms 13924 KB Output is correct
30 Correct 877 ms 13528 KB Output is correct
31 Correct 1151 ms 13652 KB Output is correct
32 Correct 1948 ms 14064 KB Output is correct
33 Correct 48 ms 12236 KB Output is correct
34 Correct 49 ms 12168 KB Output is correct
35 Correct 48 ms 12168 KB Output is correct
36 Correct 52 ms 12204 KB Output is correct
37 Correct 1954 ms 14064 KB Output is correct
38 Correct 682 ms 13156 KB Output is correct
39 Correct 1945 ms 14096 KB Output is correct
40 Correct 920 ms 13560 KB Output is correct
41 Correct 1137 ms 12788 KB Output is correct
42 Correct 1760 ms 13244 KB Output is correct
43 Correct 513 ms 12140 KB Output is correct
44 Correct 1837 ms 13540 KB Output is correct
45 Correct 1603 ms 11980 KB Output is correct
46 Correct 1033 ms 10964 KB Output is correct
47 Correct 1839 ms 11912 KB Output is correct
48 Correct 1659 ms 11296 KB Output is correct
49 Correct 1681 ms 11208 KB Output is correct
50 Correct 1677 ms 11160 KB Output is correct
51 Correct 1689 ms 11204 KB Output is correct
52 Correct 1685 ms 11080 KB Output is correct
53 Correct 53 ms 10164 KB Output is correct
54 Correct 55 ms 10120 KB Output is correct
55 Correct 48 ms 10128 KB Output is correct
56 Correct 49 ms 10176 KB Output is correct
57 Correct 1268 ms 10768 KB Output is correct
58 Correct 504 ms 10272 KB Output is correct
59 Correct 1849 ms 11336 KB Output is correct
60 Correct 437 ms 10312 KB Output is correct
61 Correct 1588 ms 11260 KB Output is correct
62 Correct 1831 ms 11768 KB Output is correct
63 Correct 1842 ms 11968 KB Output is correct
64 Correct 1837 ms 11836 KB Output is correct
65 Correct 695 ms 10548 KB Output is correct
66 Correct 564 ms 10440 KB Output is correct
67 Correct 1666 ms 11312 KB Output is correct
68 Correct 1429 ms 11252 KB Output is correct
69 Correct 1689 ms 11112 KB Output is correct
70 Correct 1685 ms 11116 KB Output is correct
71 Correct 1688 ms 11320 KB Output is correct
72 Correct 1679 ms 11280 KB Output is correct
73 Correct 829 ms 10644 KB Output is correct
74 Correct 1403 ms 11080 KB Output is correct
75 Correct 1817 ms 11956 KB Output is correct
76 Correct 1833 ms 11920 KB Output is correct
77 Correct 50 ms 10152 KB Output is correct
78 Correct 50 ms 10168 KB Output is correct
79 Correct 54 ms 10112 KB Output is correct
80 Correct 52 ms 10176 KB Output is correct
81 Correct 1394 ms 11076 KB Output is correct
82 Correct 824 ms 10656 KB Output is correct
83 Correct 483 ms 10468 KB Output is correct
84 Correct 1373 ms 11088 KB Output is correct
85 Correct 1669 ms 11420 KB Output is correct
86 Correct 1699 ms 11628 KB Output is correct
87 Correct 1136 ms 10900 KB Output is correct
88 Correct 504 ms 10424 KB Output is correct

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9700 KB Output is correct
2 Correct 5 ms 9648 KB Output is correct
3 Correct 7 ms 9812 KB Output is correct
4 Correct 7 ms 9812 KB Output is correct
5 Correct 11 ms 9956 KB Output is correct
6 Correct 11 ms 9940 KB Output is correct
7 Correct 9 ms 9836 KB Output is correct
8 Correct 10 ms 9836 KB Output is correct
9 Correct 10 ms 9840 KB Output is correct
10 Correct 10 ms 9844 KB Output is correct
11 Correct 14 ms 9844 KB Output is correct
12 Correct 12 ms 9812 KB Output is correct
13 Correct 10 ms 9844 KB Output is correct
14 Correct 10 ms 9840 KB Output is correct
15 Correct 7 ms 9840 KB Output is correct
16 Correct 9 ms 9840 KB Output is correct
17 Correct 9 ms 9812 KB Output is correct
18 Correct 11 ms 9928 KB Output is correct
19 Correct 9 ms 9812 KB Output is correct
20 Correct 11 ms 9840 KB Output is correct
21 Correct 1712 ms 13868 KB Output is correct
22 Correct 1728 ms 13860 KB Output is correct
23 Correct 1750 ms 14088 KB Output is correct
24 Correct 1803 ms 13916 KB Output is correct
25 Correct 1935 ms 14288 KB Output is correct
26 Correct 1946 ms 14288 KB Output is correct
27 Correct 1690 ms 13800 KB Output is correct
28 Correct 1691 ms 13924 KB Output is correct
29 Correct 1741 ms 13924 KB Output is correct
30 Correct 877 ms 13528 KB Output is correct
31 Correct 1151 ms 13652 KB Output is correct
32 Correct 1948 ms 14064 KB Output is correct
33 Correct 50 ms 12020 KB Output is correct
34 Correct 46 ms 11956 KB Output is correct
35 Correct 60 ms 12060 KB Output is correct
36 Correct 46 ms 11904 KB Output is correct
37 Correct 1960 ms 13852 KB Output is correct
38 Correct 1875 ms 13648 KB Output is correct
39 Correct 1916 ms 13780 KB Output is correct
40 Correct 1893 ms 14240 KB Output is correct
41 Correct 1859 ms 14324 KB Output is correct
42 Correct 1706 ms 13556 KB Output is correct
43 Correct 171 ms 12108 KB Output is correct
44 Correct 1751 ms 13680 KB Output is correct
45 Correct 1565 ms 13476 KB Output is correct
46 Correct 950 ms 12720 KB Output is correct
47 Correct 830 ms 12564 KB Output is correct
48 Correct 582 ms 12516 KB Output is correct
49 Correct 1690 ms 13540 KB Output is correct
50 Correct 1701 ms 13632 KB Output is correct
51 Correct 1694 ms 13496 KB Output is correct
52 Correct 1687 ms 13536 KB Output is correct
53 Correct 239 ms 12468 KB Output is correct
54 Correct 1173 ms 12952 KB Output is correct
55 Correct 1450 ms 13168 KB Output is correct
56 Correct 1233 ms 12912 KB Output is correct
57 Correct 50 ms 11980 KB Output is correct
58 Correct 47 ms 11928 KB Output is correct
59 Correct 50 ms 12040 KB Output is correct
60 Correct 49 ms 12012 KB Output is correct
61 Correct 1524 ms 13352 KB Output is correct
62 Correct 1528 ms 13272 KB Output is correct
63 Correct 1840 ms 14128 KB Output is correct
64 Correct 1700 ms 13472 KB Output is correct
65 Correct 1617 ms 13500 KB Output is correct
66 Correct 798 ms 12556 KB Output is correct
67 Correct 1392 ms 13188 KB Output is correct
68 Correct 1638 ms 13568 KB Output is correct
69 Correct 48 ms 12236 KB Output is correct
70 Correct 49 ms 12168 KB Output is correct
71 Correct 48 ms 12168 KB Output is correct
72 Correct 52 ms 12204 KB Output is correct
73 Correct 1954 ms 14064 KB Output is correct
74 Correct 682 ms 13156 KB Output is correct
75 Correct 1945 ms 14096 KB Output is correct
76 Correct 920 ms 13560 KB Output is correct
77 Correct 1137 ms 12788 KB Output is correct
78 Correct 1760 ms 13244 KB Output is correct
79 Correct 513 ms 12140 KB Output is correct
80 Correct 1837 ms 13540 KB Output is correct
81 Correct 1603 ms 11980 KB Output is correct
82 Correct 1033 ms 10964 KB Output is correct
83 Correct 1839 ms 11912 KB Output is correct
84 Correct 1659 ms 11296 KB Output is correct
85 Correct 1681 ms 11208 KB Output is correct
86 Correct 1677 ms 11160 KB Output is correct
87 Correct 1689 ms 11204 KB Output is correct
88 Correct 1685 ms 11080 KB Output is correct
89 Correct 53 ms 10164 KB Output is correct
90 Correct 55 ms 10120 KB Output is correct
91 Correct 48 ms 10128 KB Output is correct
92 Correct 49 ms 10176 KB Output is correct
93 Correct 1268 ms 10768 KB Output is correct
94 Correct 504 ms 10272 KB Output is correct
95 Correct 1849 ms 11336 KB Output is correct
96 Correct 437 ms 10312 KB Output is correct
97 Correct 1588 ms 11260 KB Output is correct
98 Correct 1831 ms 11768 KB Output is correct
99 Correct 1842 ms 11968 KB Output is correct
100 Correct 1837 ms 11836 KB Output is correct
101 Correct 695 ms 10548 KB Output is correct
102 Correct 564 ms 10440 KB Output is correct
103 Correct 1666 ms 11312 KB Output is correct
104 Correct 1429 ms 11252 KB Output is correct
105 Correct 1689 ms 11112 KB Output is correct
106 Correct 1685 ms 11116 KB Output is correct
107 Correct 1688 ms 11320 KB Output is correct
108 Correct 1679 ms 11280 KB Output is correct
109 Correct 829 ms 10644 KB Output is correct
110 Correct 1403 ms 11080 KB Output is correct
111 Correct 1817 ms 11956 KB Output is correct
112 Correct 1833 ms 11920 KB Output is correct
113 Correct 50 ms 10152 KB Output is correct
114 Correct 50 ms 10168 KB Output is correct
115 Correct 54 ms 10112 KB Output is correct
116 Correct 52 ms 10176 KB Output is correct
117 Correct 1394 ms 11076 KB Output is correct
118 Correct 824 ms 10656 KB Output is correct
119 Correct 483 ms 10468 KB Output is correct
120 Correct 1373 ms 11088 KB Output is correct
121 Correct 1669 ms 11420 KB Output is correct
122 Correct 1699 ms 11628 KB Output is correct
123 Correct 1136 ms 10900 KB Output is correct
124 Correct 504 ms 10424 KB Output is correct
125 Correct 108 ms 10660 KB Output is correct
126 Correct 110 ms 10604 KB Output is correct
127 Correct 142 ms 10704 KB Output is correct
128 Correct 119 ms 10572 KB Output is correct
129 Correct 100 ms 10572 KB Output is correct
130 Correct 120 ms 10572 KB Output is correct
131 Correct 1893 ms 11044 KB Output is correct
132 Execution timed out 5071 ms 12408 KB Time limit exceeded
133 Halted 0 ms 0 KB -