oj.uz

답안 #894600

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
894600 2023-12-28T14:13:57 Z thunopro 청소 (JOI20_sweeping) C++14
11 / 100
 2514 ms 108576 KB 
#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) ;
      |  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 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

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 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

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 183 ms 31176 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 183 ms 31176 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 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 -