Submission #161176

#	Time	Username	Problem	Language	Result	Execution time	Memory
161176		pink_bittern	Segments (IZhO18_segments)	C++14	75 / 100	5019 ms	25656 KiB

segments

#include <bits/stdc++.h>
#define pb push_back
#define pll pair <ll, ll>
#define MOMI using namespace std;
#define mp make_pair
#define pyshnapyshnakaa ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#pragma optimize("TKACHENKO-GORYACHENKO")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define _FORTIFY_SOURCE 0
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("fast-math")
 
typedef int ll;
 
typedef long double ld;

using namespace std;

const ll inf = 2e9 + 500;
const ll maxn = 2e5 + 100;
const ll block = 190; /// cnt_of_blocks
// const ll block_sz = 5e3 + 10;
const ll block_sz = (maxn + block - 1) / block;

ll n, m, k, t;

struct seg{
	ll l;
	ll r;
	inline ll sz() const {
		return r - l + 1;
	}
	ll i;
};

inline bool operator==(seg a, seg b) {
	return a.i == b.i;
}

vector <seg> S;

// vector <seg> segs;

struct R {
	bool operator()(seg a, seg b) const {
		if (a.r == b.r) {
			return a.i < b.i;
		}
		return a.r < b.r; 
	}
};

struct L {
	bool operator()(seg a, seg b) const {
		if (a.l == b.l) {
			return a.i < b.i;
		}
		return a.l < b.l;
	}
};

vector <seg> lasts;

inline bool cmp(seg a, seg b) {
	return (a.r - a.l) < (b.r - b.l);
}

inline bool cmpl(const seg& a, const seg& b) {
	return a.l < b.l;
}

inline bool cmpr(const seg& a, const seg& b) {
	return a.r < b.r;
}

inline bool cmpsz(const seg& a, const seg& b) {
	return a.sz() < b.sz();
}

ll LASTL[block];

ll LASTR[block];

// set <seg, L> segl;

// set <seg, R> segr;

vector <seg> segs;

vector <seg> R[block];

vector <seg> L[block];

// set <ll> L1[block];

// set <ll> R1[block];

// map <ll, ll> LS[block];

// map <ll, ll> RS[block];

ll MNL[block];
ll MXL[block];
ll MNR[block];
ll MXR[block];

ll IL[maxn];
ll IR[maxn];

bool used[maxn];

inline void buildL(ll q) {
	ll w;
	sort(L[q].begin(), L[q].end(), cmpsz);
	MNL[q] = inf;
	MXL[q] = -inf;
	for (w = 0; w < L[q].size(); w++) {
		MNL[q] = min(MNL[q], L[q][w].l);
		MXL[q] = max(MXL[q], L[q][w].l);
		// LS[q][L[q][w].sz()]++;
		// L1[q].insert(L[q][w].sz());
	}
	// ll s = 0;
	// for (auto p : LS[q]) {
	// 	LS[q][p.first] += s;
	// 	s = LS[q][p.first];
	// }
}

inline void buildR(ll q) {
	ll w;
	MNR[q] = -inf;
	MXR[q] = inf;
	// RS[q].clear();
	// R1[q].clear();
	sort(R[q].begin(), R[q].end(), cmpsz);
	for (w = 0; w < R[q].size(); w++) {
		MNR[q] = min(MNR[q], R[q][w].r);
		MXR[q] = max(MXR[q], R[q][w].r);
		// cout << R[q][w].sz() << " ";
		// RS[q][R[q][w].sz()] += 1;
		// R1[q].insert(R[q][w].sz());
	}
	// cout << endl;
	// ll s = 0;
	// for (auto p : RS[q]){
	// 	RS[q][p.first] += s;
	// 	s = RS[q][p.first];
	// }
	// for (auto p: RS[q]) {
	// 	cout << p.first << " " << p.second << endl;
	// }
	// cout << endl << endl;
}

