oj.uz

Submission #160190

# Submission time Handle Problem Language Result Execution time Memory
160190 2019-10-26T09:55:29 Z pink_bittern Segments (IZhO18_segments) C++14
7 / 100
 5000 ms 29196 KB 
#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("unroll-loops")
 
typedef int ll;
 
typedef long double ld;

using namespace std;

const ll inf = 2e9 + 500;
const ll maxn = 3e5;
const ll block = 1e2; /// 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;
	ll sz;
	ll i;
};

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

vector <seg> S;

vector <seg> segs;

vector <seg> lasts;

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

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

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

ll LASTL[block];

ll LASTR[block];

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;
	LS[q].clear();
	L1[q].clear();
	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();
	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 (q != 0) {
			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(), 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++) {
		buildL(q);
	}
	for (q = 0; q < block; q++) {
		buildR(q);
	}
}

inline void add(seg a) {
	lasts.pb(a);
	S.pb(a);
	segs.pb(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];
	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; 
	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;
	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) {
	auto j = L1[i].lower_bound(x);
	if (j == L1[i].begin()) {
		return L[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);
	ll dans = LS[i][ind];
	ll ans = L[i].size() - dans;
	//cout << ans << endl;
	return ans;
}

inline ll fastR(ll i, ll x) {
	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;
}


inline ll getansL(ll x, ll l) {
	ll q;
	// 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++;
		}
	}
	return ans;
}

inline ll getansR(ll x, ll r) {
	ll q;
	//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;
		}
		if (MXR[q] > r) {
			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++;
		}
	}
	// 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 lastans = 0;
	for (q = 0; q < n; q++) {
		ll comm;
		if (q % block_sz == 0) {
			rebuild();
		}
		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.sz = r - l + 1;
			x.i = segs.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 (l > r) {
				swap(l, r);
			} 
			x.l = l; x.r = r;
			x.sz = x.r - x.l + 1;
			cin >> c;
			lastans = answer(x, c);
			cout << lastans << '\n';
		}
		// cout << "Q " << q << endl;
	}
	return 0;
}

Compilation message

segments.cpp:7:0: warning: ignoring #pragma optimize  [-Wunknown-pragmas]
 #pragma optimize("TKACHENKO-GORYACHENKO")
 
segments.cpp: In function 'void buildL(ll)':
segments.cpp:86: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:105: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:134:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (q = 0; q < segs.size(); q++) {
              ~~^~~~~~~~~~~~~
segments.cpp:150:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (q = 0; q < segs.size(); q++) {
              ~~^~~~~~~~~~~~~
segments.cpp:126:8: warning: unused variable 'w' [-Wunused-variable]
  ll q, w;
        ^
segments.cpp: In function 'll slowL(ll, ll, ll)':
segments.cpp:205: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:216: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:285: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:320: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:337:5: warning: unused variable 'q' [-Wunused-variable]
  ll q, w;
     ^
segments.cpp:337:8: warning: unused variable 'w' [-Wunused-variable]
  ll q, w;
        ^
segments.cpp: In function 'int main()':
segments.cpp:360:8: warning: unused variable 'w' [-Wunused-variable]
  ll q, w, e, a, b, c;
        ^
segments.cpp:360:11: warning: unused variable 'e' [-Wunused-variable]
  ll q, w, e, a, b, c;
           ^
segments.cpp:360:17: warning: unused variable 'b' [-Wunused-variable]
  ll q, w, e, a, b, c;
                 ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 8 ms 504 KB Output is correct
4 Correct 8 ms 504 KB Output is correct
5 Correct 21 ms 1400 KB Output is correct
6 Correct 23 ms 1400 KB Output is correct
7 Correct 140 ms 684 KB Output is correct
8 Correct 1346 ms 1304 KB Output is correct
9 Correct 1262 ms 1436 KB Output is correct
10 Correct 361 ms 1400 KB Output is correct
11 Correct 28 ms 1272 KB Output is correct
12 Correct 28 ms 1148 KB Output is correct
13 Correct 426 ms 1528 KB Output is correct
14 Correct 1257 ms 1272 KB Output is correct
15 Correct 8 ms 504 KB Output is correct
16 Correct 11 ms 508 KB Output is correct
17 Correct 335 ms 860 KB Output is correct
18 Correct 840 ms 1540 KB Output is correct
19 Correct 463 ms 972 KB Output is correct
20 Correct 445 ms 1016 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5101 ms 14672 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 2528 KB Output is correct
2 Correct 278 ms 2584 KB Output is correct
3 Correct 819 ms 2692 KB Output is correct
4 Correct 302 ms 2536 KB Output is correct
5 Correct 4454 ms 20752 KB Output is correct
6 Correct 4639 ms 20168 KB Output is correct
7 Correct 4598 ms 21392 KB Output is correct
8 Correct 3353 ms 29196 KB Output is correct
9 Execution timed out 5015 ms 28044 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 2576 KB Output is correct
2 Correct 297 ms 2648 KB Output is correct
3 Correct 298 ms 2700 KB Output is correct
4 Correct 350 ms 2576 KB Output is correct
5 Execution timed out 5009 ms 22588 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 8 ms 504 KB Output is correct
4 Correct 8 ms 504 KB Output is correct
5 Correct 21 ms 1400 KB Output is correct
6 Correct 23 ms 1400 KB Output is correct
7 Correct 140 ms 684 KB Output is correct
8 Correct 1346 ms 1304 KB Output is correct
9 Correct 1262 ms 1436 KB Output is correct
10 Correct 361 ms 1400 KB Output is correct
11 Correct 28 ms 1272 KB Output is correct
12 Correct 28 ms 1148 KB Output is correct
13 Correct 426 ms 1528 KB Output is correct
14 Correct 1257 ms 1272 KB Output is correct
15 Correct 8 ms 504 KB Output is correct
16 Correct 11 ms 508 KB Output is correct
17 Correct 335 ms 860 KB Output is correct
18 Correct 840 ms 1540 KB Output is correct
19 Correct 463 ms 972 KB Output is correct
20 Correct 445 ms 1016 KB Output is correct
21 Execution timed out 5101 ms 14672 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 8 ms 504 KB Output is correct
4 Correct 8 ms 504 KB Output is correct
5 Correct 21 ms 1400 KB Output is correct
6 Correct 23 ms 1400 KB Output is correct
7 Correct 140 ms 684 KB Output is correct
8 Correct 1346 ms 1304 KB Output is correct
9 Correct 1262 ms 1436 KB Output is correct
10 Correct 361 ms 1400 KB Output is correct
11 Correct 28 ms 1272 KB Output is correct
12 Correct 28 ms 1148 KB Output is correct
13 Correct 426 ms 1528 KB Output is correct
14 Correct 1257 ms 1272 KB Output is correct
15 Correct 8 ms 504 KB Output is correct
16 Correct 11 ms 508 KB Output is correct
17 Correct 335 ms 860 KB Output is correct
18 Correct 840 ms 1540 KB Output is correct
19 Correct 463 ms 972 KB Output is correct
20 Correct 445 ms 1016 KB Output is correct
21 Execution timed out 5101 ms 14672 KB Time limit exceeded
22 Halted 0 ms 0 KB -