#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e9;
const int MAXM = 5e5;
int N, M, Q;
struct Node
{
unordered_map<int, int> PX, PY, QX, QY, PV;
unordered_map<int, vector<int>> SX, SY;
map<int, int> MX, MY;
Node *lc, *rc;
Node() : lc(NULL), rc(NULL) {}
};
Node *root;
void push(Node *node, int px, int py, int pnum)
{
assert(px+py<=N);
assert(node->PX.find(pnum)==node->PX.end());
node->PX[pnum]=px;
node->PY[pnum]=py;
node->PV[pnum]=1;
node->SX[pnum].push_back(pnum);
node->SY[pnum].push_back(pnum);
node->QX[pnum]=pnum;
node->QY[pnum]=pnum;
if(node->MX.find(px)==node->MX.end()) node->MX[px]=pnum;
else
{
int t=node->MX[px];
node->QX[pnum]=t;
node->SX[t].push_back(pnum);
node->SX[pnum].pop_back();
}
if(node->MY.find(py)==node->MY.end()) node->MY[py]=pnum;
else
{
int t=node->MY[py];
node->QY[pnum]=t;
node->SY[t].push_back(pnum);
node->SY[pnum].pop_back();
}
}
int FindX(Node *node, int p)
{
if(node->QX[p]==p) return p;
return node->QX[p]=FindX(node, node->QX[p]);
}
int FindY(Node *node, int p)
{
if(node->QY[p]==p) return p;
return node->QY[p]=FindX(node, node->QY[p]);
}
void update(Node *node, int x, int y, int l, int px, int py, int pnum)
{
int m=l>>1;
int qx=x+m, qy=y+l-m;
assert(qx+qy==N);
assert(node!=NULL);
if(px<=qx && py<=qy)
{
//printf("P %d %d Q %d %d / %d\n", px, py, qx, qy, pnum);
push(node, px, py, pnum);
return;
}
if(qy<py)
{
assert(px<qx);
if(node->lc==NULL) node->lc=new Node();
node->PV[pnum]=-1;
update(node->lc, x, qy, m, px, py, pnum);
}
else if(qx<px)
{
assert(py<qy);
if(node->rc==NULL) node->rc=new Node();
node->PV[pnum]=-2;
update(node->rc, qx, y, l-m, px, py, pnum);
}
else assert(0);
}
void updateH(Node *node, int x, int y, int l, int px, int py)
{
if(l<=1) return;
int m=l>>1;
int qx=x+m, qy=y+l-m;
assert(qx+qy==N);
//printf("updateH : x %d y %d qx %d qy %d px %d py %d\n", x, y, qx, qy, px, py);
if(px<=qx)
{
vector<int> V;
vector<map<int, int>::iterator> VV;
for(auto it=node->MX.begin(); it!=node->MX.end() && it->first<=px; it++)
{
V.push_back(it->second);
VV.push_back(it);
}
for(auto it : VV) node->MX.erase(it);
if(!V.empty())
{
node->MX[px]=V[0];
node->PX[V[0]]=px;
for(int i=1; i<V.size(); i++)
{
node->QX[V[i]]=V[0];
if(node->SX[V[0]].size()<node->SX[V[i]].size()) swap(node->SX[V[0]], node->SX[V[i]]);
while(!node->SX[V[i]].empty())
{
node->SX[V[0]].push_back(node->SX[V[i]].back());
node->SX[V[i]].pop_back();
}
}
}
if(node->lc!=NULL) updateH(node->lc, x, qy, m, px, py);
}
else
{
vector<pii> V, V2;
vector<map<int, int>::iterator> VV;
for(auto it=node->MY.begin(); it!=node->MY.end() && it->first<=py; it++)
{
V.push_back({it->second, it->first});
VV.push_back(it);
}
for(auto it : VV) node->MY.erase(it);
for(auto it : V) for(auto jt : node->SY[it.first])
{
if(node->PV[jt]!=1) continue;
V2.push_back({jt, it.second});
node->PV[jt]=-2;
}
if(!V2.empty())
{
if(node->rc==NULL) node->rc=new Node();
for(auto it : V2)
{
update(node->rc, qx, y, l-m, qx+1, it.second, it.first);
}
}
if(node->rc!=NULL) updateH(node->rc, qx, y, l-m, px, py);
}
}
void updateV(Node *node, int x, int y, int l, int px, int py)
{
if(l<=1) return;
int m=l>>1;
int qx=x+m, qy=y+l-m;
assert(qx+qy==N);
//printf("updateH : x %d y %d qx %d qy %d px %d py %d\n", x, y, qx, qy, px, py);
if(py<=qy)
{
vector<int> V;
vector<map<int, int>::iterator> VV;
for(auto it=node->MY.begin(); it!=node->MY.end() && it->first<=py; it++)
{
V.push_back(it->second);
VV.push_back(it);
}
for(auto it : VV) node->MY.erase(it);
if(!V.empty())
{
node->MY[py]=V[0];
node->PY[V[0]]=py;
for(int i=1; i<V.size(); i++)
{
node->QY[V[i]]=V[0];
if(node->SY[V[0]].size()<node->SY[V[i]].size()) swap(node->SY[V[0]], node->SY[V[i]]);
while(!node->SY[V[i]].empty())
{
node->SY[V[0]].push_back(node->SY[V[i]].back());
node->SY[V[i]].pop_back();
}
}
}
if(node->rc!=NULL) updateV(node->rc, qx, y, l-m, px, py);
}
else
{
vector<pii> V, V2;
vector<map<int, int>::iterator> VV;
for(auto it=node->MX.begin(); it!=node->MX.end() && it->first<=px; it++)
{
V.push_back({it->second, it->first});
VV.push_back(it);
}
for(auto it : VV) node->MX.erase(it);
for(auto it : V) for(auto jt : node->SX[it.first])
{
if(node->PV[jt]!=1) continue;
V2.push_back({jt, it.second});
node->PV[jt]=-1;
}
if(!V2.empty())
{
if(node->lc==NULL) node->lc=new Node();
for(auto it : V2)
{
update(node->lc, x, qy, m, it.second, qy+1, it.first);
}
}
if(node->lc!=NULL) updateV(node->lc, x, qy, m, px, py);
}
}
pii query(Node *node, int x, int y, int l, int num)
{
assert(node!=NULL);
int m=l>>1;
int qx=x+m, qy=y+l-m;
assert(qx+qy==N);
assert(node->PV[num]!=0);
if(node->PV[num]==1)
{
int px=node->PX[FindX(node, num)], py=node->PY[FindY(node, num)];
//printf("P %d %d Q %d %d XY %d %d / %d\n", px, py, qx, qy, x, y, num);
assert(px<=qx && py<=qy);
return {px, py};
}
else if(node->PV[num]==-1) return query(node->lc, x, qy, m, num);
else if(node->PV[num]==-2) return query(node->rc, qx, y, l-m, num);
}
int main()
{
root=new Node();
scanf("%d%d%d", &N, &M, &Q); N+=2;
for(int i=1; i<=M; i++)
{
int x, y;
scanf("%d%d", &x, &y); x++; y++;
update(root, 0, 0, N, x, y, i);
}
while(Q--)
{
int t;
scanf("%d", &t);
if(t==1)
{
int p;
scanf("%d", &p);
pii ans=query(root, 0, 0, N, p);
printf("%d %d\n", ans.first-1, ans.second-1);
}
else if(t==2)
{
int x, y;
scanf("%d", &y); y++;
x=N-y;
updateH(root, 0, 0, N, x, y);
}
else if(t==3)
{
int x, y;
scanf("%d", &x); x++;
y=N-x;
updateV(root, 0, 0, N, x, y);
}
else
{
int x, y;
scanf("%d%d", &x, &y); x++; y++; M++;
update(root, 0, 0, N, x, y, M);
}
//printf("DONE\n");
}
}
Compilation message
sweeping.cpp: In function 'void updateH(Node*, int, int, int, int, int)':
sweeping.cpp:117:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
117 | for(int i=1; i<V.size(); i++)
| ~^~~~~~~~~
sweeping.cpp: In function 'void updateV(Node*, int, int, int, int, int)':
sweeping.cpp:180:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
180 | for(int i=1; i<V.size(); i++)
| ~^~~~~~~~~
sweeping.cpp: In function 'pii query(Node*, int, int, int, int)':
sweeping.cpp:239:1: warning: control reaches end of non-void function [-Wreturn-type]
239 | }
| ^
sweeping.cpp: In function 'int main()':
sweeping.cpp:244:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
244 | scanf("%d%d%d", &N, &M, &Q); N+=2;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:249:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
249 | scanf("%d%d", &x, &y); x++; y++;
| ~~~~~^~~~~~~~~~~~~~~~
sweeping.cpp:255:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
255 | scanf("%d", &t);
| ~~~~~^~~~~~~~~~
sweeping.cpp:259:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
259 | scanf("%d", &p);
| ~~~~~^~~~~~~~~~
sweeping.cpp:266:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
266 | scanf("%d", &y); y++;
| ~~~~~^~~~~~~~~~
sweeping.cpp:273:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
273 | scanf("%d", &x); x++;
| ~~~~~^~~~~~~~~~
sweeping.cpp:280:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
280 | scanf("%d%d", &x, &y); x++; y++; M++;
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
8440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16572 ms |
2097156 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11393 ms |
2080292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11393 ms |
2080292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
8440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