inline void rebuild() { 
	// cout << "VSEM PIZDEC " << endl << endl << endl;
	ll q, w;
	lasts.clear();
	ll blocki = 0;
	// sort(segs.begin(), segs.end(), cmpl);
	for (q = 0; q < block; q++) {
		R[q].clear();
		L[q].clear();
	}
	// for (q = 0; q < segs.size(); q++) {
	// 	if (used[segs[q].i]) {
	// 		continue;
	// 	}
	// 	if (L[blocki].size() > block_sz) {
	// 		blocki++;
	// 	}
	// 	//cout << "BLOCKI " << blocki << " " << segs[q].l << endl;
	// 	// MNL[blocki] = min(MNL[blocki], segs[q].l);
	// 	// MXL[blocki] = max(MXL[blocki], segs[q].l);
	// 	IL[segs[q].i] = blocki;
	// 	L[blocki].pb(segs[q]);
	// }
	sort(segs.begin(), segs.end(), cmpl);
	for (auto p : segs) {
		if (used[p.i]) {
			continue;
		}
		if (L[blocki].size() > block_sz) {
			blocki++;
		}
		IL[p.i] = blocki;
		L[blocki].pb(p);
	}
	sort(segs.begin(), segs.end(), cmpr);
	for (auto p: segs) {
		if (used[p.i]) {
			continue;
		}
		if (R[blocki].size() > block_sz) {
			blocki++;
		}
		IR[p.i] = blocki;
		R[blocki].pb(p);
	}
	// sort(segs.begin(), segs.end(), cmpr);
	// for (q = 0; q < segs.size(); q++) {
	// 	if (used[segs[q].i]) {
	// 		continue;
	// 	}
	// 	// cout << "NOT USED " << segs[q].i << endl;
	// 	if (q != 0) {
	// 		if (R[blocki].size() > block_sz) {
	// 			blocki++;
	// 		}
	// 	}
	// 	// MNR[blocki] = min(MNR[blocki], segs[q].r);
	// 	// MXR[blocki] = max(MXR[blocki], segs[q].r);
	// 	IR[segs[q].i] = blocki;
	// 	R[blocki].pb(segs[q]);
	// }
	// cout << "SZ UMOM " << R[0].size() << endl; 
	for (q = 0; q < block; q++) {
		// if (L[q].size() == 0) {
		// 	break;
		// } 
		buildL(q);
	}
	for (q = 0; q < block; q++) {
		// if (R[q].size() == 0) {
		// 	break;
		// }
		buildR(q);
	}
}

inline void add(seg a) {
	lasts.pb(a);
	S.pb(a);
	// segs.pb(a);
	// segl.insert(a);
	// segr.insert(a);
	segs.push_back(a);
	IL[a.i] = IR[a.i] = -1;
}

inline void del(seg b) {
	// cout << b.i << " I" << endl; 
	ll il = IL[b.i], ir = IR[b.i];
	// segl.erase(b);
	// segr.erase(b);
	used[b.i] = 1;
	if (il == -1) {
		return;
	}
	// cout << il << " " << ir << endl;
	// ll sz = R[ir].size();
	//cout << "IR " << ir << " " << sz << endl;
	L[il].erase(find(L[il].begin(), L[il].end(), b));
	R[ir].erase(find(R[ir].begin(), R[ir].end(), b));
	buildL(il);
	buildR(ir);
	// cout << "NEW SZ " << R[ir].size() << endl << endl;
	// if (R[ir].size() == sz) {
	// 	cout << "UH SYKA" << endl;
	// }
}

inline ll slowL(ll i, ll x, ll l) {
	//cout << "SLOW CARS" << endl; 
	// if (L[i].size() > block_sz * 2) {
	// 	exit(-1);
	// }
	ll q;
	ll ans = 0;
	for (q = 0; q < L[i].size(); q++) {
		if (L[i][q].l >= l && L[i][q].sz() >= x) {
			ans++;
		}
	}
	return ans;
}

inline ll slowR(ll i, ll x, ll r) {
	ll q;
	// if (R[i].size() > block_sz * 2) {
	// 	exit(-1);
	// }
	ll ans = 0;
	for (q = 0; q < R[i].size(); q++) {
		if (R[i][q].r <= r && R[i][q].sz() >= x) {
			ans++;
		}
	}
	return ans;
}

