oj.uz

Submission #634339

# Submission time Handle Problem Language Result Execution time Memory
634339 2022-08-24T09:12:22 Z drkarlicio2107 Segments (IZhO18_segments) C++14
0 / 100
 1189 ms 3092 KB 
#include <bits/stdc++.h>
using namespace std;
const int bs=1000, MN=2e5+10, m= (MN+bs-1)/bs, siz=2e5+10; 
int q, t, ids, n, bc; int l[siz], r[siz]; bool unutra[siz];  
vector< pair <int, int> > TRE;  int mini[m], maxi[m]; 
vector<pair <int, int> > dulj[m]; vector<pair <int, int> > answer[m]; vector<pair <int, int> > tre;  
int num(int val) {
	return lower_bound(TRE.begin(), TRE.end(), make_pair (val, (int)-1e9))-TRE.begin(); 
}
int LESS(int rr, int k) {
	if (bc<=0) return 0; 
	int ind=0, ans=0; 
	while (ind<bc && maxi[ind]<=rr) {
		ans+=lower_bound(dulj[ind].begin(), dulj[ind].end(), make_pair(k, -1))-dulj[ind].begin(); ind+=1; 
	}
	for (int i=0; i<dulj [ind].size(); i++) if (dulj [ind][i].second<=rr && dulj [ind][i].first<k) ans++; 
	return ans; 
}
int MORE(int ll, int rr) {
	if (bc<=0) return 0; 
	int ans=0, ind=bc-1; 
	while (ind>0 && mini[ind]>rr) {
		ans+=(int)answer[ind].size()-(upper_bound(answer[ind].begin(), answer[ind].end(), make_pair(ll, (int)1e9))-answer[ind].begin()); ind-=1; 
	}
	for (int i=0; i<answer[ind].size(); i++) if (answer[ind][i].first>ll && answer[ind][i].second>rr) ans++; 
	return ans; 
}
int convert(int ll, int rr, int k) {
	return LESS(rr, k)-LESS(ll-1, k); 
}
bool not_ok(int a1, int b1, int a2, int b2) {
	return b1<a2 ||  b2<a1; 
}
int query(int l1, int r1, int k) {
	if (r1-l1+1<k) return 0; 
	int ans=n-(convert(l1+k-1, r1, k)+MORE(r1-k+1, r1)+num(l1+k-1)); 
	for (int i=0; i<tre.size(); i++) 
		if (!k || (!not_ok(l[tre [i].first], r[tre [i].first], l1, r1) && min(r1, r[tre [i].first])-max(l1, l[tre [i].first])>=k-1)){
			if (tre [i].second) ans--;
			else ans++;
		}
	return ans; 
}
void did() {
	for (int i=0; i<tre.size(); i++) if (tre [i].second) unutra[tre [i].first]=1; 
	TRE.clear(); tre.clear(); 
	for (int i=1; i<ids+1; i++) if (!unutra[i]) TRE.push_back({r[i], i}); 
	sort(TRE.begin(), TRE.end()); n=TRE.size(); bc=(n+bs-1)/bs; 
	for (int b=0; b<=bc; b++) {
		dulj[b].clear(); answer[b].clear(); 
	}
	for (int b=0; b<bc; b++) {
		for (int i=b*bs; i<min(n, (b+1)*bs); i++){
			int ind=TRE[i].second; 
			dulj[b].push_back({r[ind]-l[ind]+1, r[ind]}); 
			answer[b].push_back({l[ind], r[ind]}); 
			maxi[b]=r[ind]; if (i==b*m) mini[b]=r[ind];  
 		}	
 		sort(dulj[b].begin(), dulj[b].end()); sort(answer[b].begin(), answer[b].end()); 
	}
	return ;
}
int main() { 
	scanf ("%d%d", &q, &t); int lA=0;
	for (int i=1; i<=q; i++) {
		if (!(i % bs)) did(); 
		int ty; scanf ("%d", &ty);
		if (ty==1) {
			ids++; scanf ("%d%d", &l[ids], &r [ids]); l[ids]^=t*lA; r[ids]^=t*lA; 
			if (l[ids]>r[ids]) swap(l[ids], r[ids]);
			tre.push_back({ids, 0}); 
		}
		else if (ty==2) {
			int j; cin >> j; tre.push_back({j, 1}); 
		}
		else {
			int l1, r1, k; scanf ("%d%d%d", &l1, &r1, &k) ; l1^=t*lA; r1^=t*lA; 
			if (l1>r1) swap(l1, r1);
			int ans=query(l1, r1, k); lA=ans;
			printf ("%d\n", ans); 
		}
	}
	return 0;
}

Compilation message

segments.cpp: In function 'int LESS(int, int)':
segments.cpp:16:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for (int i=0; i<dulj [ind].size(); i++) if (dulj [ind][i].second<=rr && dulj [ind][i].first<k) ans++;
      |                ~^~~~~~~~~~~~~~~~~~
segments.cpp: In function 'int MORE(int, int)':
segments.cpp:25:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for (int i=0; i<answer[ind].size(); i++) if (answer[ind][i].first>ll && answer[ind][i].second>rr) ans++;
      |                ~^~~~~~~~~~~~~~~~~~~
segments.cpp: In function 'int query(int, int, int)':
segments.cpp:37:17: 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 |  for (int i=0; i<tre.size(); i++)
      |                ~^~~~~~~~~~~
segments.cpp: In function 'void did()':
segments.cpp:45:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for (int i=0; i<tre.size(); i++) if (tre [i].second) unutra[tre [i].first]=1;
      |                ~^~~~~~~~~~~
segments.cpp: In function 'int main()':
segments.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |  scanf ("%d%d", &q, &t); int lA=0;
      |  ~~~~~~^~~~~~~~~~~~~~~~
segments.cpp:67:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |   int ty; scanf ("%d", &ty);
      |           ~~~~~~^~~~~~~~~~~
segments.cpp:69:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |    ids++; scanf ("%d%d", &l[ids], &r [ids]); l[ids]^=t*lA; r[ids]^=t*lA;
      |           ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
segments.cpp:77:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |    int l1, r1, k; scanf ("%d%d%d", &l1, &r1, &k) ; l1^=t*lA; r1^=t*lA;
      |                   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 8 ms 340 KB Output is correct
4 Correct 7 ms 340 KB Output is correct
5 Incorrect 10 ms 468 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 684 KB Output is correct
2 Correct 131 ms 692 KB Output is correct
3 Correct 193 ms 736 KB Output is correct
4 Correct 134 ms 588 KB Output is correct
5 Incorrect 1144 ms 2988 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 640 KB Output is correct
2 Correct 147 ms 668 KB Output is correct
3 Correct 149 ms 592 KB Output is correct
4 Correct 159 ms 620 KB Output is correct
5 Incorrect 1148 ms 3092 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 8 ms 340 KB Output is correct
4 Correct 7 ms 340 KB Output is correct
5 Incorrect 10 ms 468 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 8 ms 340 KB Output is correct
4 Correct 7 ms 340 KB Output is correct
5 Incorrect 10 ms 468 KB Output isn't correct
6 Halted 0 ms 0 KB -