#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pdd pair<long double, long double>
#define pii pair<int, int>
#define pll pair<ll, ll>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
const int mxN=500005;
const int mxQ=1000010;
const int mxM=3000010;
const ll MOD=1000000007;
const ll INF=1e18;
int dx[4]={1, 0, -1, 0}, dy[4]={0, 1, 0, -1};
int ddx[8]={1, 1, 0, -1, -1, -1, 0, 1}, ddy[8]={0, -1, -1, -1, 0, 1, 1, 1};
typedef struct qry{
int idx, typ, a, b;
}qry;
typedef struct cmp{
bool operator()(pii a, pii b){
return a.fi!=b.fi ? a.fi<b.fi : a.se>b.se;
}
}cmp;
int N, M, Q;
pii A[mxN+mxQ];
int tim[mxN+mxQ];
qry B[mxQ];
vector <pii> ct[4*mxQ], seg[4*mxQ];
vector <pair<pii, int>> sct[4*mxQ];
vector <int> st[4*mxQ];
void input()
{
cin >> N >> M >> Q;
for(int i=1;i<=M;i++) cin >> A[i].fi >> A[i].se;
int dc=M;
for(int i=1;i<=Q;i++)
{
B[i].idx=i;
cin >> B[i].typ;
if(B[i].typ==4) cin >> B[i].a >> B[i].b;
else cin >> B[i].a;
if(B[i].typ==2 || B[i].typ==3)
{
B[i].a++;
if(B[i].a>N) B[i].typ=5;
}
if(B[i].typ==2) B[i].a=N-B[i].a;
if(B[i].typ==4) tim[++dc]=i, A[dc]=pii(B[i].a, B[i].b);
}
}
pii ts[4*mxN];
void init(int idx, int s, int e, pii val)
{
ts[idx]=val;
if(s==e) return;
int mid=(s+e)/2;
init(2*idx, s, mid, val);
init(2*idx+1, mid+1, e, val);
}
void tupd(int idx, int s1, int e1, int s2, int e2, pii val)
{
if(s2<=s1 && e1<=e2)
{
if(ts[idx].se-ts[idx].fi>val.se-val.fi) ts[idx]=val;
return;
}
if(s2>e1 || s1>e2) return;
int mid=(s1+e1)/2;
tupd(2*idx, s1, mid, s2, e2, val);
tupd(2*idx+1, mid+1, e1, s2, e2, val);
}
pii tsolv(int idx, int s1, int e1, int pos)
{
if(s1==e1) return ts[idx];
int mid=(s1+e1)/2;
pii ret;
if(pos<=mid) ret=tsolv(2*idx, s1, mid, pos);
else ret=tsolv(2*idx+1, mid+1, e1, pos);
return (ret.se-ret.fi<ts[idx].se-ts[idx].fi) ? ret : ts[idx];
}
void dfs(int idx, int pos, vector<pii> &v, vector<pii> &lr)
{
if(lr[pos].fi!=0) dfs(idx, lr[pos].fi, v, lr);
ct[idx].push_back(v[pos]);
if(lr[pos].fi==0) st[idx].push_back(v[pos].fi);
else st[idx].push_back(v[lr[pos].fi].se+1);
if(lr[pos].se!=0) dfs(idx, lr[pos].se, v, lr);
}
void seg_init(int ii, int idx, int s, int e)
{
if(s==e)
{
seg[ii][idx]=ct[ii][s];
return;
}
int mid=(s+e)/2;
seg_init(ii, 2*idx, s, mid);
seg_init(ii, 2*idx+1, mid+1, e);
seg[ii][idx]=((seg[ii][2*idx].se-seg[ii][2*idx].fi>seg[ii][2*idx+1].se-seg[ii][2*idx+1].fi) ? seg[ii][2*idx] : seg[ii][2*idx+1]);
}
void make_seg(int idx, int s, int e)
{
//printf("idx=%d, s=%d, e=%d\n", idx, s, e);
vector <pii> v, lr;
vector <int> cr;
for(int i=s;i<=e;i++) if(B[i].typ==2 || B[i].typ==3) cr.push_back(B[i].a);
cr.push_back(0), cr.push_back(N);
sort(cr.begin(), cr.end());
cr.erase(unique(cr.begin(), cr.end()), cr.end());
//printf("cr: ");
//for(int ele : cr) printf("%d ", ele);
//printf("\n");
int K=cr.size();
init(1, 0, K-1, pii(0, K-1));
v.emplace_back(0, K-1);
for(int i=s;i<=e;i++)
{
if(B[i].typ!=2 && B[i].typ!=3) continue;
int np=lower_bound(cr.begin(), cr.end(), B[i].a)-cr.begin();
//printf("np=%d\n", np);
pii rng=tsolv(1, 0, K-1, np), now;
//printf("rng=%d, %d\n", rng.fi, rng.se);
if(B[i].typ==2 && (np==K-1 || (cr[np]+1==cr[np+1] && tsolv(1, 0, K-1, np+1)!=rng))) continue;
if(B[i].typ==3 && (np==0 || (cr[np]-1==cr[np-1] && tsolv(1, 0, K-1, np-1)!=rng))) continue;
if(B[i].typ==2) now=pii(rng.fi, np);
if(B[i].typ==3) now=pii(np, rng.se);
//printf("rng=%d, %d\n", rng.fi, rng.se);
tupd(1, 0, K-1, now.fi, now.se, now);
v.push_back(now);
}
for(pii &ele : v) ele.fi=cr[ele.fi], ele.se=cr[ele.se];
sort(v.begin(), v.end(), cmp());
//for(pii ele : v) printf("(%d, %d) ", ele.fi, ele.se);
//printf("\n");
lr.resize(v.size());
stack <pair<pii, int>> stk;
for(int i=0;i<v.size();i++)
{
while(stk.size() && stk.top().fi.se<v[i].fi) stk.pop();
if(stk.size())
{
if(stk.top().fi.fi==v[i].fi) lr[stk.top().se].fi=i;
else lr[stk.top().se].se=i;
}
stk.emplace(v[i], i);
}
//for(int i=0;i<lr.size();i++) printf("(%d, %d) ", lr[i].fi, lr[i].se);
//printf("\n");
dfs(idx, 0, v, lr);
//for(int i=0;i<ct[idx].size();i++) printf("(%d, %d) ", ct[idx][i].fi, ct[idx][i].se);
//printf("\n");
//for(int i=0;i<st[idx].size();i++) printf("%d ", st[idx][i]);
//printf("\n");
seg[idx].resize(4*ct[idx].size());
seg_init(idx, 1, 0, v.size()-1);
sct[idx].resize(ct[idx].size());
for(int i=0;i<ct[idx].size();i++)
{
sct[idx][i].fi=ct[idx][i];
sct[idx][i].se=i;
}
sort(sct[idx].begin(), sct[idx].end());
if(s==e) return;
int mid=(s+e)/2;
make_seg(2*idx, s, mid);
make_seg(2*idx+1 ,mid+1, e);
}
pii seg_solv(int ii, int idx, int s1, int e1, int s2, int e2)
{
if(s1>e2 || s2>e1) return pii(1, 0);
if(s2<=s1 && e1<=e2) return seg[ii][idx];
int mid=(s1+e1)/2;
pii ret1=seg_solv(ii, 2*idx, s1, mid, s2, e2), ret2=seg_solv(ii, 2*idx+1, mid+1, e1, s2, e2);
if(ret1.se-ret1.fi<ret2.se-ret2.fi) return ret2;
else return ret1;
}
pii f(int idx, pii xy)
{
//printf("idx=%d, xy=%d, %d\n", idx, xy.fi, xy.se);
int l=upper_bound(st[idx].begin(), st[idx].end(), xy.fi)-st[idx].begin()-1;
int r=upper_bound(st[idx].begin(), st[idx].end(), N-xy.se)-st[idx].begin()-1;
pii rng=seg_solv(idx, 1, 0, ct[idx].size()-1, l, r);
//printf("rng=%d, %d\n", rng.fi, rng.se);
int pos=lower_bound(sct[idx].begin(), sct[idx].end(), pair<pii, int>(rng, -1))-sct[idx].begin();
pos=sct[idx][pos].se;
//printf("pos=%d\n", pos);
if(pos!=0 && ct[idx][pos].fi<=ct[idx][pos-1].fi && ct[idx][pos-1].se<=ct[idx][pos].se) rng.fi=ct[idx][pos-1].se+1;
if(pos!=ct[idx].size()-1 && ct[idx][pos].fi<=ct[idx][pos+1].fi && ct[idx][pos+1].se<=ct[idx][pos].se) rng.se=ct[idx][pos+1].fi-1;
//printf("rng=%d, %d\n", rng.fi, rng.se);
xy.fi=max(xy.fi, rng.fi);
xy.se=max(xy.se, N-rng.se);
return xy;
}
pii solv(int idx, int s1, int e1, int s2, int e2, pii xy)
{
if(s2>e1 || s1>e2) return xy;
if(s2<=s1 && e1<=e2) return f(idx, xy);
int mid=(s1+e1)/2;
pii xy1=solv(2*idx, s1, mid, s2, e2, xy);
return solv(2*idx+1, mid+1, e1, s2, e2, xy1);
}
int main()
{
gibon
input();
make_seg(1, 1, Q);
for(int i=1;i<=Q;i++) if(B[i].typ==1)
{
pii ret=solv(1, 1, Q, tim[B[i].a], i, A[B[i].a]);
//printf("i=%d\n", i);
cout << ret.fi << " " << ret.se << '\n';
}
}
Compilation message
sweeping.cpp: In function 'void make_seg(int, int, int)':
sweeping.cpp:141:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
141 | for(int i=0;i<v.size();i++)
| ~^~~~~~~~~
sweeping.cpp:163:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
163 | for(int i=0;i<ct[idx].size();i++)
| ~^~~~~~~~~~~~~~~
sweeping.cpp: In function 'std::pair<int, int> f(int, std::pair<int, int>)':
sweeping.cpp:194:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
194 | if(pos!=ct[idx].size()-1 && ct[idx][pos].fi<=ct[idx][pos+1].fi && ct[idx][pos+1].se<=ct[idx][pos].se) rng.se=ct[idx][pos+1].fi-1;
| ~~~^~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
188 ms |
378696 KB |
Output is correct |
| 2 |
Correct |
193 ms |
379236 KB |
Output is correct |
| 3 |
Correct |
174 ms |
377676 KB |
Output is correct |
| 4 |
Correct |
194 ms |
378640 KB |
Output is correct |
| 5 |
Correct |
212 ms |
379616 KB |
Output is correct |
| 6 |
Correct |
189 ms |
377752 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9426 ms |
1219804 KB |
Output is correct |
| 2 |
Correct |
9376 ms |
1219916 KB |
Output is correct |
| 3 |
Correct |
9204 ms |
1219840 KB |
Output is correct |
| 4 |
Runtime error |
5162 ms |
1579560 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10427 ms |
1291460 KB |
Output is correct |
| 2 |
Correct |
10377 ms |
1287576 KB |
Output is correct |
| 3 |
Incorrect |
8882 ms |
1302344 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10427 ms |
1291460 KB |
Output is correct |
| 2 |
Correct |
10377 ms |
1287576 KB |
Output is correct |
| 3 |
Incorrect |
8882 ms |
1302344 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
188 ms |
378696 KB |
Output is correct |
| 2 |
Correct |
193 ms |
379236 KB |
Output is correct |
| 3 |
Correct |
174 ms |
377676 KB |
Output is correct |
| 4 |
Correct |
194 ms |
378640 KB |
Output is correct |
| 5 |
Correct |
212 ms |
379616 KB |
Output is correct |
| 6 |
Correct |
189 ms |
377752 KB |
Output is correct |
| 7 |
Correct |
9426 ms |
1219804 KB |
Output is correct |
| 8 |
Correct |
9376 ms |
1219916 KB |
Output is correct |
| 9 |
Correct |
9204 ms |
1219840 KB |
Output is correct |
| 10 |
Runtime error |
5162 ms |
1579560 KB |
Execution killed with signal 11 |
| 11 |
Halted |
0 ms |
0 KB |
- |
