oj.uz

답안 #318174

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
318174 2020-10-31T14:59:14 Z arnold518 식물 비교 (IOI20_plants) C++14
5 / 100
 1234 ms 129440 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;
const int INF = 1e8;

int N, K, R[MAXN+10], H[MAXN+10];

struct SEG
{
	pii tree[MAXN*4+10];
	int lazy[MAXN*4+10];

	void busy(int node, int tl, int tr)
	{
		tree[node].first+=lazy[node];
		if(tl!=tr)
		{
			lazy[node*2]+=lazy[node];
			lazy[node*2+1]+=lazy[node];
		}
		lazy[node]=0;
	}
	void init(int node, int tl, int tr)
	{
		if(tl==tr)
		{
			tree[node]={0, tl};
			lazy[node]=0;
			return;
		}
		int mid=tl+tr>>1;
		init(node*2, tl, mid);
		init(node*2+1, mid+1, tr);
		tree[node]=min(tree[node*2], tree[node*2+1]);
	}
	void update(int node, int tl, int tr, int l, int r, int k)
	{
		busy(node, tl, tr);
		if(l<=tl && tr<=r)
		{
			lazy[node]+=k;
			busy(node, tl, tr);
			return;
		}
		if(r<tl || tr<l) return;
		int mid=tl+tr>>1;
		update(node*2, tl, mid, l, r, k);
		update(node*2+1, mid+1, tr, l, r, k);
		tree[node]=min(tree[node*2], tree[node*2+1]);
	}
	void update2(int node, int tl, int tr, int p, int k)
	{
		busy(node, tl, tr);
		if(tl==tr)
		{
			tree[node].first=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);
		tree[node]=min(tree[node*2], tree[node*2+1]);
	}
	pii query(int node, int tl, int tr, int l, int r)
	{
		busy(node, tl, tr);
		if(l<=tl && tr<=r) return tree[node];
		if(r<tl || tr<l) return {INF, -1};
		int mid=tl+tr>>1;
		return min(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r));
	}
	void query2(int node, int tl, int tr, int l, int r, vector<int> &V)
	{
		busy(node, tl, tr);
		if(tree[node].first!=0) return;
		if(r<tl || tr<l) return;
		if(tl==tr)
		{
			V.push_back(tl);
			return;
		}
		int mid=tl+tr>>1;
		query2(node*2, tl, mid, l, r, V);
		query2(node*2+1, mid+1, tr, l, r, V);
	}
	void init()
	{
		init(1, 0, N-1);
	}
	void update(int l, int r, int k)
	{
		l=(l%N+N)%N; r=(r%N+N)%N;
		if(l<=r) update(1, 0, N-1, l, r, k);
		else
		{
			update(1, 0, N-1, l, N-1, k);
			update(1, 0, N-1, 0, r, k);
		}
	}
	void update2(int p, int k)
	{
		p=(p%N+N)%N;
		update2(1, 0, N-1, p, k);
	}
	pii query(int l, int r)
	{
		l=(l%N+N)%N; r=(r%N+N)%N;
		if(l<=r) return query(1, 0, N-1, l, r);
		else return min(query(1, 0, N-1, l, N-1), query(1, 0, N-1, 0, r));
	}
	vector<int> query2(int l, int r)
	{
		vector<int> ret;
		l=(l%N+N)%N; r=(r%N+N)%N;
		if(l<=r) query2(1, 0, N-1, l, r, ret);
		else
		{
			query2(1, 0, N-1, l, N-1, ret);
			query2(1, 0, N-1, 0, r, ret);
		}
		return ret;
	}
}seg1, seg2, seg3;

int LL[MAXN*2+10][30], RR[MAXN*2+10][30];

