#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
using namespace std;
typedef pair<int, int> pii;
#define N 500050
int n, m, q;
const int inf = (int)(1e9) + 10;
class Treap{
public:
struct node{
int sz, x, y, w, lazyX, lazyY;
int xmin, xmax, ymin, ymax;
node *l, *r;
node(int X, int Y){
sz = 1;
w = rand();
l = r = NULL;
lazyX = lazyY = -1;
x = xmin = xmax = X;
y = ymin = ymax = Y;
}
};
void insert(int idx, int x, int y){
node *l = NULL, *r = NULL, *novo = new node (x, y);
Split(root, l, r, idx + 1);
Merge(root, novo, r);
Merge(root, l, root);
}
node *root = NULL;
void update(int a, int b, int X, int flag){
node *l1 = NULL, *r1 = NULL, *l2 = NULL, *r2 = NULL, *T = NULL;
Split(root, l1, r1, b + 1);
Split(l1, l2, r2, a);
if(flag)r2->lazyX = X;
else r2->lazyY = X;
Merge(T, l2, r2);
Merge(root, T, r1);
}
pii query(int a, int b){
node *l1 = NULL, *r1 = NULL, *l2 = NULL, *r2 = NULL, *T = NULL;
Split(root, l1, r1, b + 1);
Split(l1, l2, r2, a);
pii resp = pii(r2->x, r2->y);
assert(tam(r2) == 1);
Merge(T, l2, r2);
Merge(root, T, r1);
return resp;
}
//retorna o cara mais a direita tal que xi <= XMAX
int findx(node *&root, int XMAX){
prop(root);
// cout<<" XMAX = "<<XMAX<<" | "<<xmin(root)<<"\n";
if(!root or xmin(root) > XMAX) return -inf;
prop(root->l);prop(root->r);
upd(root);
int p = tam(root->l) + 1, key = root->x;
if(root->r and key <= XMAX and (!root->l or xmin(root->l) <= XMAX)){
return p + max(findx(root->r, XMAX), 0);
}
if(key <= XMAX){
// cout<<"GO MID "<<xmin(root->l)<<"\n";
return p;
}
return findx(root->l, XMAX);
}
//retorna o cara mais a esquerda tal que yi <= XMAX
int findy(node *&root, int XMAX){
// cout<<"YMAX = "<<XMAX<<"\n";
prop(root);
if(!root or ymin(root) > XMAX) return -inf;
prop(root->l);prop(root->r);
upd(root);
int p = tam(root->l) + 1, key = root->y;
if(root->l and key <= XMAX and (!root->r or ymin(root->r) <= XMAX)){
int L = findy(root->l, XMAX);
if(L >= 0)return L;
else return p;
}
if(key <= XMAX) return p;
return (p + findy(root->r, XMAX));
}
private:
int tam(node *root){return root != NULL? root->sz:0;}
int xmin(node *&root){return (root?root->xmin:inf);}
int xmax(node *&root){return (root?root->xmax:-inf);}
int ymin(node *&root){return (root?root->ymin:inf);}
int ymax(node *&root){return (root?root->ymax:-inf);}
void prop(node *&root){
if(!root) return;
if(root->l and root->lazyX != -1) root->l->lazyX = root->lazyX;
if(root->l and root->lazyY != -1) root->l->lazyY = root->lazyY;
if(root->r and root->lazyX != -1) root->r->lazyX = root->lazyX;
if(root->r and root->lazyY != -1) root->r->lazyY = root->lazyY;
if(root->lazyX != -1){
root->x = root->lazyX;
root->xmin = root->x;
}
if(root->lazyY != -1){
root->y = root->lazyY;
root->ymin=root->y;
}
root->lazyX = root->lazyY = -1;
}
void upd(node *&root){
if(root == NULL) return;
root->sz = tam(root->l) + tam(root->r) + 1;
root->xmin = min({xmin(root->l), xmin(root->r),root->x});
root->xmax = max({xmax(root->l), xmax(root->r),root->x});
root->ymin = min({ymin(root->l), ymin(root->r),root->y});
root->ymax = max({ymax(root->l), ymax(root->r),root->y});
}
void Merge(node *&root, node *l, node *r){
if(!l or !r) root = (l ? l: r);
else{
if(l->w > r->w){
prop(l);
Merge(l->r, l->r, r), root = l;
}
else{
prop(r);
Merge(r->l, l, r->l), root = r;
}
upd(root);
}
}
void Split(node *root, node *&l, node *&r, int idx){
if(!root) l = r = NULL;
else{
prop(root);
int p = tam(root->l) + 1;
if(p < idx) Split(root->r, root->r, r, idx - p), l = root;
else Split(root->l, l, root->l, idx), r = root;
upd(root);
}
}
} good;
pii v[N];
int32_t main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>m>>q;
int cnt=0;
for(int i = 1; i <= m; i++){
cin>>v[i].f>>v[i].s;
good.insert(i, v[i].f, v[i].s);
}
for(int i = 1; i <= q; i++){
int t;
cin>>t;
if(t == 1){
++cnt;
int p;
cin>>p;
auto pos = good.query(p,p);
cout<<pos.f<<" "<<pos.s<<"\n";
}
if(t == 2){
int l;
cin>>l;
int L = good.findy(good.root, l); // menor i, tal que yi <= l
int R = good.findx(good.root, n-l);// maior i, tal que xi <= n-l
// assert(1 <= L and L <= m and 1 <= R and R <= m);
if(L > 0 and R > 0 and L <= R) good.update(L, R, n-l,1); // atualiza x para n-l
}
if(t == 3){
int l;
cin>>l;
int L = good.findy(good.root, n-l); // menor i, tal que yi <= n-l
int R = good.findx(good.root, l);// maior i, tal que xi <= l
if(L > 0 and R > 0 and L <= R) good.update(L, R, n-l,0); // atualiza y para n-l
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
748 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
462 ms |
71884 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3235 ms |
45548 KB |
Output is correct |
| 2 |
Correct |
2953 ms |
45444 KB |
Output is correct |
| 3 |
Correct |
3061 ms |
45228 KB |
Output is correct |
| 4 |
Correct |
3752 ms |
45636 KB |
Output is correct |
| 5 |
Correct |
3029 ms |
55540 KB |
Output is correct |
| 6 |
Correct |
2963 ms |
65644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3235 ms |
45548 KB |
Output is correct |
| 2 |
Correct |
2953 ms |
45444 KB |
Output is correct |
| 3 |
Correct |
3061 ms |
45228 KB |
Output is correct |
| 4 |
Correct |
3752 ms |
45636 KB |
Output is correct |
| 5 |
Correct |
3029 ms |
55540 KB |
Output is correct |
| 6 |
Correct |
2963 ms |
65644 KB |
Output is correct |
| 7 |
Incorrect |
2594 ms |
65448 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
748 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
