답안 #262541

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
262541 2020-08-13T03:35:26 Z arnold518 청소 (JOI20_sweeping) C++14
0 / 100
2365 ms 128248 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 = 1.5e6;

struct Point
{
	int x, y, p;
};

struct Query
{
	int t, p, x, y;
};

int N, M, Q;
Point A[MAXN+10];
Query B[MAXN+10];
int pos[MAXN+10];

struct SEG
{
	vector<int> tree, lazy;

	SEG()
	{
		tree.resize(MAXN*4+10);
		lazy.resize(MAXN*4+10);
	}

	void busy(int node, int tl, int tr)
	{
		tree[node]=max(tree[node], lazy[node]);
		if(tl!=tr)
		{
			lazy[node*2]=max(lazy[node*2], lazy[node]);
			lazy[node*2+1]=max(lazy[node*2+1], lazy[node]);
		}
		lazy[node]=0;
	}

	void update(int node, int tl, int tr, int l, int r, int k)
	{
		busy(node, tl, tr);
		if(r<tl || tr<l) return;
		if(l<=tl && tr<=r)
		{
			lazy[node]=k;
			busy(node, tl, tr);
			return;
		}
		int mid=tl+tr>>1;
		update(node*2, tl, mid, l, r, k);
		update(node*2+1, mid+1, tr, l, r, k);
	}

	void update2(int node, int tl, int tr, int p, int k)
	{
		busy(node, tl, tr);
		if(tl==tr) { tree[node]=k; return; }
		int mid=tl+tr>>1;
		if(p<=mid) update2(node*2, tl, mid, p ,k);
		else update2(node*2+1, mid+1, tr, p, k);
	}

	int query(int node, int tl, int tr, int p)
	{
		busy(node, tl, tr);
		if(tl==tr) return tree[node];
		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);
	}
}segx, segy;

int main()
{
	scanf("%d%d%d", &N, &M, &Q);
	for(int i=1; i<=M; i++) scanf("%d%d", &A[i].x, &A[i].y), A[i].p=i;

	for(int i=1; i<=Q; i++)
	{
		scanf("%d", &B[i].t);
		if(B[i].t==1) scanf("%d", &B[i].p);
		else if(B[i].t==2) scanf("%d", &B[i].x);
		else if(B[i].t==3) scanf("%d", &B[i].x);
		else if(B[i].t==4)
		{
			scanf("%d%d", &B[i].x, &B[i].y);
			B[i].p=++M;
			A[M]={B[i].x, B[i].y, M};
		}
	}

	for(int i=1; i<=M; i++) segx.update2(1, 1, M, i, A[i].x);
	for(int i=1; i<=M; i++) segy.update2(1, 1, M, i, A[i].y);

	for(int i=1; i<=Q; i++)
	{
		if(B[i].t==1)
		{
			printf("%d %d\n", segx.query(1, 1, M, B[i].p), segy.query(1, 1, M, B[i].p));
		}
		else if(B[i].t==2)
		{
			int l, r;
			int lo=0, hi=M+1;
			while(lo+1<hi)
			{
				int mid=lo+hi>>1;
				if(A[mid].y<=B[i].x) hi=mid;
				else lo=mid;
			}
			l=hi;
			lo=0, hi=M+1;
			while(lo+1<hi)
			{
				int mid=lo+hi>>1;
				if(A[mid].x<=N-B[i].x) lo=mid;
				else hi=mid;
			}
			r=lo;
			segx.update(1, 1, M, l, r, N-B[i].x);
		}
		else if(B[i].t==3)
		{
			int l, r;
			int lo=0, hi=M+1;
			while(lo+1<hi)
			{
				int mid=lo+hi>>1;
				if(A[mid].y<=N-B[i].x) hi=mid;
				else lo=mid;
			}
			l=hi;
			lo=0, hi=M+1;
			while(lo+1<hi)
			{
				int mid=lo+hi>>1;
				if(A[mid].x<=B[i].x) lo=mid;
				else hi=mid;
			}
			r=lo;
			segy.update(1, 1, M, l, r, N-B[i].x);
		}
	}
}

Compilation message

sweeping.cpp: In member function 'void SEG::update(int, int, int, int, int, int)':
sweeping.cpp:56:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |   int mid=tl+tr>>1;
      |           ~~^~~
sweeping.cpp: In member function 'void SEG::update2(int, int, int, int, int)':
sweeping.cpp:65:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |   int mid=tl+tr>>1;
      |           ~~^~~
sweeping.cpp: In member function 'int SEG::query(int, int, int, int)':
sweeping.cpp:74:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |   int mid=tl+tr>>1;
      |           ~~^~~
sweeping.cpp: In function 'int main()':
sweeping.cpp:114:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |     int mid=lo+hi>>1;
      |             ~~^~~
sweeping.cpp:122:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  122 |     int mid=lo+hi>>1;
      |             ~~^~~
sweeping.cpp:135:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  135 |     int mid=lo+hi>>1;
      |             ~~^~~
sweeping.cpp:143:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  143 |     int mid=lo+hi>>1;
      |             ~~^~~
sweeping.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   82 |  scanf("%d%d%d", &N, &M, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:83:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   83 |  for(int i=1; i<=M; i++) scanf("%d%d", &A[i].x, &A[i].y), A[i].p=i;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   87 |   scanf("%d", &B[i].t);
      |   ~~~~~^~~~~~~~~~~~~~~
sweeping.cpp:88:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   88 |   if(B[i].t==1) scanf("%d", &B[i].p);
      |                 ~~~~~^~~~~~~~~~~~~~~
sweeping.cpp:89:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   89 |   else if(B[i].t==2) scanf("%d", &B[i].x);
      |                      ~~~~~^~~~~~~~~~~~~~~
sweeping.cpp:90:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   90 |   else if(B[i].t==3) scanf("%d", &B[i].x);
      |                      ~~~~~^~~~~~~~~~~~~~~
sweeping.cpp:93:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   93 |    scanf("%d%d", &B[i].x, &B[i].y);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 65 ms 94584 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1535 ms 128248 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2365 ms 126116 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2365 ms 126116 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 65 ms 94584 KB Output isn't correct
2 Halted 0 ms 0 KB -