oj.uz

답안 #246703

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
246703 2020-07-10T00:45:08 Z arnold518 청소 (JOI20_sweeping) C++14
0 / 100
 3510 ms 42360 KB 
#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;
const int MAXQ = 1e6;

struct Point
{
	int x, y;
};

int N, M, Q;
Point A[MAXM+10];

Point tree[MAXM*4+10];

void update(int node, int tl, int tr, int l, int r, Point p)
{
	if(l<=tl && tr<=r)
	{
		tree[node].x=max(tree[node].x, p.x);
		tree[node].y=max(tree[node].y, p.y);
		return;
	}
	if(r<tl || tr<l) return;
	int mid=tl+tr>>1;
	update(node*2, tl, mid, l, r, p);
	update(node*2+1, mid+1, tr, l, r, p);
}

Point query(int node, int tl, int tr, int p)
{
	if(tl==tr) return tree[node];
	tree[node*2].x=max(tree[node*2].x, tree[node].x);
	tree[node*2].y=max(tree[node*2].y, tree[node].y);
	tree[node*2+1].x=max(tree[node*2+1].x, tree[node].x);
	tree[node*2+1].y=max(tree[node*2+1].y, tree[node].y);

	int mid=tl+tr>>1;
	if(p<=mid) return query(node*2, tl, mid, p);
	else return query(node*2+1, mid+1, tr, p);
}

int main()
{
	int i, j;

	scanf("%d%d%d", &N, &M, &Q);
	for(i=1; i<=M; i++)
	{
		scanf("%d%d", &A[i].x, &A[i].y);
		update(1, 1, M, i, i, A[i]);
	}
	for(i=1; i<=Q; i++)
	{
		int t;
		scanf("%d", &t);
		if(t==1)
		{
			int p; Point r;
			scanf("%d", &p);
			r=query(1, 1, M, p);
			printf("%d %d\n", r.x, r.y);
		}
		else if(t==2)
		{
			int l, r, k;
			scanf("%d", &k);

			int lo=0, hi=M;
			while(lo+1<hi)
			{
				int mid=lo+hi>>1;
				if(query(1, 1, M, mid).y>k) lo=mid;
				else hi=mid;
			}
			l=hi;

			lo=1, hi=M+1;
			while(lo+1<hi)
			{
				int mid=lo+hi>>1;
				if(query(1, 1, M, mid).x<=N-k) lo=mid;
				else hi=mid;
			}
			r=lo;

			update(1, 1, M, l, r, {N-k, 0});
		}
		else if(t==3)
		{
			int l, r, k;
			scanf("%d", &k);

			int lo=0, hi=M;
			while(lo+1<hi)
			{
				int mid=lo+hi>>1;
				if(query(1, 1, M, mid).y>N-k) lo=mid;
				else hi=mid;
			}
			l=hi;

			lo=1, hi=M+1;
			while(lo+1<hi)
			{
				int mid=lo+hi>>1;
				if(query(1, 1, M, mid).x<=k) lo=mid;
				else hi=mid;
			}
			r=lo;

			update(1, 1, M, l, r, {0, N-k});
		}
	}
}

Compilation message

sweeping.cpp: In function 'void update(int, int, int, int, int, Point)':
sweeping.cpp:31:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
sweeping.cpp: In function 'Point query(int, int, int, int)':
sweeping.cpp:44:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
sweeping.cpp: In function 'int main()':
sweeping.cpp:78:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=lo+hi>>1;
             ~~^~~
sweeping.cpp:87:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=lo+hi>>1;
             ~~^~~
sweeping.cpp:103:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=lo+hi>>1;
             ~~^~~
sweeping.cpp:112:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=lo+hi>>1;
             ~~^~~
sweeping.cpp:51:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
sweeping.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &M, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &A[i].x, &A[i].y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t);
   ~~~~~^~~~~~~~~~
sweeping.cpp:66:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &p);
    ~~~~~^~~~~~~~~~
sweeping.cpp:73:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &k);
    ~~~~~^~~~~~~~~~
sweeping.cpp:98:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &k);
    ~~~~~^~~~~~~~~~

Subtask #1
0 / 1.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3510 ms 22428 KB Output is correct
2 Correct 3238 ms 42360 KB Output is correct
3 Correct 2590 ms 41084 KB Output is correct
4 Correct 2709 ms 41976 KB Output is correct
5 Incorrect 3053 ms 41884 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3510 ms 22428 KB Output is correct
2 Correct 3238 ms 42360 KB Output is correct
3 Correct 2590 ms 41084 KB Output is correct
4 Correct 2709 ms 41976 KB Output is correct
5 Incorrect 3053 ms 41884 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

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