| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 213160 |
2020-03-25T05:50:02 Z |
qkxwsm |
Sweeping (JOI20_sweeping) |
C++14 |
|
4170 ms |
128340 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 = 530013;
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 MP(a.fi, -a.se) > MP(b.fi, -b.se);
}
struct node
{
node *ch[2], *p;
pii pos, lazy;
int pri;
node(int x, int y)
{
ch[0] = nullptr;
ch[1] = nullptr;
p = nullptr;
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))
{
pnn p = split(t -> ch[0], v, dir);
t -> ch[0] = p.se; if (t -> ch[0]) t -> ch[0] -> p = t;
if (p.fi) p.fi -> p = nullptr;
return {p.fi, t};
}
else
{
pnn p = split(t -> ch[1], v, dir);
t -> ch[1] = p.fi; if (t -> ch[1]) t -> ch[1] -> p = t;
if (p.se) p.se -> p = nullptr;
return {t, p.se};
}
}
pnn Split(node *t, pii v)
{
if (!t) return {nullptr, nullptr};
push(t);
if (cmp(t -> pos, v))
{
pnn p = Split(t -> ch[0], v);
t -> ch[0] = p.se; if (t -> ch[0]) t -> ch[0] -> p = t;
if (p.fi) p.fi -> p = nullptr;
return {p.fi, t};
}
else
{
pnn p = Split(t -> ch[1], v);
t -> ch[1] = p.fi; if (t -> ch[1]) t -> ch[1] -> p = t;
if (p.se) p.se -> p = nullptr;
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(int x, int y, int idx)
{
// inorder(root); cerr << endl;
// cerr << "insert " << x << ' ' << y << endl;
V[idx] = new node(x, y);
pnn p = Split(root, {x, y});
// cerr << "ok" << endl;
root = merge(p.fi, merge(V[idx], 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;
}
int query(int w, int L, int R, int a, int b)
{
if (a <= L && R <= b) return seg[w];
int mid = (L + R) >> 1;
if (b <= mid) return query(w << 1, L, mid, a, b);
if (mid < a) return query(w << 1 | 1, mid + 1, R, a, b);
return min(query(w << 1, L, mid, a, b), query(w << 1 | 1, mid + 1, R, a, b));
}
};
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";
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.
// 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));
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;
ins(N - idx, arr[x].se, x);
arr[x] = MP(-1, -1);
}
// assert(segy.query(1, 0, SZ(cy) - 1, 0, indexof(idx, cy)) >= N - idx);
//push shit horizontally.
//everything with x <= N-idx and y <= idx gets pushed to x=N-idx.
}
if (typ == 3)
{
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));
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;
ins(arr[x].fi, N - idx, x);
arr[x] = MP(-1, -1);
}
// assert(segx.query(1, 0, SZ(cx) - 1, 0, indexof(idx, cx)) >= N - idx);
}
if (typ == 4)
{
cin >> idx;
continue;
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
33920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2917 ms |
114008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2390 ms |
126424 KB |
Output is correct |
| 2 |
Correct |
2516 ms |
126292 KB |
Output is correct |
| 3 |
Correct |
2183 ms |
125528 KB |
Output is correct |
| 4 |
Correct |
2316 ms |
126040 KB |
Output is correct |
| 5 |
Correct |
2430 ms |
128340 KB |
Output is correct |
| 6 |
Correct |
2380 ms |
126288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2390 ms |
126424 KB |
Output is correct |
| 2 |
Correct |
2516 ms |
126292 KB |
Output is correct |
| 3 |
Correct |
2183 ms |
125528 KB |
Output is correct |
| 4 |
Correct |
2316 ms |
126040 KB |
Output is correct |
| 5 |
Correct |
2430 ms |
128340 KB |
Output is correct |
| 6 |
Correct |
2380 ms |
126288 KB |
Output is correct |
| 7 |
Correct |
3409 ms |
116432 KB |
Output is correct |
| 8 |
Correct |
3528 ms |
116572 KB |
Output is correct |
| 9 |
Correct |
3361 ms |
116440 KB |
Output is correct |
| 10 |
Correct |
2702 ms |
125648 KB |
Output is correct |
| 11 |
Correct |
4170 ms |
126036 KB |
Output is correct |
| 12 |
Correct |
3080 ms |
127704 KB |
Output is correct |
| 13 |
Correct |
3112 ms |
127696 KB |
Output is correct |
| 14 |
Correct |
203 ms |
33536 KB |
Output is correct |
| 15 |
Correct |
940 ms |
69584 KB |
Output is correct |
| 16 |
Correct |
3368 ms |
115796 KB |
Output is correct |
| 17 |
Correct |
3283 ms |
115672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
33920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
