oj.uz

Submission #161299

# Submission time Handle Problem Language Result Execution time Memory
161299 2019-11-01T18:35:17 Z pink_bittern Segments (IZhO18_segments) C++14
22 / 100
 5000 ms 10640 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("Ofast")
// #pragma GCC optimize("unroll-loops")
 
typedef int ll;
 
typedef long double ld;
 
using namespace std;
 
const ll inf = 2e9 + 500;
const ll maxn = 2e5 + 100;
const ll block = 100;
const ll block_sz = 3000;
 
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;
 
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();
}
 
vector <seg> segs;
 
vector <seg> R[block];
 
vector <seg> L[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);
	}
}
 
inline void buildR(ll q) {
	ll w;
 	MNR[q] = inf;
	MXR[q] = -inf;
	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);
	}
}
 
inline void rebuild() { 
	ll q, w;
	lasts.clear();
	ll blocki = 0;
	for (q = 0; q < block; q++) {
		R[q].clear();
		L[q].clear();
	}
	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);
	}
	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.push_back(a);
	IL[a.i] = IR[a.i] = -1;
}
 
inline void del(seg b) { 
	ll il = IL[b.i], ir = IR[b.i];
	if (used[b.i]) {
		return;
	}
	used[b.i] = 1;
	if (il == -1) {
		return;
	}
	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);
}
 
inline ll slowL(ll i, ll x, ll l) {
	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) {
	if (L[i].empty()) {
		return 0;
	}
	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;
}
 
inline ll fastR(ll i, ll x) {
	if (R[i].empty()) {
		return 0;
	}
	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;
}
 
inline ll getansL(ll x, ll l) {
	ll q;
	ll ans = 0;
	for (q = 0; q < block; q++) {
		if (MNL[q] == inf) {
			continue;
		}
		if (MNL[q] >= l) {
			ans += fastL(q, x);
			continue;
		}
		if (MXL[q] < l) {
			continue;
		}
		if (MNL[q] < l) {
			ans += slowL(q, x, l);
		}
	}
 
	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;
	ll ans = 0;
	ll cnt = 0;
	for (q = 0; q < block; q++) {
		if (MNR[q] == inf) {
			continue;
		}
		// if (q > 1) {
		// 	if (MXR[q - 1] > MNR[q]) {
		// 		exit(-1);
		// 	}
		// }
		if (MXR[q] <= r) {
			ll dans = fastR(q, x);
			ans += dans;
			continue;
		}
		if (MNR[q] > r) {
			continue;
		}
		/// MXR[q] > r && MNR[q] <= r, 
		ll dans = slowR(q, x, r);
		ans += dans;
		cnt++;
	}
	// if (cnt > 5) {
	// 	exit(-1);
	// }
	for (q = 0; q < lasts.size(); q++) {
		if (used[lasts[q].i]) {
			continue;
		}
		if (lasts[q].r <= r && lasts[q].sz() >= x) {
			ans++;
		}
	}
	return ans;
}
 
inline ll answer(seg c, ll k) {
	if (c.sz() < k) {
		return 0;
	}
	ll q, w;
	ll ans = 0;
	ll lk = c.r - k + 2, rk = c.l + k - 2;
	ll allans = getansR(k, inf);
	ll dansl = getansL(k, lk);
	ll dansr = getansR(k, rk);
	ans = allans - dansr - dansl;
	return ans;
}
 
