#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(x<=px && y<=py);
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(node->rc!=NULL) updateH(node->rc, qx, y, l-m, px, py);
if(!V2.empty())
{
if(node->rc==NULL) node->rc=new Node();
for(auto it : V2)
{
update(node->rc, qx, y, l-m, px, it.second, it.first);
}
}
}
}
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(node->lc!=NULL) updateV(node->lc, x, qy, m, px, py);
if(!V2.empty())
{
if(node->lc==NULL) node->lc=new Node();
for(auto it : V2)
{
update(node->lc, x, qy, m, it.second, py, it.first);
}
}
}
}
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, py;
for(auto it : node->MX) for(auto jt : node->SX[it.second]) if(jt==num) px=it.first;
for(auto it : node->MY) for(auto jt : node->SY[it.second]) if(jt==num) py=it.first;
//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:118:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | for(int i=1; i<V.size(); i++)
| ~^~~~~~~~~
sweeping.cpp: In function 'void updateV(Node*, int, int, int, int, int)':
sweeping.cpp:181:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
181 | for(int i=1; i<V.size(); i++)
| ~^~~~~~~~~
sweeping.cpp: In function 'pii query(Node*, int, int, int, int)':
sweeping.cpp:241:1: warning: control reaches end of non-void function [-Wreturn-type]
241 | }
| ^
sweeping.cpp: In function 'int main()':
sweeping.cpp:246:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
246 | scanf("%d%d%d", &N, &M, &Q); N+=2;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:251:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
251 | scanf("%d%d", &x, &y); x++; y++;
| ~~~~~^~~~~~~~~~~~~~~~
sweeping.cpp:257:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
257 | scanf("%d", &t);
| ~~~~~^~~~~~~~~~
sweeping.cpp:261:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
261 | scanf("%d", &p);
| ~~~~~^~~~~~~~~~
sweeping.cpp:268:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
268 | scanf("%d", &y); y++;
| ~~~~~^~~~~~~~~~
sweeping.cpp:275:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
275 | scanf("%d", &x); x++;
| ~~~~~^~~~~~~~~~
sweeping.cpp:282:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
282 | scanf("%d%d", &x, &y); x++; y++; M++;
| ~~~~~^~~~~~~~~~~~~~~~
sweeping.cpp: In function 'pii query(Node*, int, int, int, int)':
sweeping.cpp:237:17: warning: 'py' may be used uninitialized in this function [-Wmaybe-uninitialized]
237 | return {px, py};
| ^
sweeping.cpp:237:17: warning: 'px' may be used uninitialized in this function [-Wmaybe-uninitialized]
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
34 ms |
7032 KB |
Output is correct |
| 2 |
Correct |
14 ms |
2688 KB |
Output is correct |
| 3 |
Correct |
187 ms |
2680 KB |
Output is correct |
| 4 |
Correct |
28 ms |
6008 KB |
Output is correct |
| 5 |
Correct |
32 ms |
7576 KB |
Output is correct |
| 6 |
Correct |
13 ms |
2048 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
17162 ms |
2097156 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15584 ms |
1929916 KB |
Output is correct |
| 2 |
Correct |
17050 ms |
1954468 KB |
Output is correct |
| 3 |
Execution timed out |
18050 ms |
276920 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15584 ms |
1929916 KB |
Output is correct |
| 2 |
Correct |
17050 ms |
1954468 KB |
Output is correct |
| 3 |
Execution timed out |
18050 ms |
276920 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
34 ms |
7032 KB |
Output is correct |
| 2 |
Correct |
14 ms |
2688 KB |
Output is correct |
| 3 |
Correct |
187 ms |
2680 KB |
Output is correct |
| 4 |
Correct |
28 ms |
6008 KB |
Output is correct |
| 5 |
Correct |
32 ms |
7576 KB |
Output is correct |
| 6 |
Correct |
13 ms |
2048 KB |
Output is correct |
| 7 |
Runtime error |
17162 ms |
2097156 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 8 |
Halted |
0 ms |
0 KB |
- |
