| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 213147 |
2020-03-25T04:34:05 Z |
qkxwsm |
Sweeping (JOI20_sweeping) |
C++14 |
|
1877 ms |
71800 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 = 1500013;
const int INF = 1000000007;
int N, M, Q;
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);
// cerr << t -> pos.fi << ',' << t -> pos.se << ' ' << t -> pri << endl;
if ((!dir && t -> pos.fi > v) || (dir && t -> pos.se < v))
{
// cerr << "left\n";
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
{
// cerr << "right\n";
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};
}
}
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]);
}
void preorder(node *t)
{
if (!t) return;
push(t);
cerr << t -> pos.fi << ',' << t -> pos.se << ',' << t -> pri << ' ';
preorder(t -> ch[0]);
preorder(t -> ch[1]);
}
node *root;
node *V[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;
V[i] = new node(p.fi, p.se);
root = merge(root, V[i]);
// cerr << "i = " << i << endl;
}
while(Q--)
{
// inorder(root); cerr << endl;
int typ, idx;
cin >> typ >> idx;
// cerr << "QUERY " << typ << ' ' << idx << endl;
if (typ == 1)
{
idx--;
// cerr << "idx = " << idx << endl;
get(V[idx]);
pii p = V[idx] -> pos;
cout << p.fi << ' ' << p.se << '\n';
}
if (typ == 2)
{
pnn p = split(root, idx + 1, true), p1 = split(p.se, N - idx + 1, false);
// inorder(p1.fi); cerr << endl;
// cerr << "N - idx = " << N - idx << endl;
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)
{
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));
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
768 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 |
297 ms |
71800 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 |
Correct |
1877 ms |
45432 KB |
Output is correct |
| 2 |
Correct |
1735 ms |
45560 KB |
Output is correct |
| 3 |
Correct |
1693 ms |
45052 KB |
Output is correct |
| 4 |
Correct |
1847 ms |
45564 KB |
Output is correct |
| 5 |
Correct |
1873 ms |
45560 KB |
Output is correct |
| 6 |
Correct |
1732 ms |
45560 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1877 ms |
45432 KB |
Output is correct |
| 2 |
Correct |
1735 ms |
45560 KB |
Output is correct |
| 3 |
Correct |
1693 ms |
45052 KB |
Output is correct |
| 4 |
Correct |
1847 ms |
45564 KB |
Output is correct |
| 5 |
Correct |
1873 ms |
45560 KB |
Output is correct |
| 6 |
Correct |
1732 ms |
45560 KB |
Output is correct |
| 7 |
Incorrect |
1438 ms |
45560 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
768 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
