Submission #176046

#	Time	Username	Problem	Language	Result	Execution time	Memory
176046		Lightning	Segments (IZhO18_segments)	C++14	7 / 100	5027 ms	3764 KiB

segments

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#include <stack>
#include <queue>
#include <deque>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef pair <int, int> pii;

//#define ordered_set tree<pii, null_type,less<pii>, rb_tree_tag,tree_order_statistics_node_update>
//  order_of_key (k) : Number of items strictly smaller than k .
//  find_by_order(k) : K-th element in a set (counting from zero).
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define pb push_back
#define ppb pop_back
#define mkp make_pair
#define F first
#define S second
#define show(a) cerr << #a <<" -> "<< a <<"\n"
#define fo(a, b, c, d) for(int (a) = (b); (a) <= (c); (a) += (d))
#define foo(a, b, c ,d) for(int (a) = (b); (a) >= (c); (a) -= (d))
//#define int ll

const int N = 2e5 + 5;
const int INF = 1e9 + 5;

int n, cnt;
pii seg[N];
//set <int> id;
int t;
bool off[N];

bool com(int k, int l1, int r1, int l2, int r2) {
	int l = max(l1, l2);
	int r = min(r1, r2);
	return (max(r - l + 1, 0) >= k);
}

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> t;
//	for(int i = 1; i <= n; ++i) {
//		id.insert(i);
//	}
	int lastans = 0;
	for(int it = 1; it <= n; ++it) {
		int type;
		cin >> type;
		if(type == 1) {
			int a, b;
			cin >> a >> b;
			//int curID = *id.begin();
			int curID = ++cnt;
			int l = (a ^ (t * lastans));
			int r = (b ^ (t * lastans));
			if(l > r) swap(l, r);
			seg[curID] = mkp(l, r);
			//id.erase(curID);
		} else if(type == 2) {
			int a;
			cin >> a;
			//seg[a] = mkp(0, 0);
			off[a] = 1;
		} else {
			int a, b, k;
			cin >> a >> b >> k;
			int l = (a ^ (t * lastans));
			int r = (b ^ (t * lastans));
			if(l > r) swap(l, r);
			int ans = 0;
			for(int i = 1; i <= cnt; ++i) {
				//if(id.find(i) != id.end()) continue; // if i exist in set id, it maens that i hasn't segment
				if(off[i]) continue;
				if(com(k, l, r, seg[i].F, seg[i].S)) {
					++ans;
				}	
			}
			cout << ans <<"\n";
			lastans = ans;
		}
	}		
	return 0;
}
/*
6 1
1 1 2
3 2 4 2
1 3 5
3 2 3 1
2 1
3 0 3 1
6 0
1 3 10
1 3 5
3 6 10 6
2 1
1 3 10
3 6 4 2
*/
/*
	If you only do what you can do, 
	You will never be more than you are now!
------	------	------	------	------	------	------	------	------	------	------	------
	We must all suffer from one of two pains: the pain of discipline or the pain of regret. 
	The difference is discipline weighs grams while regret weighs tons.
*/

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