oj.uz

답안 #317655

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
317655 2020-10-30T06:07:00 Z arnold518 식물 비교 (IOI20_plants) C++14
0 / 100
 18 ms 23808 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;

vector<int> adj[MAXN+10];
int LL[MAXN+10], RR[MAXN+10], dfn;

void dfs(int now)
{
	LL[now]=++dfn;
	for(int nxt : adj[now]) dfs(nxt);
	RR[now]=dfn;
}

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();

	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);
	vector<int> root;
	for(int i=0; i<V.size(); i++)
	{
		int now=V[i].second;
		pii t=seg3.query(now-K+1, now+K-1);
		if(t.first!=INF) adj[t.second].push_back(i);
		else root.push_back(i);
		seg3.update2(now, V[i].first);
	}
	for(auto it : root) dfs(it);
	return;
}

int compare_plants(int x, int y)
{
	if(LL[x]<=LL[y] && RR[y]<=RR[x]) return 1;
	if(LL[y]<=LL[x] && RR[x]<=RR[y]) 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:177: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]
  177 |  for(int i=0; i<V.size(); i++)
      |               ~^~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 23808 KB Output is correct
2 Correct 14 ms 23808 KB Output is correct
3 Incorrect 18 ms 23808 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23808 KB Output is correct
2 Correct 15 ms 23808 KB Output is correct
3 Incorrect 14 ms 23808 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23808 KB Output is correct
2 Correct 15 ms 23808 KB Output is correct
3 Incorrect 14 ms 23808 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 23808 KB Output is correct
2 Correct 15 ms 23808 KB Output is correct
3 Incorrect 14 ms 23808 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23808 KB Output is correct
2 Correct 15 ms 23808 KB Output is correct
3 Incorrect 15 ms 23808 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 23808 KB Output is correct
2 Correct 14 ms 23808 KB Output is correct
3 Incorrect 18 ms 23808 KB Output isn't correct
4 Halted 0 ms 0 KB -