# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
41723 |
2018-02-21T04:17:40 Z |
aome |
Segments (IZhO18_segments) |
C++14 |
|
5000 ms |
1332 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
const int B = 1000;
int n, t, sz, lastans;
int cnt;
int L[N], R[N];
bool del[N];
vector<int> buf_add;
vector<int> buf_del;
vector<int> block_l[500];
vector<int> block_r[500];
vector< pair<int, int> > go;
void prep() {
go.clear();
for (int i = 1; i <= sz; ++i) {
if (!del[i]) go.push_back(make_pair(R[i] - L[i] + 1, i));
}
sort(go.begin(), go.end());
buf_add.clear(), buf_del.clear();
int m = go.size();
for (int i = 0; i <= m / B; ++i) block_l[i].clear(), block_r[i].clear();
for (int i = 0; i < m; ++i) block_l[i / B].push_back(L[go[i].second]);
for (int i = 0; i < m; ++i) block_r[i / B].push_back(R[go[i].second]);
for (int i = 0; i <= m / B; ++i) {
sort(block_l[i].begin(), block_l[i].end());
sort(block_r[i].begin(), block_r[i].end());
}
}
int calc(int id, int l, int r) {
// count number of commont points betweeen L[id], R[id] and l, r
if (L[id] > l) return max(0, min(r, R[id]) - L[id] + 1);
return max(0, min(R[id], r) - l + 1);
}
int calL(int l, int r, int x) {
// count number of segments from l -> r which has L > x
int res = 0;
int bl = l / B, br = r / B;
// if (bl == br) {
for (int i = l; i <= r; ++i) res += L[go[i].second] > x;
return res;
// }
for (int i = bl + 1; i < br; ++i) {
int tmp = lower_bound(block_l[i].begin(), block_l[i].end(), x + 1) - block_l[i].begin();
res += B - tmp + 1;
}
for (int i = l; i < (bl + 1) * B; ++i) res += L[go[i].second] > x;
for (int i = br * B; i <= r; ++i) res += L[go[i].second] > x;
return res;
}
int calR(int l, int r, int x) {
// count number of segments from l -> r which has R < x
int res = 0;
int bl = l / B, br = r / B;
// if (bl == br) {
for (int i = l; i <= r; ++i) res += R[go[i].second] < x;
return res;
// }
for (int i = bl + 1; i < br; ++i) {
int tmp = lower_bound(block_r[i].begin(), block_r[i].end(), x) - block_r[i].begin();
res += tmp;
}
for (int i = l; i < (bl + 1) * B; ++i) res += R[go[i].second] < x;
for (int i = br * B; i <= r; ++i) res += R[go[i].second] < x;
return res;
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> t;
for (int i = 1; i <= n; ++i) {
if (i % 1 == 0) prep();
int type; cin >> type;
if (type == 1) {
int l, r; cin >> l >> r;
l = l ^ (1LL * t * lastans);
r = r ^ (1LL * t * lastans);
if (l > r) swap(l, r);
++sz, L[sz] = l, R[sz] = r, buf_add.push_back(sz), cnt++;
}
if (type == 2) {
int x; cin >> x, buf_del.push_back(x), del[x] = 1, cnt--;
}
if (type == 3) {
int l, r, k;
cin >> l >> r >> k;
l = l ^ (1LL * t * lastans);
r = r ^ (1LL * t * lastans);
if (l > r) swap(l, r);
if (r - l + 1 < k) {
lastans = 0, cout << "0\n"; continue;
}
int res = 0;
// cout << "#add\n";
// for (auto j : buf_add) cout << j << ' '; cout << '\n';
// cout << "#del\n";
// for (auto j : buf_del) cout << j << ' '; cout << '\n';
for (auto j : buf_add) res += calc(j, l, r) < k;
for (auto j : buf_del) res -= calc(j, l, r) < k;
int p = lower_bound(go.begin(), go.end(), make_pair(k, 0)) - go.begin();
// cout << "#go\n";
// for (auto i : go) cout << i.second << ' '; cout << '\n';
// cout << "#p " << p << '\n';
// number of segments r - l + 1 < k
res += p;
// query p -> go.size() - 1 (segments with size >= k)
// count number of segments L > r - k + 1
res += calL(p, go.size() - 1, r - k + 1);
// count number of segments R < l + k - 1
res += calR(p, go.size() - 1, l + k - 1);
// cout << "#l-r " << l << ' ' << r << '\n';
// cout << "# " << res << '\n';
res = cnt - res, lastans = res;
cout << res << '\n';
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
480 KB |
Output is correct |
3 |
Correct |
24 ms |
560 KB |
Output is correct |
4 |
Correct |
14 ms |
620 KB |
Output is correct |
5 |
Correct |
2241 ms |
804 KB |
Output is correct |
6 |
Correct |
2164 ms |
932 KB |
Output is correct |
7 |
Correct |
513 ms |
932 KB |
Output is correct |
8 |
Correct |
1862 ms |
968 KB |
Output is correct |
9 |
Correct |
1764 ms |
968 KB |
Output is correct |
10 |
Correct |
2266 ms |
968 KB |
Output is correct |
11 |
Correct |
1714 ms |
968 KB |
Output is correct |
12 |
Correct |
1702 ms |
968 KB |
Output is correct |
13 |
Correct |
2261 ms |
1044 KB |
Output is correct |
14 |
Correct |
1666 ms |
1044 KB |
Output is correct |
15 |
Correct |
14 ms |
1044 KB |
Output is correct |
16 |
Correct |
34 ms |
1044 KB |
Output is correct |
17 |
Correct |
965 ms |
1148 KB |
Output is correct |
18 |
Correct |
2181 ms |
1148 KB |
Output is correct |
19 |
Correct |
1052 ms |
1148 KB |
Output is correct |
20 |
Correct |
1117 ms |
1148 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5071 ms |
1148 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3731 ms |
1332 KB |
Output is correct |
2 |
Correct |
2238 ms |
1332 KB |
Output is correct |
3 |
Execution timed out |
5100 ms |
1332 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2235 ms |
1332 KB |
Output is correct |
2 |
Correct |
2394 ms |
1332 KB |
Output is correct |
3 |
Correct |
2332 ms |
1332 KB |
Output is correct |
4 |
Correct |
2990 ms |
1332 KB |
Output is correct |
5 |
Execution timed out |
5082 ms |
1332 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
480 KB |
Output is correct |
3 |
Correct |
24 ms |
560 KB |
Output is correct |
4 |
Correct |
14 ms |
620 KB |
Output is correct |
5 |
Correct |
2241 ms |
804 KB |
Output is correct |
6 |
Correct |
2164 ms |
932 KB |
Output is correct |
7 |
Correct |
513 ms |
932 KB |
Output is correct |
8 |
Correct |
1862 ms |
968 KB |
Output is correct |
9 |
Correct |
1764 ms |
968 KB |
Output is correct |
10 |
Correct |
2266 ms |
968 KB |
Output is correct |
11 |
Correct |
1714 ms |
968 KB |
Output is correct |
12 |
Correct |
1702 ms |
968 KB |
Output is correct |
13 |
Correct |
2261 ms |
1044 KB |
Output is correct |
14 |
Correct |
1666 ms |
1044 KB |
Output is correct |
15 |
Correct |
14 ms |
1044 KB |
Output is correct |
16 |
Correct |
34 ms |
1044 KB |
Output is correct |
17 |
Correct |
965 ms |
1148 KB |
Output is correct |
18 |
Correct |
2181 ms |
1148 KB |
Output is correct |
19 |
Correct |
1052 ms |
1148 KB |
Output is correct |
20 |
Correct |
1117 ms |
1148 KB |
Output is correct |
21 |
Execution timed out |
5071 ms |
1148 KB |
Time limit exceeded |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
480 KB |
Output is correct |
3 |
Correct |
24 ms |
560 KB |
Output is correct |
4 |
Correct |
14 ms |
620 KB |
Output is correct |
5 |
Correct |
2241 ms |
804 KB |
Output is correct |
6 |
Correct |
2164 ms |
932 KB |
Output is correct |
7 |
Correct |
513 ms |
932 KB |
Output is correct |
8 |
Correct |
1862 ms |
968 KB |
Output is correct |
9 |
Correct |
1764 ms |
968 KB |
Output is correct |
10 |
Correct |
2266 ms |
968 KB |
Output is correct |
11 |
Correct |
1714 ms |
968 KB |
Output is correct |
12 |
Correct |
1702 ms |
968 KB |
Output is correct |
13 |
Correct |
2261 ms |
1044 KB |
Output is correct |
14 |
Correct |
1666 ms |
1044 KB |
Output is correct |
15 |
Correct |
14 ms |
1044 KB |
Output is correct |
16 |
Correct |
34 ms |
1044 KB |
Output is correct |
17 |
Correct |
965 ms |
1148 KB |
Output is correct |
18 |
Correct |
2181 ms |
1148 KB |
Output is correct |
19 |
Correct |
1052 ms |
1148 KB |
Output is correct |
20 |
Correct |
1117 ms |
1148 KB |
Output is correct |
21 |
Execution timed out |
5071 ms |
1148 KB |
Time limit exceeded |
22 |
Halted |
0 ms |
0 KB |
- |