oj.uz

Submission #159990

# Submission time Handle Problem Language Result Execution time Memory
159990 2019-10-25T16:12:20 Z pink_bittern Segments (IZhO18_segments) C++14
0 / 100
 1599 ms 65540 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 = 5e3 + 10; /// cnt_of_blocks
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();
	for (w = 0; w < L[q].size(); w++) {
		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;
	RS[q].clear();
	R1[q].clear();
	for (w = 0; w < R[q].size(); w++) {
		RS[q][R[q][w].sz]++;
		R1[q].insert(R[q][w].sz);
	}
	ll s = 0;
	for (auto p : RS[q]){
		RS[q][p.first] += s;
		s = RS[q][p.first];
	}
}

void rebuild() {
	ll q, w;
	lasts.clear();
	ll blocki = 0;
	for (q = 0; q < block; q++) {
		MNL[q] = inf;
		MXL[q] = -inf;
		MNR[q] = inf;
		MXR[q] = -inf;
	}
	sort(segs.begin(), segs.end(), cmpl);
	for (q = 0; q < segs.size(); q++) {
		if (used[segs[q].i]) {
			continue;
		}
		if (q != 0) {
			if (L[blocki].size() > block_sz) {
				blocki++;
			}
		}
		MNL[blocki] = min(MNL[blocki], segs[q].l);
		MXL[blocki] = max(MXL[blocki], segs[q].l);
		IL[q] = 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;
		}
		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]);
	}
	for (q = 0; q < block; q++) {
		buildL(q);
	}
	for (q = 0; q < block; q++) {
		buildR(q);
	}
}

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

void del(seg b) {
	ll il = IL[b.i], ir = IR[b.i];
	used[b.i] = 1;
	if (il == -1) {
		return;
	}
	cout << il << " " << ir << 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);
}

ll fastL(ll i, ll x) {
	auto j = L1[i].upper_bound(x);
	if (j == L1[i].begin()) {
		return L[i].size();
	}
	j--;
	ll ind = (*j);
	ll dans = LS[i][ind];
	ll ans = L[i].size() - dans;
	return ans;
}

ll fastR(ll i, ll x) {
	auto j = R1[i].upper_bound(x);
	if (j == R1[i].begin()) {
		return R[i].size();
	}
	j--;
	ll ind = (*j);
	ll dans = RS[i][ind];
	ll ans = R[i].size() - dans;
	return ans;
}

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

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 getansL(ll x, ll l) {
	ll q;
	ll ans = 0;
	for (q = 0; q < block; q++) {
		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;
}

ll getansR(ll x, ll r) {
	ll q;
	ll ans = 0;
	for (q = 0; q < block; q++) {
		if (MXR[q] <= r) {
			ans += fastR(q, x);
			continue;
		}
		if (MNR[q] > r) {
			continue;
		}
		if (MXR[q] > r) {
			ans += slowR(q, x, r);
		}
	}
	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;
}

ll answer(seg c, ll k) {
	if (c.sz < k) {
		return 0;
	}
	ll q, w;
	ll lk = c.r - k + 2, rk = c.l + k - 2;
	ll allans = getansR(0, inf);
	ll dansl = getansL(k, lk);
	ll dansr = getansR(k, rk);
	ll ans = allans - dansr - dansl;
	return ans;
}

signed main() {
	ll q, w, e, a, b, c;
	cin >> n >> t;
	ll lastans = 0;
	for (q = 0; q < n; q++) {
		ll comm;
		if (q % block == 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]);
		}
		// cout << "Q " << q << endl;
		if (comm == 3) {
			cin >> l >> r;
			l ^= (lastans * t);
			r ^= (lastans * t);
			if (l > r) {
				swap(l, r);
			} 
			x.l = l; x.r = r;
			cin >> c;
			lastans = answer(x, c);
			cout << lastans << 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:83: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:98: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:120:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (q = 0; q < segs.size(); q++) {
              ~~^~~~~~~~~~~~~
segments.cpp:135:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (q = 0; q < segs.size(); q++) {
              ~~^~~~~~~~~~~~~
segments.cpp:110: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:239: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:265: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:280:5: warning: unused variable 'q' [-Wunused-variable]
  ll q, w;
     ^
segments.cpp:280:8: warning: unused variable 'w' [-Wunused-variable]
  ll q, w;
        ^
segments.cpp: In function 'int main()':
segments.cpp:290:8: warning: unused variable 'w' [-Wunused-variable]
  ll q, w, e, a, b, c;
        ^
segments.cpp:290:11: warning: unused variable 'e' [-Wunused-variable]
  ll q, w, e, a, b, c;
           ^
segments.cpp:290:17: warning: unused variable 'b' [-Wunused-variable]
  ll q, w, e, a, b, c;
                 ^

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1656 KB Output is correct
2 Correct 3 ms 1656 KB Output is correct
3 Incorrect 75 ms 1884 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 848 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 542 ms 5504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1599 ms 6408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1656 KB Output is correct
2 Correct 3 ms 1656 KB Output is correct
3 Incorrect 75 ms 1884 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1656 KB Output is correct
2 Correct 3 ms 1656 KB Output is correct
3 Incorrect 75 ms 1884 KB Output isn't correct
4 Halted 0 ms 0 KB -