oj.uz

Submission #160188

# Submission time Handle Problem Language Result Execution time Memory
160188 2019-10-26T09:50:49 Z pink_bittern Segments (IZhO18_segments) C++14
7 / 100
 5000 ms 12368 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 = 2e3; /// 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 4 ms 888 KB Output is correct
2 Correct 3 ms 888 KB Output is correct
3 Correct 29 ms 1016 KB Output is correct
4 Correct 32 ms 1016 KB Output is correct
5 Correct 110 ms 2272 KB Output is correct
6 Correct 119 ms 2040 KB Output is correct
7 Correct 142 ms 1296 KB Output is correct
8 Correct 163 ms 1900 KB Output is correct
9 Correct 168 ms 1704 KB Output is correct
10 Correct 118 ms 2308 KB Output is correct
11 Correct 120 ms 1700 KB Output is correct
12 Correct 120 ms 1656 KB Output is correct
13 Correct 123 ms 2304 KB Output is correct
14 Correct 226 ms 1628 KB Output is correct
15 Correct 29 ms 1016 KB Output is correct
16 Correct 39 ms 1016 KB Output is correct
17 Correct 167 ms 1420 KB Output is correct
18 Correct 143 ms 2236 KB Output is correct
19 Correct 172 ms 1400 KB Output is correct
20 Correct 178 ms 1616 KB Output is correct

Subtask #2
0 / 15.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3303 ms 3168 KB Output is correct
2 Correct 2904 ms 3288 KB Output is correct
3 Correct 3671 ms 3016 KB Output is correct
4 Correct 3045 ms 3284 KB Output is correct
5 Execution timed out 5008 ms 12220 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3120 ms 2968 KB Output is correct
2 Correct 2970 ms 3216 KB Output is correct
3 Correct 2940 ms 3372 KB Output is correct
4 Correct 3171 ms 3216 KB Output is correct
5 Execution timed out 5017 ms 12112 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 888 KB Output is correct
2 Correct 3 ms 888 KB Output is correct
3 Correct 29 ms 1016 KB Output is correct
4 Correct 32 ms 1016 KB Output is correct
5 Correct 110 ms 2272 KB Output is correct
6 Correct 119 ms 2040 KB Output is correct
7 Correct 142 ms 1296 KB Output is correct
8 Correct 163 ms 1900 KB Output is correct
9 Correct 168 ms 1704 KB Output is correct
10 Correct 118 ms 2308 KB Output is correct
11 Correct 120 ms 1700 KB Output is correct
12 Correct 120 ms 1656 KB Output is correct
13 Correct 123 ms 2304 KB Output is correct
14 Correct 226 ms 1628 KB Output is correct
15 Correct 29 ms 1016 KB Output is correct
16 Correct 39 ms 1016 KB Output is correct
17 Correct 167 ms 1420 KB Output is correct
18 Correct 143 ms 2236 KB Output is correct
19 Correct 172 ms 1400 KB Output is correct
20 Correct 178 ms 1616 KB Output is correct
21 Execution timed out 5074 ms 12368 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 888 KB Output is correct
2 Correct 3 ms 888 KB Output is correct
3 Correct 29 ms 1016 KB Output is correct
4 Correct 32 ms 1016 KB Output is correct
5 Correct 110 ms 2272 KB Output is correct
6 Correct 119 ms 2040 KB Output is correct
7 Correct 142 ms 1296 KB Output is correct
8 Correct 163 ms 1900 KB Output is correct
9 Correct 168 ms 1704 KB Output is correct
10 Correct 118 ms 2308 KB Output is correct
11 Correct 120 ms 1700 KB Output is correct
12 Correct 120 ms 1656 KB Output is correct
13 Correct 123 ms 2304 KB Output is correct
14 Correct 226 ms 1628 KB Output is correct
15 Correct 29 ms 1016 KB Output is correct
16 Correct 39 ms 1016 KB Output is correct
17 Correct 167 ms 1420 KB Output is correct
18 Correct 143 ms 2236 KB Output is correct
19 Correct 172 ms 1400 KB Output is correct
20 Correct 178 ms 1616 KB Output is correct
21 Execution timed out 5074 ms 12368 KB Time limit exceeded
22 Halted 0 ms 0 KB -