inline ll fastL(ll i, ll x) {
	// lower_bound(A.begin(), A.end(), x, cmpsz);
	// auto j = L1[i].lower_bound(x);
	// if (j == L1[i].begin()) {
	// 	return L[i].size();
	// }
	seg good;
	good.l = 0; good.r = x - 1; 
	ll j = (lower_bound(L[i].begin(), L[i].end(), good, cmpsz) - L[i].begin());
	return L[i].size() - j;
	// for (ll q = 0; q < L[i].size(); q++) {
	// 	cout << L[i][q].sz() << " ";
	// }
	// cout << endl;
	// cout << endl << endl;
	// j--;
	// ll ind = (*j);
	// ll dans = LS[i][ind];
	// ll ans = L[i].size() - dans;
	//cout << ans << endl;
	// return ans;
}

inline ll fastR(ll i, ll x) {
	seg good;
	good.l = 0; good.r = x - 1;
	ll j = (lower_bound(R[i].begin(), R[i].end(), good, cmpsz) - R[i].begin());
	return R[i].size() - j;
	// auto j = R1[i].lower_bound(x);
	// if (j == R1[i].begin()) {
	// 	return R[i].size();
	// }
	// // for (ll q = 0; q < L[i].size(); q++) {
	// // 	cout << L[i][q].sz() << " ";
	// // }
	// // cout << endl;
	// // cout << endl << endl;
	// j--;
	// ll ind = (*j);
	// // cout << "IND " << ind << endl; 
	// ll dans = RS[i][ind];
	// ll ans = R[i].size() - dans;
	// return ans;
}

map <pll, ll> ANSL;

map <pll, ll> ANSR;

inline ll getansL(ll x, ll l) {
	ll q;
	pll p = mp(x, l);
	if (ANSL.find(p) != ANSL.end()) {
		return ANSL[p];
	}
	// cout << "L " << l << endl;
	ll ans = 0;
	for (q = 0; q < block; q++) {
		// if (MNL[q] != inf)cout << MNL[q] << " " << MXL[q] << " " << q << " MNL" << endl;
		if (MNL[q] == inf) {
			continue;
		}
		if (MNL[q] >= l) {
			ans += fastL(q, x);
			continue;
		}
		if (MXL[q] < l) {
			// cout << "UMOM " << endl;
			continue;
		}
		if (MNL[q] < l) {
			ans += slowL(q, x, l);
		}
	}
	// if (ans != 0) {
	// 	exit(-1);
	// }
	for (q = 0; q < lasts.size(); q++) {
		if (used[lasts[q].i]) {
			continue;
		}
		if (lasts[q].l >= l && lasts[q].sz() >= x) {
			ans++;
		}
	}
	ANSL[p] = ans;
	return ans;
}

inline ll getansR(ll x, ll r) {
	ll q;
	pll p = mp(x, r);
	if (ANSR.find(p) != ANSR.end()) {
		return ANSR[p];
	}
	//cout << "X R " << x << " " << r << endl;
	ll ans = 0;
	for (q = 0; q < block; q++) {
		// if (R[q].size() != 0)cout << "SZ " << R[q].size() << " " << q << endl;
		if (MNR[q] == inf) {
			continue;
		}
		if (MXR[q] <= r) {
			ll dans = fastR(q, x);
			// if (dans != 0)cout << "DANS1 " << q << " " << dans << endl;
			ans += dans;
			continue;
		}
		if (MNR[q] > r) {
			continue;
		}
		ll dans = slowR(q, x, r);
		// if (dans != 0)cout << "DANS2 " << q << " " << dans << endl;
		ans += dans;
	}
	for (q = 0; q < lasts.size(); q++) {
		if (used[lasts[q].i]) {
			continue;
		}
		if (lasts[q].r <= r && lasts[q].sz() >= x) {
			// cout << "DANS3 " << lasts[q].i << " " << 1 << endl;
			ans++;
		}
	}
	ANSR[p] = ans;
	// cout << "ANS " << ans << endl << endl;
	return ans;
}

