#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
const int inf = 1e9 + 7;
#define X first
#define Y second
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
int rand(int a, int b) {
return uniform_int_distribution<int>(a, b)(rng);
}
struct STNode {
STNode *l, *r;
ii v;
STNode(ii v = {inf, inf}) {
this->v = v;
l = r = nullptr;
}
void upd() {
v = {inf, inf};
if(l != nullptr)
v = min(v, l->v);
if(r != nullptr)
v = min(v, r->v);
}
};
struct SegmentTree {
int lv;
STNode *root;
SegmentTree(int n) {
root = new STNode();
lv = 2;
while(lv < n + 2)
lv *= 2;
}
void insert(STNode *&n, int l, int r, int w, int v) {
//~ cout << "a" << endl;
if(n == nullptr)
n = new STNode();
if(l == r) {
n->v = {v, l};
return ;
}
if(w <= (l + r) / 2)
insert(n->l, l, (l + r) / 2, w, v);
else
insert(n->r, (l + r) / 2 + 1, r, w, v);
n->upd();
}
ii query(STNode *&n, int l, int r, int a, int b) {
if(n == nullptr || r < a || l > b || l > r)
return {inf, inf};
if(a <= l && r <= b)
return n->v;
return min(query(n->l, l, (l + r) / 2, a, b),
query(n->r, (l + r) / 2 + 1, r, a, b));
}
void insert(int w, int v) {
insert(root, 0, lv - 1, w, v);
}
ii query(int a, int b) {
return query(root, 0, lv - 1, a, b);
}
};
struct TreapNode {
TreapNode *l, *r, *p;
int x, y, q, lazyx, lazyy, sz;
TreapNode(int _x, int _y) {
x = _x;
y = _y;
q = rand(INT_MIN, INT_MAX);
l = r = p = nullptr;
lazyx = 0;
lazyy = 0;
sz = 1;
}
TreapNode* attach(TreapNode *ll, TreapNode *rr) {
l = ll;
r = rr;
sz = 1;
if(l != nullptr)
l->p = this, sz += l->sz;
if(r != nullptr)
r->p = this, sz += r->sz;
return this;
}
void push() {
x = max(x, lazyx);
y = max(y, lazyy);
if(l != nullptr) {
l->lazyx = max(l->lazyx, lazyx);
l->lazyy = max(l->lazyy, lazyy);
}
if(r != nullptr) {
r->lazyx = max(r->lazyx, lazyx);
r->lazyy = max(r->lazyy, lazyy);
}
lazyx = 0;
lazyy = 0;
}
void print() {
push();
cout << "[";
if(l != nullptr)
l->print();
cout << "]";
cout << "(" << x << ", " << y << ")[";
if(r != nullptr)
r->print();
cout << "]";
}
};
int szof(TreapNode *n) {
if(n == nullptr)
return 0;
return n->sz;
}
struct Treap {
TreapNode *root;
map<int, TreapNode*> M;
int total;
Treap() {
root = new TreapNode(0, 0);
total = 1;
}
TreapNode* merge(TreapNode *a, TreapNode *b) {
if(a == nullptr)
return b;
if(b == nullptr)
return a;
a->push();
b->push();
if(a->q < b->q)
return a->attach(a->l, merge(a->r, b));
else
return b->attach(merge(a, b->l), b->r);
}
bool comp(int x1, int y1, int x2, int y2) {
return (x1 < x2 || y1 > y2);
}
pair<TreapNode*, TreapNode*> split(TreapNode *n, int x, int y) {
if(n == nullptr)
return {nullptr, nullptr};
n->push();
if(comp(x, y, n->x, n->y)) {
TreapNode *m = n->l;
n->attach(nullptr, n->r);
auto p = split(m, x, y);
return {p.X, n->attach(p.Y, n->r)};
} else {
TreapNode *m = n->r;
n->attach(n->l, nullptr);
auto p = split(m, x, y);
return {n->attach(n->l, p.X), p.Y};
}
}
void insert(int i, int x, int y) {
TreapNode *n = new TreapNode(x, y);
M[i] = n;
auto p = split(root, x, y);
root = merge(merge(p.X, n), p.Y);
total++;
}
// dla x' <= x
void maxy(int x, int v) {
auto p = split(root, x, -1);
if(p.X != nullptr)
p.X->lazyy = max(p.X->lazyy, v);
root = merge(p.X, p.Y);
}
// dla y' <= y
void maxx(int y, int v) {
auto p = split(root, inf, y+1);
//~ cout << "maxx split" << endl;
//~ if(p.X != nullptr) p.X->print(); cout << endl;
//~ if(p.Y != nullptr) p.Y->print(); cout << endl;
if(p.Y != nullptr)
p.Y->lazyx = max(p.Y->lazyx, v);
root = merge(p.X, p.Y);
}
void process_lazy_up(TreapNode *n) {
if(n == nullptr)
return ;
process_lazy_up(n->p);
n->push();
}
ii query(int i) {
TreapNode *n = M[i];
process_lazy_up(n);
return {n->x, n->y};
}
void print() {
root->print();
cerr << endl;
}
};
struct Points {
// inicjalizujemy punktami, ktore sie nie zmieniaja
// wrzucamy wszystkie na drzewo i mape wektorow
// treap pusty
// przy kazdym zapytaniu najpierw aktualizujemy treapa, potem przerzucamy na niego punkty
int n, m;
Treap *T;
SegmentTree *ST;
map<int, vector<ii> > M;
set<int> on_treap;
map<int, ii> initial_cor;
Points(vector<pair<int, ii> > P, int n) {
this->n = n;
T = new Treap();
ST = new SegmentTree(inf);
for(auto p : P) {
M[p.Y.X].emplace_back(p.Y.Y, p.X);
initial_cor[p.X] = p.Y;
}
for(auto &p : M) {
sort(p.Y.begin(), p.Y.end(), greater<ii>());
ST->insert(p.X, p.Y.back().X);
}
m = P.size();
}
ii query(int i) {
if(on_treap.count(i))
return T->query(i);
else
return initial_cor[i];
}
void sweep_horizontally(int s) {
T->maxx(s, n - s);
ii p;
while((p = ST->query(0, n - s)).X <= s) {
int x = p.Y;
T->insert(M[x].back().Y, n - s, M[x].back().X);
on_treap.insert(M[x].back().Y);
M[x].pop_back();
int v = inf;
if(M[x].size())
v = M[x].back().X;
ST->insert(x, v);
}
}
void sweep_vertically(int s) {
T->maxy(s, n - s);
ii p;
while((p = ST->query(0, s)).X <= n - s) {
int x = p.Y;
T->insert(M[x].back().Y, x, n - s);
on_treap.insert(M[x].back().Y);
M[x].pop_back();
int v = inf;
if(M[x].size())
v = M[x].back().X;
ST->insert(x, v);
}
}
int size() {
return m;
}
vector<pair<int, ii> > get_all_points() {
vector<pair<int, ii>> res;
for(auto p : initial_cor) {
if(on_treap.count(p.X))
res.push_back({p.X, T->query(p.X)});
else
res.push_back({p.X, p.Y});
}
return res;
}
};
struct MasterPoints {
int n;
Points *I;
vector<Points*> P;
map<int, Points*> M;
MasterPoints(vector<pair<int, ii> > P, int n) {
this->n = n;
I = new Points(P, n);
for(auto p : P)
M[p.X] = I;
}
ii query(int i) {
return M[i]->query(i);
}
void sweep_horizontally(int s) {
I->sweep_horizontally(s);
for(auto p : P)
p->sweep_horizontally(s);
}
void sweep_vertically(int s) {
I->sweep_vertically(s);
for(auto p : P)
p->sweep_vertically(s);
}
void add_point(int i, int x, int y) {
P.push_back(new Points({{i, {x, y}}}, n));
M[i] = P.back();
if(P.size() > 1 && P.back()->size() == P[P.size() - 2]->size()) {
auto P1 = P.back()->get_all_points();
P.pop_back();
auto P2 = P.back()->get_all_points();
P.pop_back();
for(auto p : P2)
P1.push_back(p);
P.push_back(new Points(P1, n));
for(auto p : P1)
M[p.X] = P.back();
}
}
};
int n, m, q;
MasterPoints *PP;
int main() {
scanf("%d%d%d", &n, &m, &q);
vector<pair<int, ii> > P;
for(int i = 1 ; i <= m ; i++) {
int a, b;
scanf("%d%d", &a, &b);
P.push_back({i, {a, b}});
}
PP = new MasterPoints(P, n);
int cnt = m;
while(q--) {
int t;
scanf("%d", &t);
if(t == 1) {
int i;
scanf("%d", &i);
ii p = PP->query(i);
printf("%d %d\n", p.X, p.Y);
} else if(t == 2) {
int s;
scanf("%d", &s);
PP->sweep_horizontally(s);
} else if(t == 3) {
int s;
scanf("%d", &s);
PP->sweep_vertically(s);
} else {
int a, b;
scanf("%d%d", &a, &b);
PP->add_point(++cnt, a, b);
}
//~ cout << "TREAP\n";
//~ PP->T->print();
}
return 0;
}
Compilation message
sweeping.cpp: In function 'int main()':
sweeping.cpp:364:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &n, &m, &q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:369:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~
sweeping.cpp:378:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &t);
~~~~~^~~~~~~~~~
sweeping.cpp:381:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &i);
~~~~~^~~~~~~~~~
sweeping.cpp:386:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &s);
~~~~~^~~~~~~~~~
sweeping.cpp:390:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &s);
~~~~~^~~~~~~~~~
sweeping.cpp:394:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
4856 KB |
Output is correct |
| 2 |
Correct |
68 ms |
3448 KB |
Output is correct |
| 3 |
Correct |
19 ms |
6528 KB |
Output is correct |
| 4 |
Correct |
49 ms |
4984 KB |
Output is correct |
| 5 |
Correct |
483 ms |
6556 KB |
Output is correct |
| 6 |
Correct |
11 ms |
1024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18075 ms |
389676 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6437 ms |
408840 KB |
Output is correct |
| 2 |
Correct |
6367 ms |
428752 KB |
Output is correct |
| 3 |
Correct |
5577 ms |
416116 KB |
Output is correct |
| 4 |
Correct |
5558 ms |
423192 KB |
Output is correct |
| 5 |
Correct |
5998 ms |
424316 KB |
Output is correct |
| 6 |
Correct |
6202 ms |
428352 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6437 ms |
408840 KB |
Output is correct |
| 2 |
Correct |
6367 ms |
428752 KB |
Output is correct |
| 3 |
Correct |
5577 ms |
416116 KB |
Output is correct |
| 4 |
Correct |
5558 ms |
423192 KB |
Output is correct |
| 5 |
Correct |
5998 ms |
424316 KB |
Output is correct |
| 6 |
Correct |
6202 ms |
428352 KB |
Output is correct |
| 7 |
Correct |
8189 ms |
401184 KB |
Output is correct |
| 8 |
Correct |
8124 ms |
401008 KB |
Output is correct |
| 9 |
Correct |
7902 ms |
400948 KB |
Output is correct |
| 10 |
Correct |
7674 ms |
416056 KB |
Output is correct |
| 11 |
Correct |
8847 ms |
423272 KB |
Output is correct |
| 12 |
Correct |
9608 ms |
423968 KB |
Output is correct |
| 13 |
Correct |
9131 ms |
424040 KB |
Output is correct |
| 14 |
Correct |
523 ms |
4192 KB |
Output is correct |
| 15 |
Correct |
3549 ms |
114920 KB |
Output is correct |
| 16 |
Correct |
8092 ms |
399288 KB |
Output is correct |
| 17 |
Correct |
7767 ms |
399224 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
4856 KB |
Output is correct |
| 2 |
Correct |
68 ms |
3448 KB |
Output is correct |
| 3 |
Correct |
19 ms |
6528 KB |
Output is correct |
| 4 |
Correct |
49 ms |
4984 KB |
Output is correct |
| 5 |
Correct |
483 ms |
6556 KB |
Output is correct |
| 6 |
Correct |
11 ms |
1024 KB |
Output is correct |
| 7 |
Execution timed out |
18075 ms |
389676 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
