#include<bits/stdc++.h>
using namespace std ;
#define maxn 1000009
#define ll long long
#define fi first
#define se second
#define pb push_back
#define left id<<1
#define right id<<1|1
#define re exit(0);
#define _lower(v,x) lower_bound(v.begin(),v.end(),x)-v.begin()+1
const int mod = 1e9+7 ;
const int INF = 1e9 ;
const int LOG = 18 ;
typedef vector<int> vi ;
typedef pair<int,int> pii ;
typedef vector<pii> vii ;
typedef vector<ll> vl ;
typedef pair<ll,ll> pll ;
typedef vector<pll> vll ;
void add ( int&a , int b ) { if ((a+=b) > mod ) a -= mod ; }
void sub ( int&a , int b ) { if ((a-=b) < 0 ) a += mod ; }
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
void rf ( )
{
freopen ("bai1.inp","r",stdin) ;
// freopen ("bai1.out","w",stdout) ;
}
int _pow ( int a , int n )
{
if ( n == 0 ) return 1 ;
int res = _pow ( a , n / 2 ) ;
if ( n % 2 ) return ( 1ll * res * res % mod * a % mod ) ;
else return ( 1ll * res * res % mod ) ;
}
int n , m , nq ;
struct point {
int x , y , fac ;
} a [maxn] ;
struct query{
int T , p , L ;
int x , y ;
int fac ;
} q [maxn] ;
const int N = 1e6 ;
const int maxN = 1e6+9 ;
void sub1 ()
{
for ( int r = 1 ; r <= nq ; r ++ )
{
if ( q[r].T == 1 )
{
cout << a [q[r].p].x << " " << a [q[r].p].y << "\n" ;
}
else if ( q [r].T == 2 )
{
for ( int i = 1 ; i <= m ; i ++ )
{
if ( a [i].x < n - q[r].L && a [i].y <= q[r].L ) a [i].x = n - q[r].L ;
}
}
else if ( q [r].T == 3 )
{
for ( int i = 1 ; i <= m ; i ++ )
{
if ( a [i].y < n - q[r].L && a [i].x <= q[r].L ) a [i].y = n - q[r].L ;
}
}
else
{
a [q[r].p] = {q[r].x,q[r].y} ;
}
}
}
bool check_sub2 ()
{
for ( int i = 1 ; i <= nq ; i ++ ) if ( q[i].T == 3 ) return false ;
return true ;
}
int fac [maxN] ;
void mapping ()
{
vi v ;
map <int,int> mp ;
for ( int i = 1 ; i <= m ; i ++ ) v . pb (a[i].y) ;
for ( int i = 1 ; i <= nq ; i ++ )
{
if ( q[i].T == 2 ) v . pb (q[i].L) ;
}
sort (v.begin(),v.end()) ;
for ( int i = 1 ; i <= m ; i ++ )
{
a [i].fac = _lower(v,a[i].y) + mp [_lower(v,a[i].y)] ++ ;
}
for ( int i = 1 ; i <= nq ; i ++ )
{
if ( q[i].T == 2 ) q[i].fac = _lower(v,q[i].L) + mp [_lower(v,q[i].L)] ++ ;
}
for ( int i = 0 ; i < v.size () ; i ++ ) fac [i+1] = v [i] ;
}
int T [maxN*4] , lazy [maxN*4] ;
void down ( int id )
{
int &t = lazy [id] ;
chkmax (T[left],t) , chkmax (T[right],t) ;
chkmax (lazy[left],t) , chkmax (lazy[right],t) ;
t = 0 ;
}
void update ( int id , int l , int r , int u , int v , int w , int force )
{
if ( l > v || r < u ) return ;
if ( u <= l && r <= v )
{
if ( l == r && force == 1 )
{
T [id] = w ;
return ;
}
else
{
chkmax (T[id],w) , chkmax (lazy[id],w) ;
return ;
}
}
down (id) ;
int mid = (l+r)/2 ;
update (left,l,mid,u,v,w,force) ;
update (right,mid+1,r,u,v,w,force) ;
}
int get ( int id , int l , int r , int pos )
{
if ( l > pos || r < pos ) return 0 ;
if ( l == r ) return T [id] ;
down (id) ;
int mid = (l+r)/2 ;
return get (left,l,mid,pos) + get (right,mid+1,r,pos) ;
}
void sub2 ()
{
mapping () ;
for ( int i = 1 ; i <= m ; i ++ ) update (1,1,N,a[i].fac,a[i].fac,a[i].x,1) ;
for ( int r = 1 ; r <= nq ; r ++ )
{
if ( q[r].T == 1 )
{
int num = q[r].p ;
int x = get (1,1,N,a[num].fac) ;
cout << x << " " << a [num].y << "\n" ;
}
else if ( q[r].T == 2 )
{
int L = q[r].fac ;
update (1,1,N,1,L,n-q[r].L,0) ;
}
else if ( q[r].T == 4 )
{
int num = a[q[r].p].fac ;
update (1,1,N,num,num,q[r].x,1) ;
}
}
}
int main ( )
{
ios_base :: sync_with_stdio (0) ;
cin.tie(0) ; cout.tie(0) ;
// rf () ;
cin >> n >> m >> nq ;
for ( int i = 1 ; i <= m ; i ++ ) cin >> a [i].x >> a [i].y ;
// T = 2 push x
// T = 3 push y
for ( int i = 1 ; i <= nq ; i ++ )
{
cin >> q[i].T ;
if ( q[i].T == 1 ) cin >> q[i].p ;
else if ( q[i].T == 2 ) cin >> q[i].L ;
else if ( q[i].T == 3 ) cin >> q[i].L ;
else
{
int x , y ; cin >> x >> y ;
q [i].p = ++ m ;
a [m] = {x,y} ;
q [i].x = x , q [i].y = y ;
}
}
if ( m <= 7e3 && nq <= 5e3 ) sub1 () ;
else if (check_sub2 () ) sub2 () ;
}
//-std=c++11
Compilation message
sweeping.cpp: In function 'void mapping()':
sweeping.cpp:114:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for ( int i = 0 ; i < v.size () ; i ++ ) fac [i+1] = v [i] ;
| ~~^~~~~~~~~~~
sweeping.cpp: In function 'void rf()':
sweeping.cpp:31:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
31 | freopen ("bai1.inp","r",stdin) ;
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
4440 KB |
Output is correct |
| 2 |
Correct |
5 ms |
4696 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4440 KB |
Output is correct |
| 4 |
Correct |
10 ms |
4700 KB |
Output is correct |
| 5 |
Correct |
27 ms |
4444 KB |
Output is correct |
| 6 |
Correct |
6 ms |
4440 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2177 ms |
108460 KB |
Output is correct |
| 2 |
Correct |
2514 ms |
108576 KB |
Output is correct |
| 3 |
Correct |
2292 ms |
108452 KB |
Output is correct |
| 4 |
Correct |
1551 ms |
108264 KB |
Output is correct |
| 5 |
Correct |
1554 ms |
108520 KB |
Output is correct |
| 6 |
Correct |
2128 ms |
108560 KB |
Output is correct |
| 7 |
Correct |
2200 ms |
108456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
183 ms |
31176 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
183 ms |
31176 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
4440 KB |
Output is correct |
| 2 |
Correct |
5 ms |
4696 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4440 KB |
Output is correct |
| 4 |
Correct |
10 ms |
4700 KB |
Output is correct |
| 5 |
Correct |
27 ms |
4444 KB |
Output is correct |
| 6 |
Correct |
6 ms |
4440 KB |
Output is correct |
| 7 |
Correct |
2177 ms |
108460 KB |
Output is correct |
| 8 |
Correct |
2514 ms |
108576 KB |
Output is correct |
| 9 |
Correct |
2292 ms |
108452 KB |
Output is correct |
| 10 |
Correct |
1551 ms |
108264 KB |
Output is correct |
| 11 |
Correct |
1554 ms |
108520 KB |
Output is correct |
| 12 |
Correct |
2128 ms |
108560 KB |
Output is correct |
| 13 |
Correct |
2200 ms |
108456 KB |
Output is correct |
| 14 |
Incorrect |
183 ms |
31176 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
