oj.uz

Submission #160189

# Submission time Handle Problem Language Result Execution time Memory
160189 2019-10-26T09:54:31 Z pink_bittern Segments (IZhO18_segments) C++14
7 / 100
 5000 ms 23004 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 = 2e2; /// 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 380 KB Output is correct
3 Correct 8 ms 504 KB Output is correct
4 Correct 8 ms 504 KB Output is correct
5 Correct 24 ms 1656 KB Output is correct
6 Correct 26 ms 1528 KB Output is correct
7 Correct 249 ms 760 KB Output is correct
8 Correct 694 ms 1548 KB Output is correct
9 Correct 726 ms 1248 KB Output is correct
10 Correct 266 ms 1732 KB Output is correct
11 Correct 27 ms 1144 KB Output is correct
12 Correct 33 ms 1144 KB Output is correct
13 Correct 266 ms 1768 KB Output is correct
14 Correct 786 ms 1272 KB Output is correct
15 Correct 8 ms 504 KB Output is correct
16 Correct 12 ms 504 KB Output is correct
17 Correct 779 ms 836 KB Output is correct
18 Correct 459 ms 1532 KB Output is correct
19 Correct 961 ms 1128 KB Output is correct
20 Correct 999 ms 1180 KB Output is correct

Subtask #2
0 / 15.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 595 ms 2740 KB Output is correct
2 Correct 397 ms 2668 KB Output is correct
3 Correct 1125 ms 2760 KB Output is correct
4 Correct 520 ms 2816 KB Output is correct
5 Execution timed out 5010 ms 20876 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 2640 KB Output is correct
2 Correct 422 ms 2632 KB Output is correct
3 Correct 420 ms 2668 KB Output is correct
4 Correct 538 ms 2500 KB Output is correct
5 Execution timed out 5088 ms 23004 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 380 KB Output is correct
3 Correct 8 ms 504 KB Output is correct
4 Correct 8 ms 504 KB Output is correct
5 Correct 24 ms 1656 KB Output is correct
6 Correct 26 ms 1528 KB Output is correct
7 Correct 249 ms 760 KB Output is correct
8 Correct 694 ms 1548 KB Output is correct
9 Correct 726 ms 1248 KB Output is correct
10 Correct 266 ms 1732 KB Output is correct
11 Correct 27 ms 1144 KB Output is correct
12 Correct 33 ms 1144 KB Output is correct
13 Correct 266 ms 1768 KB Output is correct
14 Correct 786 ms 1272 KB Output is correct
15 Correct 8 ms 504 KB Output is correct
16 Correct 12 ms 504 KB Output is correct
17 Correct 779 ms 836 KB Output is correct
18 Correct 459 ms 1532 KB Output is correct
19 Correct 961 ms 1128 KB Output is correct
20 Correct 999 ms 1180 KB Output is correct
21 Execution timed out 5078 ms 14888 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 380 KB Output is correct
3 Correct 8 ms 504 KB Output is correct
4 Correct 8 ms 504 KB Output is correct
5 Correct 24 ms 1656 KB Output is correct
6 Correct 26 ms 1528 KB Output is correct
7 Correct 249 ms 760 KB Output is correct
8 Correct 694 ms 1548 KB Output is correct
9 Correct 726 ms 1248 KB Output is correct
10 Correct 266 ms 1732 KB Output is correct
11 Correct 27 ms 1144 KB Output is correct
12 Correct 33 ms 1144 KB Output is correct
13 Correct 266 ms 1768 KB Output is correct
14 Correct 786 ms 1272 KB Output is correct
15 Correct 8 ms 504 KB Output is correct
16 Correct 12 ms 504 KB Output is correct
17 Correct 779 ms 836 KB Output is correct
18 Correct 459 ms 1532 KB Output is correct
19 Correct 961 ms 1128 KB Output is correct
20 Correct 999 ms 1180 KB Output is correct
21 Execution timed out 5078 ms 14888 KB Time limit exceeded
22 Halted 0 ms 0 KB -