Submission #383032

#	Time	Username	Problem	Language	Result	Execution time	Memory
383032		maximath_1	Segments (IZhO18_segments)	C++11	100 / 100	2187 ms	32972 KiB

segments

#include <stdio.h>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <numeric>
#include <queue>
#include <assert.h>
#include <map>
#include <set>
#include <limits.h>
using namespace std;
 
#define ll long long
#define ld long double
const int MX = 200005;
const int LG = (int)log2(MX) + 2;
const int BLOCK = 1205;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
 
#define gc getchar//_unlocked //can't for window server
void cin(int &x){
	char c = gc(); bool neg = false;
	for(; c < '0'||'9' < c; c = gc())
		if(c == '-') neg=true;
	x = c - '0'; c = gc();
	for(; '0' <= c && c <= '9'; c = gc())
		x = (x << 1) + (x << 3) + (c - '0');
	if(neg) x = -x;
}
 
int n, t, last_ans = 0;
int lf[MX], rg[MX], len[MX], cnt_id = 0;
 
bool cmp(int a, int b){
	return len[a] <= len[b];
}
 
int isect(int l1, int r1, int l2, int r2){
	return min(r1, r2) - max(l1, l2) + 1;
}
 
struct dat{
	vector<int> pend, all;
	vector<int> BL[MX], BR[MX];
 
	void add(int id){
		pend.push_back(id);
		if(pend.size() >= BLOCK){
			vector<int> tmp;
			sort(pend.begin(), pend.end(), cmp);

			int i = 0, j = 0;
			for(i = 0, j = 0; i < pend.size() && j < all.size();){
				if(cmp(pend[i], all[j])){
					tmp.push_back(pend[i]);
					i ++;
				}else{
					tmp.push_back(all[j]);
					j ++;
				}
			}

			for(; i < pend.size(); i ++)
				tmp.push_back(pend[i]);
			for(; j < all.size(); j ++)
				tmp.push_back(all[j]);

			all.clear(); pend.clear();
			all = tmp;
 
			for(int bl = 0; bl * BLOCK < all.size(); bl ++)
				BL[bl].clear(), BR[bl].clear();
 
			for(int i = 0; i < all.size(); i ++){
				int bl = i / BLOCK;
				BL[bl].push_back(lf[all[i]]);
				BR[bl].push_back(rg[all[i]]);
			}
 
			for(int bl = 0; bl * BLOCK < all.size(); bl ++)
				sort(BL[bl].begin(), BL[bl].end()),
				sort(BR[bl].begin(), BR[bl].end());
		}
	}
 
	int get(int l, int r, int k){
		int res = 0;
		if(r - l + 1 < k) return 0;
 
		for(int i = 0; i < pend.size(); i ++)
			if(isect(lf[pend[i]], rg[pend[i]], l, r) >= k)
				res ++;
 
 		int cnt = 0;
		for(int bl = 0; bl * BLOCK < all.size(); bl ++){
			int st = bl * BLOCK, ed = min(st + BLOCK - 1, (int)all.size() - 1);
 
			if(len[all[st]] >= k){
				res += ed - st + 1;
				res -= BL[bl].end() - upper_bound(BL[bl].begin(), BL[bl].end(), r - k + 1);
				res -= lower_bound(BR[bl].begin(), BR[bl].end(), l + k - 1) - BR[bl].begin();
			}else if(len[all[ed]] >= k){
				cnt ++;
				for(int i = st; i <= ed; i ++)
					if(isect(lf[all[i]], rg[all[i]], l, r) >= k)
						res ++;					
			}
		}

		if(cnt > 1){
			exit(42);
		}
 
		return res;
	}
} active, deleted;
 
int main(){
	cin(n); cin(t);
 
	for(int tp, l, r, k; n --;){
		cin(tp);
		if(tp == 1){
			cin(l); cin(r);
			l ^= (t * last_ans);
			r ^= (t * last_ans);
			if(l > r) swap(l, r);
 
			cnt_id ++;
			lf[cnt_id] = l, rg[cnt_id] = r;
			len[cnt_id] = r - l + 1;
 
			active.add(cnt_id);
		}else if(tp == 2){
			cin(k);
 
			deleted.add(k);
		}else{
			cin(l); cin(r); cin(k);
			l ^= (t * last_ans);
			r ^= (t * last_ans);
			if(l > r) swap(l, r);
 
			last_ans = active.get(l, r, k) - deleted.get(l, r, k);
			printf("%d\n", last_ans);
		}
	}
 
	return 0;
}

Compilation message (stderr)

segments.cpp: In member function 'void dat::add(int)':
segments.cpp:56:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |    for(i = 0, j = 0; i < pend.size() && j < all.size();){
      |                      ~~^~~~~~~~~~~~~
segments.cpp:56:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |    for(i = 0, j = 0; i < pend.size() && j < all.size();){
      |                                         ~~^~~~~~~~~~~~
segments.cpp:66:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |    for(; i < pend.size(); i ++)
      |          ~~^~~~~~~~~~~~~
segments.cpp:68:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |    for(; j < all.size(); j ++)
      |          ~~^~~~~~~~~~~~
segments.cpp:74:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |    for(int bl = 0; bl * BLOCK < all.size(); bl ++)
      |                    ~~~~~~~~~~~^~~~~~~~~~~~
segments.cpp:77:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |    for(int i = 0; i < all.size(); i ++){
      |                   ~~^~~~~~~~~~~~
segments.cpp:83:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |    for(int bl = 0; bl * BLOCK < all.size(); bl ++)
      |                    ~~~~~~~~~~~^~~~~~~~~~~~
segments.cpp: In member function 'int dat::get(int, int, int)':
segments.cpp:93:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |   for(int i = 0; i < pend.size(); i ++)
      |                  ~~^~~~~~~~~~~~~
segments.cpp:98:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |   for(int bl = 0; bl * BLOCK < all.size(); bl ++){
      |                   ~~~~~~~~~~~^~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 15 / 15
• Subtask 3: 16 / 16
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20
• Subtask 6: 25 / 25