oj.uz

Submission #634252

# Submission time Handle Problem Language Result Execution time Memory
634252 2022-08-24T07:56:26 Z lovrot Segments (IZhO18_segments) C++11
7 / 100
 100 ms 65536 KB 
#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 = 5010;
const int N = 2 * 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;

	sort(add.begin(), add.end());

	int p1 = 0;
	int p2 = 0;
	lft.clear();
	rgt.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]);
			p2++;
		} else { 
			bkt2.pb(bkt[p2]);
			p2++;
		}
	}
	bkt.clear();
	for(pii x : bkt2){ 
		if(!ban[x.Y])
			bkt.pb(x);
	}
	bkt2.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();
}

int main(){ 
	for(int i = 0; i < N; i++) pos[i] = i / SQR;

	scanf("%d%d", &n, &xr);
	
	//cout << intersect({1, 2}, {2, 3}) << "\n";

	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;
			int 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){
				// cout << intv[x].X << " " << intv[x].Y << " " << l << " " << r << ": " << intersect(intv[x], {l, r}) << " -\n";
				if(intersect(intv[x], {l, r}) >= k) ans--;
			}
			for(pii x : add){
				// cout << intv[x.Y].X << " " << intv[x.Y].Y << " " << l << " " << r << ": " << intersect(intv[x.Y], {l, r}) << " +\n";
				if(intersect(intv[x.Y], {l, r}) >= k) ans++;
			}

			// int lo = 0, hi = b_cnt - 1;
			// while(hi - lo > 1){ 
			// 	int mi = (lo + hi) / 2;
			// 	if(bkt[mi].X < k)
			// 		lo = mi;
			// 	else 
			// 		hi = mi;
			// }
			// int b = pos[lo];
			// while(lo < bkt.size() && pos[lo] == b){ 
			// 	if(intersect(intv[bkt[lo].Y], {l, r}) >= k);
			// 	lo++;
			// }
			// b++;
			// for(b; b < b_cnt; b++){ 
			// 	ans += lft[b].size(); 
			// 	ans -= upper_bound(rgt[b].begin(), rgt[b].end(), l + k) - rgt[b].begin();
			// 	ans -= lft[b].end() - upper_bound(lft[b].begin(), lft[b].end(), r - k);
			// }
			cout << ans << "\n";
			lastans = ans;
		}

		if(add.size() + rem.size() >= SQR){ 
			bucket();
		}
	}

	return 0; 
}

Compilation message

segments.cpp: In function 'void bucket()':
segments.cpp:37: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]
   37 |  while(p1 < add.size() || p2 < bkt.size()){
      |        ~~~^~~~~~~~~~~~
segments.cpp:37: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]
   37 |  while(p1 < add.size() || p2 < bkt.size()){
      |                           ~~~^~~~~~~~~~~~
segments.cpp:38: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]
   38 |   if(p1 < add.size() && p2 < bkt.size()){
      |      ~~~^~~~~~~~~~~~
segments.cpp:38: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]
   38 |   if(p1 < add.size() && p2 < bkt.size()){
      |                         ~~~^~~~~~~~~~~~
segments.cpp:46: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]
   46 |   } else if(p1 < add.size()){
      |             ~~~^~~~~~~~~~~~
segments.cpp: In function 'int main()':
segments.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |  scanf("%d%d", &n, &xr);
      |  ~~~~~^~~~~~~~~~~~~~~~~
segments.cpp:102:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |    scanf("%d%d", &l, &r);
      |    ~~~~~^~~~~~~~~~~~~~~~
segments.cpp:112:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |    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);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 19 ms 1108 KB Output is correct
4 Correct 19 ms 1064 KB Output is correct
5 Correct 23 ms 1108 KB Output is correct
6 Correct 30 ms 1188 KB Output is correct
7 Correct 22 ms 1144 KB Output is correct
8 Correct 17 ms 1108 KB Output is correct
9 Correct 15 ms 1176 KB Output is correct
10 Correct 7 ms 1108 KB Output is correct
11 Correct 41 ms 1168 KB Output is correct
12 Correct 39 ms 1176 KB Output is correct
13 Correct 8 ms 1108 KB Output is correct
14 Correct 18 ms 1176 KB Output is correct
15 Correct 20 ms 1236 KB Output is correct
16 Correct 19 ms 1108 KB Output is correct
17 Correct 21 ms 1076 KB Output is correct
18 Correct 15 ms 1108 KB Output is correct
19 Correct 17 ms 1168 KB Output is correct
20 Correct 17 ms 1168 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 50 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 91 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 100 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 19 ms 1108 KB Output is correct
4 Correct 19 ms 1064 KB Output is correct
5 Correct 23 ms 1108 KB Output is correct
6 Correct 30 ms 1188 KB Output is correct
7 Correct 22 ms 1144 KB Output is correct
8 Correct 17 ms 1108 KB Output is correct
9 Correct 15 ms 1176 KB Output is correct
10 Correct 7 ms 1108 KB Output is correct
11 Correct 41 ms 1168 KB Output is correct
12 Correct 39 ms 1176 KB Output is correct
13 Correct 8 ms 1108 KB Output is correct
14 Correct 18 ms 1176 KB Output is correct
15 Correct 20 ms 1236 KB Output is correct
16 Correct 19 ms 1108 KB Output is correct
17 Correct 21 ms 1076 KB Output is correct
18 Correct 15 ms 1108 KB Output is correct
19 Correct 17 ms 1168 KB Output is correct
20 Correct 17 ms 1168 KB Output is correct
21 Runtime error 50 ms 65536 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 19 ms 1108 KB Output is correct
4 Correct 19 ms 1064 KB Output is correct
5 Correct 23 ms 1108 KB Output is correct
6 Correct 30 ms 1188 KB Output is correct
7 Correct 22 ms 1144 KB Output is correct
8 Correct 17 ms 1108 KB Output is correct
9 Correct 15 ms 1176 KB Output is correct
10 Correct 7 ms 1108 KB Output is correct
11 Correct 41 ms 1168 KB Output is correct
12 Correct 39 ms 1176 KB Output is correct
13 Correct 8 ms 1108 KB Output is correct
14 Correct 18 ms 1176 KB Output is correct
15 Correct 20 ms 1236 KB Output is correct
16 Correct 19 ms 1108 KB Output is correct
17 Correct 21 ms 1076 KB Output is correct
18 Correct 15 ms 1108 KB Output is correct
19 Correct 17 ms 1168 KB Output is correct
20 Correct 17 ms 1168 KB Output is correct
21 Runtime error 50 ms 65536 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -