# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
683578 |
2023-01-18T18:44:14 Z |
opPO |
Segments (IZhO18_segments) |
C++17 |
|
162 ms |
19856 KB |
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define f first
#define s second
#define pb push_back
#define ld long double
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define vec vector
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using oset = tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
const ld eps = 1e-6;
const int mod = 998244353;
const int oo = 2e9;
const ll OO = 2e18;
const int N = 1e5 + 10;
struct Query
{
int type;
int a;
int b;
int k;
int id;
Query(int type, int a, int b) : type(type), a(a), b(b) {}
Query(int type, int id) : type(type), id(id) {}
Query(int type, int a, int b, int k) : type(type), a(a), b(b), k(k) {}
};
int intersection(pii a, pii b)
{
return max(0LL, min(a.s, b.s) - max(a.f, b.f) + 1);
}
void solve()
{
int q, t;
cin >> q >> t;
vec<Query> qs;
bool g3 = true;
for (int qr = 0; qr < q; qr++)
{
int type;
cin >> type;
if (type == 1)
{
int a, b;
cin >> a >> b;
qs.pb(Query(type, a, b));
}
else if (type == 2)
{
int id;
cin >> id;
qs.pb(Query(type, id));
}
else
{
int a, b, k;
cin >> a >> b >> k;
if (k != 1) g3 = false;
qs.pb(Query(type, a, b, k));
}
}
if (q <= 5e3)
{
vec<pii> segments;
vec<pii> seg_by_id(q + 1);
int ID = 0, last_ans = 0;
for (int qr = 0; qr < q; qr++)
{
Query Q = qs[qr];
if (Q.type == 1)
{
ID++;
int l = (Q.a ^ (t * last_ans)), r = (Q.b ^ (t * last_ans));
if (l > r) swap(l, r);
segments.pb({l, r});
seg_by_id[ID] = segments.back();
}
else if (Q.type == 2)
{
pii seg = seg_by_id[Q.id];
segments.erase(find(all(segments), seg));
}
else
{
int l = (Q.a ^ (t * last_ans)), r = (Q.b ^ (t * last_ans));
if (l > r) swap(l, r);
int res = 0;
for (auto &seg : segments) if (intersection(seg, {l, r}) >= Q.k) res++;
cout << res << "\n";
last_ans = res;
}
}
return;
}
if (g3)
{
vec<pii> seg_by_id(q + 1);
int ID = 0, last_ans = 0;
oset lefts, rights;
for (int qr = 0; qr < q; qr++)
{
Query Q = qs[qr];
if (Q.type == 1)
{
ID++;
int l = (Q.a ^ (t * last_ans)), r = (Q.b ^ (t * last_ans));
if (l > r) swap(l, r);
lefts.insert({l, ID});
rights.insert({r, ID});
seg_by_id[ID] = {l, r};
}
else if (Q.type == 2)
{
pii seg = seg_by_id[Q.id];
lefts.erase(lefts.lower_bound({seg.f, -OO}));
rights.erase(rights.lower_bound({seg.s, -OO}));
}
else
{
int l = (Q.a ^ (t * last_ans)), r = (Q.b ^ (t * last_ans));
if (l > r) swap(l, r);
int res = sz(lefts);
res -= rights.order_of_key({l, -OO});
res -= sz(lefts) - lefts.order_of_key({r + 1, -OO});
cout << res << "\n";
last_ans = res;
}
}
return;
}
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
2 ms |
692 KB |
Output is correct |
4 |
Correct |
2 ms |
692 KB |
Output is correct |
5 |
Correct |
9 ms |
804 KB |
Output is correct |
6 |
Correct |
13 ms |
692 KB |
Output is correct |
7 |
Correct |
4 ms |
692 KB |
Output is correct |
8 |
Correct |
7 ms |
692 KB |
Output is correct |
9 |
Correct |
7 ms |
712 KB |
Output is correct |
10 |
Correct |
4 ms |
784 KB |
Output is correct |
11 |
Correct |
12 ms |
724 KB |
Output is correct |
12 |
Correct |
12 ms |
732 KB |
Output is correct |
13 |
Correct |
4 ms |
784 KB |
Output is correct |
14 |
Correct |
6 ms |
692 KB |
Output is correct |
15 |
Correct |
2 ms |
692 KB |
Output is correct |
16 |
Correct |
2 ms |
692 KB |
Output is correct |
17 |
Correct |
5 ms |
692 KB |
Output is correct |
18 |
Correct |
5 ms |
692 KB |
Output is correct |
19 |
Correct |
5 ms |
692 KB |
Output is correct |
20 |
Correct |
5 ms |
692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
43 ms |
5552 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
48 ms |
5952 KB |
Output is correct |
2 |
Correct |
45 ms |
7692 KB |
Output is correct |
3 |
Correct |
49 ms |
7808 KB |
Output is correct |
4 |
Correct |
53 ms |
7760 KB |
Output is correct |
5 |
Correct |
132 ms |
17184 KB |
Output is correct |
6 |
Correct |
144 ms |
15840 KB |
Output is correct |
7 |
Correct |
114 ms |
16428 KB |
Output is correct |
8 |
Correct |
145 ms |
19856 KB |
Output is correct |
9 |
Correct |
154 ms |
19272 KB |
Output is correct |
10 |
Correct |
157 ms |
16028 KB |
Output is correct |
11 |
Correct |
78 ms |
8272 KB |
Output is correct |
12 |
Correct |
129 ms |
16364 KB |
Output is correct |
13 |
Correct |
113 ms |
15148 KB |
Output is correct |
14 |
Correct |
109 ms |
11576 KB |
Output is correct |
15 |
Correct |
93 ms |
10808 KB |
Output is correct |
16 |
Correct |
76 ms |
9780 KB |
Output is correct |
17 |
Correct |
96 ms |
14608 KB |
Output is correct |
18 |
Correct |
115 ms |
14688 KB |
Output is correct |
19 |
Correct |
121 ms |
14692 KB |
Output is correct |
20 |
Correct |
99 ms |
14692 KB |
Output is correct |
21 |
Correct |
66 ms |
8496 KB |
Output is correct |
22 |
Correct |
118 ms |
12396 KB |
Output is correct |
23 |
Correct |
133 ms |
14096 KB |
Output is correct |
24 |
Correct |
103 ms |
12876 KB |
Output is correct |
25 |
Correct |
46 ms |
7756 KB |
Output is correct |
26 |
Correct |
46 ms |
7664 KB |
Output is correct |
27 |
Correct |
50 ms |
7736 KB |
Output is correct |
28 |
Correct |
45 ms |
7744 KB |
Output is correct |
29 |
Correct |
114 ms |
14596 KB |
Output is correct |
30 |
Correct |
109 ms |
14632 KB |
Output is correct |
31 |
Correct |
162 ms |
19372 KB |
Output is correct |
32 |
Correct |
147 ms |
16176 KB |
Output is correct |
33 |
Correct |
135 ms |
15324 KB |
Output is correct |
34 |
Correct |
110 ms |
10724 KB |
Output is correct |
35 |
Correct |
112 ms |
13868 KB |
Output is correct |
36 |
Correct |
122 ms |
15896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
25 ms |
5572 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
2 ms |
692 KB |
Output is correct |
4 |
Correct |
2 ms |
692 KB |
Output is correct |
5 |
Correct |
9 ms |
804 KB |
Output is correct |
6 |
Correct |
13 ms |
692 KB |
Output is correct |
7 |
Correct |
4 ms |
692 KB |
Output is correct |
8 |
Correct |
7 ms |
692 KB |
Output is correct |
9 |
Correct |
7 ms |
712 KB |
Output is correct |
10 |
Correct |
4 ms |
784 KB |
Output is correct |
11 |
Correct |
12 ms |
724 KB |
Output is correct |
12 |
Correct |
12 ms |
732 KB |
Output is correct |
13 |
Correct |
4 ms |
784 KB |
Output is correct |
14 |
Correct |
6 ms |
692 KB |
Output is correct |
15 |
Correct |
2 ms |
692 KB |
Output is correct |
16 |
Correct |
2 ms |
692 KB |
Output is correct |
17 |
Correct |
5 ms |
692 KB |
Output is correct |
18 |
Correct |
5 ms |
692 KB |
Output is correct |
19 |
Correct |
5 ms |
692 KB |
Output is correct |
20 |
Correct |
5 ms |
692 KB |
Output is correct |
21 |
Incorrect |
43 ms |
5552 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
2 ms |
692 KB |
Output is correct |
4 |
Correct |
2 ms |
692 KB |
Output is correct |
5 |
Correct |
9 ms |
804 KB |
Output is correct |
6 |
Correct |
13 ms |
692 KB |
Output is correct |
7 |
Correct |
4 ms |
692 KB |
Output is correct |
8 |
Correct |
7 ms |
692 KB |
Output is correct |
9 |
Correct |
7 ms |
712 KB |
Output is correct |
10 |
Correct |
4 ms |
784 KB |
Output is correct |
11 |
Correct |
12 ms |
724 KB |
Output is correct |
12 |
Correct |
12 ms |
732 KB |
Output is correct |
13 |
Correct |
4 ms |
784 KB |
Output is correct |
14 |
Correct |
6 ms |
692 KB |
Output is correct |
15 |
Correct |
2 ms |
692 KB |
Output is correct |
16 |
Correct |
2 ms |
692 KB |
Output is correct |
17 |
Correct |
5 ms |
692 KB |
Output is correct |
18 |
Correct |
5 ms |
692 KB |
Output is correct |
19 |
Correct |
5 ms |
692 KB |
Output is correct |
20 |
Correct |
5 ms |
692 KB |
Output is correct |
21 |
Incorrect |
43 ms |
5552 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |