oj.uz

Submission #160186

# Submission time Handle Problem Language Result Execution time Memory
160186 2019-10-26T09:48:32 Z pink_bittern Segments (IZhO18_segments) C++14
7 / 100
 5000 ms 16976 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 long long ll;
 
typedef long double ld;

using namespace std;

const ll inf = 1e15;
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;
};

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

vector <seg> S;

vector <seg> segs;

vector <seg> lasts;

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

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

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];

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];
	}
}

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;
}

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);
	}
}

void add(seg a) {
	lasts.pb(a);
	S.pb(a);
	segs.pb(a);
	IL[a.i] = IR[a.i] = -1;
}

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;
	// }
}

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;
}

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;
}

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;
}

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;
}


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;
}

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;
}

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;
	// 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 << endl;
		}
		// 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 888 KB Output is correct
2 Correct 2 ms 888 KB Output is correct
3 Correct 47 ms 1144 KB Output is correct
4 Correct 48 ms 1144 KB Output is correct
5 Correct 145 ms 3096 KB Output is correct
6 Correct 145 ms 2808 KB Output is correct
7 Correct 165 ms 1528 KB Output is correct
8 Correct 189 ms 2296 KB Output is correct
9 Correct 205 ms 2264 KB Output is correct
10 Correct 138 ms 2948 KB Output is correct
11 Correct 171 ms 2120 KB Output is correct
12 Correct 158 ms 1972 KB Output is correct
13 Correct 143 ms 2992 KB Output is correct
14 Correct 204 ms 2184 KB Output is correct
15 Correct 46 ms 1052 KB Output is correct
16 Correct 60 ms 1144 KB Output is correct
17 Correct 190 ms 1784 KB Output is correct
18 Correct 161 ms 2908 KB Output is correct
19 Correct 205 ms 1784 KB Output is correct
20 Correct 200 ms 1940 KB Output is correct

Subtask #2
0 / 15.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4673 ms 4996 KB Output is correct
2 Correct 4830 ms 5204 KB Output is correct
3 Execution timed out 5050 ms 5184 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 888 KB Output is correct
2 Correct 2 ms 888 KB Output is correct
3 Correct 47 ms 1144 KB Output is correct
4 Correct 48 ms 1144 KB Output is correct
5 Correct 145 ms 3096 KB Output is correct
6 Correct 145 ms 2808 KB Output is correct
7 Correct 165 ms 1528 KB Output is correct
8 Correct 189 ms 2296 KB Output is correct
9 Correct 205 ms 2264 KB Output is correct
10 Correct 138 ms 2948 KB Output is correct
11 Correct 171 ms 2120 KB Output is correct
12 Correct 158 ms 1972 KB Output is correct
13 Correct 143 ms 2992 KB Output is correct
14 Correct 204 ms 2184 KB Output is correct
15 Correct 46 ms 1052 KB Output is correct
16 Correct 60 ms 1144 KB Output is correct
17 Correct 190 ms 1784 KB Output is correct
18 Correct 161 ms 2908 KB Output is correct
19 Correct 205 ms 1784 KB Output is correct
20 Correct 200 ms 1940 KB Output is correct
21 Execution timed out 5079 ms 16976 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 888 KB Output is correct
2 Correct 2 ms 888 KB Output is correct
3 Correct 47 ms 1144 KB Output is correct
4 Correct 48 ms 1144 KB Output is correct
5 Correct 145 ms 3096 KB Output is correct
6 Correct 145 ms 2808 KB Output is correct
7 Correct 165 ms 1528 KB Output is correct
8 Correct 189 ms 2296 KB Output is correct
9 Correct 205 ms 2264 KB Output is correct
10 Correct 138 ms 2948 KB Output is correct
11 Correct 171 ms 2120 KB Output is correct
12 Correct 158 ms 1972 KB Output is correct
13 Correct 143 ms 2992 KB Output is correct
14 Correct 204 ms 2184 KB Output is correct
15 Correct 46 ms 1052 KB Output is correct
16 Correct 60 ms 1144 KB Output is correct
17 Correct 190 ms 1784 KB Output is correct
18 Correct 161 ms 2908 KB Output is correct
19 Correct 205 ms 1784 KB Output is correct
20 Correct 200 ms 1940 KB Output is correct
21 Execution timed out 5079 ms 16976 KB Time limit exceeded
22 Halted 0 ms 0 KB -