| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 213119 |
2020-03-25T03:20:15 Z |
qkxwsm |
Sweeping (JOI20_sweeping) |
C++14 |
|
723 ms |
159952 KB |
#include <bits/stdc++.h>
using namespace std;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
mt19937 rng(69);
template<class T>
T randomize(T mod)
{
return uniform_int_distribution<T>(0, mod - 1)(rng);
}
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
const int MAXN = 500013;
const int INF = 1000000007;
int N, M, Q;
int indexof(int v, vi &vec)
{
return UB(ALL(vec), v) - vec.begin() - 1;
}
bool cmp(pii a, pii b)
{
return (a.fi <= b.fi && a.se >= b.se);
}
struct node
{
node *ch[2], *p;
pii pos, lazy;
int pri;
node(int x, int y)
{
pos = {x, y};
lazy = {-1, -1};
pri = randomize(INF);
}
};
void push(node *t)
{
if (!t) return;
if (t -> lazy == MP(-1, -1)) return;
ckmax(t -> pos.fi, t -> lazy.fi);
ckmax(t -> pos.se, t -> lazy.se);
if (t -> ch[0])
{
ckmax(t -> ch[0] -> lazy.fi, t -> lazy.fi);
ckmax(t -> ch[0] -> lazy.se, t -> lazy.se);
assert(t -> ch[0] -> p == t);
}
if (t -> ch[1])
{
ckmax(t -> ch[1] -> lazy.fi, t -> lazy.fi);
ckmax(t -> ch[1] -> lazy.se, t -> lazy.se);
assert(t -> ch[1] -> p == t);
}
t -> lazy = {-1, -1};
return;
}
typedef pair<node*, node*> pnn;
pnn split(node* t, int v, bool dir)
{
//v goes to the right tho...
if (!t) return {nullptr, nullptr};
push(t);
if ((!dir && t -> pos.fi > v) || (dir && t -> pos.se < v))
{
// cerr << "left\n";
if (t -> ch[0]) t -> ch[0] -> p = nullptr;
pnn p = split(t -> ch[0], v, dir);
t -> ch[0] = p.se; if (t -> ch[0]) t -> ch[0] -> p = t;
return {p.fi, t};
}
else
{
// cerr << "right\n";
if (t -> ch[1]) t -> ch[1] -> p = nullptr;
pnn p = split(t -> ch[1], v, dir);
t -> ch[1] = p.fi; if (t -> ch[1]) t -> ch[1] -> p = t;
return {t, p.se};
}
}
pnn Split(node *t, pii v)
{
if (!t) return {nullptr, nullptr};
push(t);
if (cmp(v, t -> pos))
{
if (t -> ch[0]) t -> ch[0] -> p = nullptr;
pnn p = Split(t -> ch[0], v);
t -> ch[0] = p.se; if (t -> ch[0]) t -> ch[0] -> p = t;
return {p.fi, t};
}
else
{
if (t -> ch[1]) t -> ch[1] -> p = nullptr;
pnn p = Split(t -> ch[1], v);
t -> ch[1] = p.fi; if (t -> ch[1]) t -> ch[1] -> p = t;
return {t, p.se};
}
}
node *merge(node *l, node *r)
{
push(l); push(r);
if (!l) return r;
if (!r) return l;
// assert(l != r);
if (l -> pri > r -> pri)
{
l -> ch[1] = merge(l -> ch[1], r); if (l -> ch[1]) l -> ch[1] -> p = l;
return l;
}
else
{
r -> ch[0] = merge(l, r -> ch[0]); if (r -> ch[0]) r -> ch[0] -> p = r;
return r;
}
}
void get(node *t)
{
// vector<node*> vn;
// while(t)
// {
// vn.PB(t);
// t = t -> p;
// }
// reverse(ALL(vn));
// for (auto w : vn)
// {
// push(w);
// }
}
void inorder(node *t)
{
if (!t) return;
push(t);
inorder(t -> ch[0]);
cerr << t -> pos.fi << ',' << t -> pos.se << ',' << t -> pri << ' ';
inorder(t -> ch[1]);
}
node *root;
node *V[MAXN];
void ins(node *t, int idx)
{
// cerr << "ins " << t -> pos.fi << ',' << t -> pos.se << ' ' << idx << endl;
pnn p = Split(root, t -> pos);
root = merge(p.fi, merge(t, p.se));
}
struct segtree
{
int seg[2 * MAXN];
priority_queue<pii, vector<pii>, greater<pii> > pts[MAXN];
vi res;
void build(int w, int L, int R)
{
if (L == R)
{
seg[w] = (pts[L].empty() ? INF : pts[L].top().fi);
return;
}
int mid = (L + R) >> 1;
build(w << 1, L, mid);
build(w << 1 | 1, mid + 1, R);
seg[w] = min(seg[w << 1], seg[w << 1 | 1]);
}
void walk(int w, int L, int R, int a, int b, int v)
{
if (b < L || R < a || seg[w] > v) return;
if (L == R)
{
while(!pts[L].empty() && pts[L].top().fi <= v)
{
res.PB(pts[L].top().se);
pts[L].pop();
}
seg[w] = (pts[L].empty() ? INF : pts[L].top().fi);
return;
}
int mid = (L + R) >> 1;
walk(w << 1, L, mid, a, b, v);
walk(w << 1 | 1, mid + 1, R, a, b, v);
seg[w] = min(seg[w << 1], seg[w << 1 | 1]);
return;
}
};
segtree segx, segy;
vi cx, cy;
pii arr[MAXN];
int32_t main()
{
cout << fixed << setprecision(12);
cerr << fixed << setprecision(4);
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> N >> M >> Q;
FOR(i, 0, M)
{
pii p;
cin >> p.fi >> p.se;
cx.PB(p.fi);
cy.PB(p.se);
arr[i] = p;
}
sort(ALL(cx)); cx.erase(unique(ALL(cx)), cx.end());
sort(ALL(cy)); cy.erase(unique(ALL(cy)), cy.end());
FOR(i, 0, M)
{
int x = indexof(arr[i].fi, cx), y = indexof(arr[i].se, cy);
segx.pts[x].push({arr[i].se, i});
segy.pts[y].push({arr[i].fi, i});
}
segx.build(1, 0, SZ(cx) - 1);
segy.build(1, 0, SZ(cy) - 1);
while(Q--)
{
// cerr << "TREE\n";
// inorder(root); cerr << endl;
int typ, idx;
cin >> typ >> idx;
// cerr << "QUERY " << typ << ' ' << idx << endl;
if (typ == 1)
{
idx--;
if (idx >= M) continue;
// cerr << "idx = " << idx << endl;
if (arr[idx] == MP(-1, -1))
{
get(V[idx]);
pii p = V[idx] -> pos;
cout << p.fi << ' ' << p.se << '\n';
}
else
{
cout << arr[idx].fi << ' ' << arr[idx].se << '\n';
}
}
if (typ == 2)
{
//horizontal sweep.
segy.walk(1, 0, SZ(cy) - 1, 0, indexof(idx, cy), N - idx);
vi vec = segy.res; segy.res.clear();
for (int x : vec)
{
if (arr[x] == MP(-1, -1)) continue;
V[x] = new node(N - idx, arr[x].se);
ins(V[x], x);
arr[x] = MP(-1, -1);
}
// cerr << "horizontal " << idx << endl;
pnn p = split(root, idx + 1, true), p1 = split(p.se, N - idx + 1, false);
// // inorder(p1.fi);
if (p1.fi)
{
p1.fi -> lazy.fi = N - idx;
}
root = merge(p.fi, merge(p1.fi, p1.se));
//push shit horizontally.
//everything with x <= N-idx and y <= idx gets pushed to x=N-idx.
}
if (typ == 3)
{
segx.walk(1, 0, SZ(cx) - 1, 0, indexof(idx, cx), N - idx);
vi vec = segx.res; segx.res.clear();
for (int x : vec)
{
if (arr[x] == MP(-1, -1)) continue;
V[x] = new node(arr[x].fi, N - idx);
ins(V[x], x);
arr[x] = MP(-1, -1);
}
pnn p = split(root, N - idx + 1, true), p1 = split(p.se, idx, false);
if (p1.fi)
{
p1.fi -> lazy.se = N - idx;
}
//push shit vertically
//everything with x <= idx && y <= N-idx gets pushed to y = N-idx.
root = merge(p.fi, merge(p1.fi, p1.se));
}
if (typ == 4)
{
cin >> idx;
continue;
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
56 ms |
64376 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
723 ms |
159064 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
369 ms |
159952 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
369 ms |
159952 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
56 ms |
64376 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