void init(int _K, vector<int> _R)
{
	K=_K; N=_R.size();
	for(int i=0; i<N; i++) R[i]=_R[i];
	seg1.init(); seg2.init(); seg3.init();

	for(int i=0; i<N; i++)
	{
		seg1.update2(i, R[i]);
		seg2.update2(i, R[i]);
	}
	for(int i=0; i<N; i++) if(R[i]==0) seg1.update(i+1, i+K-1, 1);

	for(int i=N-1; i>=0; i--)
	{
		vector<int> V;
		assert(seg1.tree[1].first+seg1.lazy[1]==0);
		int now=seg1.tree[1].second; H[now]=i;
		assert(seg2.query(now-K+1, now-1).first>=1);
		seg1.update(now+1, now+K-1, -1);
		seg1.update2(now, INF);
		seg2.update2(now, INF);
		seg2.update(now-K+1, now-1, -1);
		seg1.update(now-K+1, now-1, -1);

		V=seg2.query2(now-K+1, now-1);
		for(auto it : V) seg1.update(it+1, it+K-1, 1);
	}
	//for(int i=0; i<N; i++) printf("%d ", H[i]); printf("\n");
	
	vector<pii> V;
	for(int i=0; i<N; i++) V.push_back({H[i], i});
	sort(V.begin(), V.end(), greater<pii>());
	
	for(int i=0; i<N; i++) seg3.update2(i, INF);

	memset(LL, -1, sizeof(LL));
	memset(RR, -1, sizeof(RR));
	for(int i=0; i<V.size(); i++)
	{
		int now=V[i].second;
		pii t1=seg3.query(now-K+1, now), t2=seg3.query(now, now+K-1);

		if(t1.first!=INF)
		{
			int p=t1.second;
			if(p<now)
			{
				LL[now][0]=p;
				LL[now+N][0]=p+N;
			}
			else
			{
				LL[now+N][0]=p;
			}
		}
		if(t2.first!=INF)
		{
			int p=t2.second;
			if(now<p)
			{
				RR[now][0]=p;
				RR[now+N][0]=p+N;
			}
			else
			{
				RR[now][0]=p+N;
			}
		}
		seg3.update2(now, H[now]);
	}
 	
	for(int i=1; i<=20; i++)
	{
		for(int j=0; j<N+N; j++)
		{
			if(LL[j][i-1]!=-1) LL[j][i]=LL[LL[j][i-1]][i-1];
			if(RR[j][i-1]!=-1) RR[j][i]=RR[RR[j][i-1]][i-1];
			//printf("%d %d / ", LL[j][i], RR[j][i]);
		}
		//printf("\n");
	}

	return;
}

int compare_plants(int x, int y)
{
	int ans=0;

	if(x<y)
	{
		if(H[x]<H[y])
		{
			int now=x+N;
			for(int i=20; i>=0; i--)
			{
				if(RR[now][i]!=-1 && RR[now][i]<y+N) now=RR[now][i];
			}
			if(RR[now][0]!=-1) now=RR[now][0];
			if(now>=y+N && H[now%N]<=H[y]) return -1;

			now=x+N;
			for(int i=20; i>=0; i--)
			{
				if(LL[now][i]!=-1 && LL[now][i]>y) now=LL[now][i];
			}
			if(LL[now][0]!=-1) now=LL[now][0];
			if(now<=y && H[now%N]<=H[y]) return -1;
		}
		else
		{
			int now=y;
			for(int i=20; i>=0; i--)
			{
				if(RR[now][i]!=-1 && RR[now][i]<x+N) now=RR[now][i];
			}
			if(RR[now][0]!=-1) now=RR[now][0];
			if(now>=x+N && H[now%N]<=H[x]) return 1;
			
			now=y;
			for(int i=20; i>=0; i--)
			{
				if(LL[now][i]!=-1 && LL[now][i]>x) now=LL[now][i];
			}
			if(LL[now][0]!=-1) now=LL[now][0];
			if(now<=x && H[now%N]<=H[x]) return 1;
		}
	}
	else
	{
		if(H[x]<H[y])
		{
			int now=x;
			for(int i=20; i>=0; i--)
			{
				if(RR[now][i]!=-1 && RR[now][i]<y+N) now=RR[now][i];
			}
			if(RR[now][0]!=-1) now=RR[now][0];
			if(now>=y+N && H[now%N]<=H[y]) return -1;

			now=x;
			for(int i=20; i>=0; i--)
			{
				if(LL[now][i]!=-1 && LL[now][i]>y) now=LL[now][i];
			}
			if(LL[now][0]!=-1) now=LL[now][0];
			if(now<=y && H[now%N]<=H[y]) return -1;
		}
		else
		{
			int now=y+N;
			for(int i=20; i>=0; i--)
			{
				if(RR[now][i]!=-1 && RR[now][i]<x+N) now=RR[now][i];
			}
			if(RR[now][0]!=-1) now=RR[now][0];
			if(now>=x+N && H[now%N]<=H[x]) return 1;
			
			now=y+N;
			for(int i=20; i>=0; i--)
			{
				if(LL[now][i]!=-1 && LL[now][i]>x) now=LL[now][i];
			}
			if(LL[now][0]!=-1) now=LL[now][0];
			if(now<=x && H[now%N]<=H[x]) return 1;
		}
	}
	return 0;
}