inline ll answer(seg c, ll k) {
	if (c.sz() < k) {
		return 0;
	}
	ll q, w;
	ll ans = 0;
	// for (q = 0; q < lasts.size(); q++) {
	// 	if (used[lasts[q].i]) {
	// 		continue;
	// 	}
	// 	ll li = max(lasts[q].l, c.l), ri = min(lasts[q].r, c.r);
	// 	if (ri - li + 1 >= k) {
	// 		ans++;
	// 	}
	// }
	// return ans;
	ll lk = c.r - k + 2, rk = c.l + k - 2;
	ll allans = getansR(k, inf);
	ll dansl = getansL(k, lk);
	// cout << "SMERT" << endl;
	ll dansr = getansR(k, rk);
	// cout << "DEBUG " << allans << " " << dansl << " " << dansr << endl;
	ans = allans - dansr - dansl;
	return ans;
}

signed main() {
	ll q, w, e, a, b, c;
	pyshnapyshnakaa;
	// cout << "BLOCKSZ " << block_sz << endl;
	cin >> n >> t;
	ll nxt = 0;
	ll lastans = 0;
	for (q = 0; q < n; q++) {
		ll comm;
		cin >> comm;
		ll l, r;
		seg x;
		if (comm == 1) {
			cin >> l >> r;
			l ^= (lastans * t);
			r ^= (lastans * t);
			if (l > r) {
				swap(l, r);
			}
			x.l = l; x.r = r;
			x.i = S.size();
			add(x);
		}
		if (comm == 2) {
			cin >> a;
			a--;
			del(S[a]);
		}
		if (comm == 3) {
			cin >> l >> r;
			l ^= (lastans * t);
			r ^= (lastans * t);
			if (lasts.size() >= block_sz) {
				rebuild();
			}
			if (l > r) {
				swap(l, r);
			} 
			x.l = l; x.r = r;
			cin >> c;
			lastans = answer(x, c);
			cout << lastans << '\n';
		}
		else {
			ANSL.clear();
			ANSR.clear();
		}
		// cout << "Q " << q << endl;
	}
	return 0;
}

Compilation message (stderr)

segments.cpp:7:0: warning: ignoring #pragma optimize  [-Wunknown-pragmas]
 #pragma optimize("TKACHENKO-GORYACHENKO")
 
segments.cpp:11:0: warning: "_FORTIFY_SOURCE" redefined
 #define _FORTIFY_SOURCE 0
 
<built-in>: note: this is the location of the previous definition
segments.cpp: In function 'void buildL(ll)':
segments.cpp:122:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (w = 0; w < L[q].size(); w++) {
              ~~^~~~~~~~~~~~~
segments.cpp: In function 'void buildR(ll)':
segments.cpp:142:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (w = 0; w < R[q].size(); w++) {
              ~~^~~~~~~~~~~~~
segments.cpp: In function 'void rebuild()':
segments.cpp:163:8: warning: unused variable 'w' [-Wunused-variable]
  ll q, w;
        ^
segments.cpp: In function 'll slowL(ll, ll, ll)':
segments.cpp:276:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (q = 0; q < L[i].size(); q++) {
              ~~^~~~~~~~~~~~~
segments.cpp: In function 'll slowR(ll, ll, ll)':
segments.cpp:290:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (q = 0; q < R[i].size(); q++) {
              ~~^~~~~~~~~~~~~
segments.cpp: In function 'll getansL(ll, ll)':
segments.cpp:375:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (q = 0; q < lasts.size(); q++) {
              ~~^~~~~~~~~~~~~~
segments.cpp: In function 'll getansR(ll, ll)':
segments.cpp:413:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (q = 0; q < lasts.size(); q++) {
              ~~^~~~~~~~~~~~~~
segments.cpp: In function 'll answer(seg, ll)':
segments.cpp:431:5: warning: unused variable 'q' [-Wunused-variable]
  ll q, w;
     ^
segments.cpp:431:8: warning: unused variable 'w' [-Wunused-variable]
  ll q, w;
        ^
segments.cpp: In function 'int main()':
segments.cpp:454:8: warning: unused variable 'w' [-Wunused-variable]
  ll q, w, e, a, b, c;
        ^
segments.cpp:454:11: warning: unused variable 'e' [-Wunused-variable]
  ll q, w, e, a, b, c;
           ^
segments.cpp:454:17: warning: unused variable 'b' [-Wunused-variable]
  ll q, w, e, a, b, c;
                 ^
segments.cpp:458:5: warning: unused variable 'nxt' [-Wunused-variable]
  ll nxt = 0;
     ^~~

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