signed main() {
	ll q, w, e, a, b, c;
	pyshnapyshnakaa;
	cin >> n >> t;
	// cout << block_sz * block << endl;
	ll nxt = 0;
	ll lastans = 0;
	ll cnt3 = 0;
	for (q = 0; q < block; q++) {
		L[q].reserve(block_sz);
		R[q].reserve(block_sz);
	}
	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 (cnt3 > 8e4 && n > 1e5) {
		// 	exit(-1);
		// }
		if (comm == 3) {
			cnt3++;
			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';
		}
	}
	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:97: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:108: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:115:8: warning: unused variable 'w' [-Wunused-variable]
  ll q, w;
        ^
segments.cpp: In function 'll slowL(ll, ll, ll)':
segments.cpp:177: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:188: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:235: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:275: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:290:5: warning: unused variable 'q' [-Wunused-variable]
  ll q, w;
     ^
segments.cpp:290:8: warning: unused variable 'w' [-Wunused-variable]
  ll q, w;
        ^
segments.cpp: In function 'int main()':
segments.cpp:301:8: warning: unused variable 'w' [-Wunused-variable]
  ll q, w, e, a, b, c;
        ^
segments.cpp:301:11: warning: unused variable 'e' [-Wunused-variable]
  ll q, w, e, a, b, c;
           ^
segments.cpp:301:17: warning: unused variable 'b' [-Wunused-variable]
  ll q, w, e, a, b, c;
                 ^
segments.cpp:305:5: warning: unused variable 'nxt' [-Wunused-variable]
  ll nxt = 0;
     ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 11 ms 1400 KB Output is correct
4 Correct 10 ms 1400 KB Output is correct
5 Correct 22 ms 1784 KB Output is correct
6 Correct 29 ms 1656 KB Output is correct
7 Correct 42 ms 1528 KB Output is correct
8 Correct 107 ms 1528 KB Output is correct
9 Correct 82 ms 1528 KB Output is correct
10 Correct 48 ms 1784 KB Output is correct
11 Correct 70 ms 1556 KB Output is correct
12 Correct 69 ms 1568 KB Output is correct
13 Correct 49 ms 1784 KB Output is correct
14 Correct 67 ms 1528 KB Output is correct
15 Correct 12 ms 1404 KB Output is correct
16 Correct 13 ms 1404 KB Output is correct
17 Correct 46 ms 1528 KB Output is correct
18 Correct 81 ms 1748 KB Output is correct
19 Correct 44 ms 1532 KB Output is correct
20 Correct 45 ms 1544 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1480 ms 7068 KB Output is correct
2 Correct 1449 ms 6944 KB Output is correct
3 Correct 1433 ms 6876 KB Output is correct
4 Correct 1357 ms 7460 KB Output is correct
5 Correct 271 ms 10384 KB Output is correct
6 Correct 187 ms 10640 KB Output is correct
7 Correct 1434 ms 7084 KB Output is correct
8 Correct 1487 ms 7072 KB Output is correct
9 Correct 1434 ms 6952 KB Output is correct
10 Correct 1961 ms 4264 KB Output is correct
11 Correct 1955 ms 5036 KB Output is correct
12 Correct 958 ms 8604 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 3736 KB Output is correct
2 Correct 284 ms 3584 KB Output is correct
3 Correct 413 ms 3664 KB Output is correct
4 Correct 295 ms 3584 KB Output is correct
5 Correct 754 ms 8556 KB Output is correct
6 Correct 1004 ms 7712 KB Output is correct
7 Correct 885 ms 7992 KB Output is correct
8 Correct 225 ms 10384 KB Output is correct
9 Correct 1095 ms 10384 KB Output is correct
10 Correct 3290 ms 8504 KB Output is correct
11 Correct 2463 ms 3996 KB Output is correct
12 Correct 3187 ms 8480 KB Output is correct
13 Correct 4030 ms 8240 KB Output is correct
14 Execution timed out 5048 ms 5540 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 3608 KB Output is correct
2 Correct 290 ms 3600 KB Output is correct
3 Correct 299 ms 3584 KB Output is correct
4 Correct 325 ms 3692 KB Output is correct
5 Correct 754 ms 8904 KB Output is correct
6 Correct 1966 ms 3624 KB Output is correct
7 Correct 588 ms 9364 KB Output is correct
8 Correct 2058 ms 4392 KB Output is correct
9 Execution timed out 5011 ms 6024 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 11 ms 1400 KB Output is correct
4 Correct 10 ms 1400 KB Output is correct
5 Correct 22 ms 1784 KB Output is correct
6 Correct 29 ms 1656 KB Output is correct
7 Correct 42 ms 1528 KB Output is correct
8 Correct 107 ms 1528 KB Output is correct
9 Correct 82 ms 1528 KB Output is correct
10 Correct 48 ms 1784 KB Output is correct
11 Correct 70 ms 1556 KB Output is correct
12 Correct 69 ms 1568 KB Output is correct
13 Correct 49 ms 1784 KB Output is correct
14 Correct 67 ms 1528 KB Output is correct
15 Correct 12 ms 1404 KB Output is correct
16 Correct 13 ms 1404 KB Output is correct
17 Correct 46 ms 1528 KB Output is correct
18 Correct 81 ms 1748 KB Output is correct
19 Correct 44 ms 1532 KB Output is correct
20 Correct 45 ms 1544 KB Output is correct
21 Correct 1480 ms 7068 KB Output is correct
22 Correct 1449 ms 6944 KB Output is correct
23 Correct 1433 ms 6876 KB Output is correct
24 Correct 1357 ms 7460 KB Output is correct
25 Correct 271 ms 10384 KB Output is correct
26 Correct 187 ms 10640 KB Output is correct
27 Correct 1434 ms 7084 KB Output is correct
28 Correct 1487 ms 7072 KB Output is correct
29 Correct 1434 ms 6952 KB Output is correct
30 Correct 1961 ms 4264 KB Output is correct
31 Correct 1955 ms 5036 KB Output is correct
32 Correct 958 ms 8604 KB Output is correct
33 Correct 291 ms 3608 KB Output is correct
34 Correct 290 ms 3600 KB Output is correct
35 Correct 299 ms 3584 KB Output is correct
36 Correct 325 ms 3692 KB Output is correct
37 Correct 754 ms 8904 KB Output is correct
38 Correct 1966 ms 3624 KB Output is correct
39 Correct 588 ms 9364 KB Output is correct
40 Correct 2058 ms 4392 KB Output is correct
41 Execution timed out 5011 ms 6024 KB Time limit exceeded
42 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 11 ms 1400 KB Output is correct
4 Correct 10 ms 1400 KB Output is correct
5 Correct 22 ms 1784 KB Output is correct
6 Correct 29 ms 1656 KB Output is correct
7 Correct 42 ms 1528 KB Output is correct
8 Correct 107 ms 1528 KB Output is correct
9 Correct 82 ms 1528 KB Output is correct
10 Correct 48 ms 1784 KB Output is correct
11 Correct 70 ms 1556 KB Output is correct
12 Correct 69 ms 1568 KB Output is correct
13 Correct 49 ms 1784 KB Output is correct
14 Correct 67 ms 1528 KB Output is correct
15 Correct 12 ms 1404 KB Output is correct
16 Correct 13 ms 1404 KB Output is correct
17 Correct 46 ms 1528 KB Output is correct
18 Correct 81 ms 1748 KB Output is correct
19 Correct 44 ms 1532 KB Output is correct
20 Correct 45 ms 1544 KB Output is correct
21 Correct 1480 ms 7068 KB Output is correct
22 Correct 1449 ms 6944 KB Output is correct
23 Correct 1433 ms 6876 KB Output is correct
24 Correct 1357 ms 7460 KB Output is correct
25 Correct 271 ms 10384 KB Output is correct
26 Correct 187 ms 10640 KB Output is correct
27 Correct 1434 ms 7084 KB Output is correct
28 Correct 1487 ms 7072 KB Output is correct
29 Correct 1434 ms 6952 KB Output is correct
30 Correct 1961 ms 4264 KB Output is correct
31 Correct 1955 ms 5036 KB Output is correct
32 Correct 958 ms 8604 KB Output is correct
33 Correct 332 ms 3736 KB Output is correct
34 Correct 284 ms 3584 KB Output is correct
35 Correct 413 ms 3664 KB Output is correct
36 Correct 295 ms 3584 KB Output is correct
37 Correct 754 ms 8556 KB Output is correct
38 Correct 1004 ms 7712 KB Output is correct
39 Correct 885 ms 7992 KB Output is correct
40 Correct 225 ms 10384 KB Output is correct
41 Correct 1095 ms 10384 KB Output is correct
42 Correct 3290 ms 8504 KB Output is correct
43 Correct 2463 ms 3996 KB Output is correct
44 Correct 3187 ms 8480 KB Output is correct
45 Correct 4030 ms 8240 KB Output is correct
46 Execution timed out 5048 ms 5540 KB Time limit exceeded
47 Halted 0 ms 0 KB -