Compilation message

plants.cpp: In member function 'void SEG::init(int, int, int)':
plants.cpp:37:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |   int mid=tl+tr>>1;
      |           ~~^~~
plants.cpp: In member function 'void SEG::update(int, int, int, int, int, int)':
plants.cpp:52:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |   int mid=tl+tr>>1;
      |           ~~^~~
plants.cpp: In member function 'void SEG::update2(int, int, int, int, int)':
plants.cpp:65:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |   int mid=tl+tr>>1;
      |           ~~^~~
plants.cpp: In member function 'pii SEG::query(int, int, int, int, int)':
plants.cpp:75:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |   int mid=tl+tr>>1;
      |           ~~^~~
plants.cpp: In member function 'void SEG::query2(int, int, int, int, int, std::vector<int>&)':
plants.cpp:88:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |   int mid=tl+tr>>1;
      |           ~~^~~
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:171:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |  for(int i=0; i<V.size(); i++)
      |               ~^~~~~~~~~
plants.cpp: In function 'int compare_plants(int, int)':
plants.cpp:221:6: warning: unused variable 'ans' [-Wunused-variable]
  221 |  int ans=0;
      |      ^~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 113124 KB Output is correct
2 Correct 56 ms 113000 KB Output is correct
3 Correct 55 ms 113124 KB Output is correct
4 Correct 58 ms 113124 KB Output is correct
5 Correct 56 ms 112996 KB Output is correct
6 Correct 130 ms 115940 KB Output is correct
7 Correct 249 ms 117056 KB Output is correct
8 Correct 1103 ms 126420 KB Output is correct
9 Correct 1141 ms 129404 KB Output is correct
10 Correct 1163 ms 129300 KB Output is correct
11 Correct 1199 ms 129364 KB Output is correct
12 Correct 1201 ms 129440 KB Output is correct
13 Correct 1234 ms 129380 KB Output is correct
14 Correct 1221 ms 129364 KB Output is correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 113216 KB Output is correct
2 Correct 57 ms 113124 KB Output is correct
3 Correct 58 ms 113124 KB Output is correct
4 Correct 55 ms 113124 KB Output is correct
5 Incorrect 56 ms 113124 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 113216 KB Output is correct
2 Correct 57 ms 113124 KB Output is correct
3 Correct 58 ms 113124 KB Output is correct
4 Correct 55 ms 113124 KB Output is correct
5 Incorrect 56 ms 113124 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 113124 KB Output is correct
2 Correct 57 ms 113000 KB Output is correct
3 Incorrect 154 ms 116068 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 112996 KB Output is correct
2 Correct 55 ms 113124 KB Output is correct
3 Correct 55 ms 112996 KB Output is correct
4 Correct 57 ms 113128 KB Output is correct
5 Incorrect 55 ms 113120 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 113120 KB Output is correct
2 Correct 56 ms 113124 KB Output is correct
3 Correct 57 ms 112996 KB Output is correct
4 Incorrect 55 ms 112996 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 113124 KB Output is correct
2 Correct 56 ms 113000 KB Output is correct
3 Correct 55 ms 113124 KB Output is correct
4 Correct 58 ms 113124 KB Output is correct
5 Correct 56 ms 112996 KB Output is correct
6 Correct 130 ms 115940 KB Output is correct
7 Correct 249 ms 117056 KB Output is correct
8 Correct 1103 ms 126420 KB Output is correct
9 Correct 1141 ms 129404 KB Output is correct
10 Correct 1163 ms 129300 KB Output is correct
11 Correct 1199 ms 129364 KB Output is correct
12 Correct 1201 ms 129440 KB Output is correct
13 Correct 1234 ms 129380 KB Output is correct
14 Correct 1221 ms 129364 KB Output is correct
15 Correct 56 ms 113216 KB Output is correct
16 Correct 57 ms 113124 KB Output is correct
17 Correct 58 ms 113124 KB Output is correct
18 Correct 55 ms 113124 KB Output is correct
19 Incorrect 56 ms 113124 KB Output isn't correct
20 Halted 0 ms 0 KB -