oj.uz

Submission #634378

# Submission time Handle Problem Language Result Execution time Memory
634378 2022-08-24T10:22:03 Z lovrot Segments (IZhO18_segments) C++11
7 / 100
 968 ms 4652 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 = 450;
const int N = 4 * 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;

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

void output(int x){ 
	cout << x << "\n";
	lastans = x;
	return;
}

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

	scanf("%d%d", &n, &xr);
	
	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, 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){
				if(intersect(intv[x], {l, r}) >= k) ans--;
			}
			for(pii x : add){
				if(intersect(intv[x.Y], {l, r}) >= k) ans++;
			}

			if(bkt.empty()){ 
				output(ans);
				continue;
			}

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

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

	return 0; 
}

Compilation message

segments.cpp: In function 'void bucket()':
segments.cpp:34: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]
   34 |  while(p1 < add.size() || p2 < bkt.size()){
      |        ~~~^~~~~~~~~~~~
segments.cpp:34: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]
   34 |  while(p1 < add.size() || p2 < bkt.size()){
      |                           ~~~^~~~~~~~~~~~
segments.cpp:35: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]
   35 |   if(p1 < add.size() && p2 < bkt.size()){
      |      ~~~^~~~~~~~~~~~
segments.cpp:35: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]
   35 |   if(p1 < add.size() && p2 < bkt.size()){
      |                         ~~~^~~~~~~~~~~~
segments.cpp:43: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]
   43 |   } else if(p1 < add.size()){
      |             ~~~^~~~~~~~~~~~
segments.cpp: In function 'int main()':
segments.cpp:144:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |    while(hi < bkt.size() && pos[hi] == b){
      |          ~~~^~~~~~~~~~~~
segments.cpp:149:8: warning: statement has no effect [-Wunused-value]
  149 |    for(b; b < b_cnt; b++){
      |        ^
segments.cpp:97:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |  scanf("%d%d", &n, &xr);
      |  ~~~~~^~~~~~~~~~~~~~~~~
segments.cpp:104:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |    scanf("%d%d", &l, &r);
      |    ~~~~~^~~~~~~~~~~~~~~~
segments.cpp:113:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |    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 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 7 ms 1900 KB Output is correct
4 Correct 7 ms 1876 KB Output is correct
5 Correct 8 ms 2016 KB Output is correct
6 Correct 10 ms 2004 KB Output is correct
7 Correct 10 ms 1876 KB Output is correct
8 Correct 8 ms 2036 KB Output is correct
9 Correct 9 ms 2032 KB Output is correct
10 Correct 7 ms 2024 KB Output is correct
11 Correct 14 ms 2004 KB Output is correct
12 Correct 19 ms 2012 KB Output is correct
13 Correct 9 ms 2004 KB Output is correct
14 Correct 9 ms 2004 KB Output is correct
15 Correct 8 ms 1876 KB Output is correct
16 Correct 9 ms 1876 KB Output is correct
17 Correct 9 ms 1876 KB Output is correct
18 Correct 7 ms 2088 KB Output is correct
19 Correct 9 ms 2004 KB Output is correct
20 Correct 9 ms 1972 KB Output is correct

Subtask #2
0 / 15.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 2224 KB Output is correct
2 Correct 128 ms 2220 KB Output is correct
3 Correct 192 ms 2332 KB Output is correct
4 Correct 145 ms 2240 KB Output is correct
5 Incorrect 968 ms 4420 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 2148 KB Output is correct
2 Correct 133 ms 2252 KB Output is correct
3 Correct 149 ms 2276 KB Output is correct
4 Correct 133 ms 2256 KB Output is correct
5 Incorrect 868 ms 4652 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 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 7 ms 1900 KB Output is correct
4 Correct 7 ms 1876 KB Output is correct
5 Correct 8 ms 2016 KB Output is correct
6 Correct 10 ms 2004 KB Output is correct
7 Correct 10 ms 1876 KB Output is correct
8 Correct 8 ms 2036 KB Output is correct
9 Correct 9 ms 2032 KB Output is correct
10 Correct 7 ms 2024 KB Output is correct
11 Correct 14 ms 2004 KB Output is correct
12 Correct 19 ms 2012 KB Output is correct
13 Correct 9 ms 2004 KB Output is correct
14 Correct 9 ms 2004 KB Output is correct
15 Correct 8 ms 1876 KB Output is correct
16 Correct 9 ms 1876 KB Output is correct
17 Correct 9 ms 1876 KB Output is correct
18 Correct 7 ms 2088 KB Output is correct
19 Correct 9 ms 2004 KB Output is correct
20 Correct 9 ms 1972 KB Output is correct
21 Incorrect 744 ms 3792 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 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 7 ms 1900 KB Output is correct
4 Correct 7 ms 1876 KB Output is correct
5 Correct 8 ms 2016 KB Output is correct
6 Correct 10 ms 2004 KB Output is correct
7 Correct 10 ms 1876 KB Output is correct
8 Correct 8 ms 2036 KB Output is correct
9 Correct 9 ms 2032 KB Output is correct
10 Correct 7 ms 2024 KB Output is correct
11 Correct 14 ms 2004 KB Output is correct
12 Correct 19 ms 2012 KB Output is correct
13 Correct 9 ms 2004 KB Output is correct
14 Correct 9 ms 2004 KB Output is correct
15 Correct 8 ms 1876 KB Output is correct
16 Correct 9 ms 1876 KB Output is correct
17 Correct 9 ms 1876 KB Output is correct
18 Correct 7 ms 2088 KB Output is correct
19 Correct 9 ms 2004 KB Output is correct
20 Correct 9 ms 1972 KB Output is correct
21 Incorrect 744 ms 3792 KB Output isn't correct
22 Halted 0 ms 0 KB -