oj.uz

답안 #302861

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
302861 2020-09-19T09:58:30 Z David_M 식물 비교 (IOI20_plants) C++14
0 / 100
 4000 ms 12664 KB 
//#include "plants.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define S second
#define F first
using namespace std;
const int N=4000006, INF=1e9+7;
int k, n, t[N], dist[N], tt[N], ans[N], Ans, u, o, path[310][310];
set <int> s;
set <pair<int, int> > q;
pair <int, int> p[N];
vector <int> rr, g[310], gg[310];
queue <int> Q;
 
void build(int l, int r, int x){
	if(l==r){t[x]=rr[l-1]; p[x]=make_pair(l, l); return;}
	
	int mid=l+r>>1; 
	build(l, mid, x<<1);
	build(mid+1, r, x<<1|1);
	t[x]=max(t[x<<1], t[x<<1|1]);
	
	if(t[x]==t[x<<1])p[x].F=p[x<<1].F;
	else p[x].F=p[x<<1|1].F;
	
	if(t[x]==t[x<<1|1])p[x].S=p[x<<1|1].S;
	else p[x].S=p[x<<1].S;
}
void push(int x){
	t[x]+=tt[x];
	tt[x<<1]+=tt[x];
	tt[x<<1|1]+=tt[x];
	tt[x]=0;
}
void upd(int l, int r, int d, int L, int R, int x){
	if(L>r||R<l)return;
	if(L==l && R==r){ tt[x]+=d; return; }
	push(x);
	int mid=L+R>>1;
	upd(l, min(mid, r), d, L, mid, x<<1);
	upd(max(l, mid+1), r, d, mid+1, R, x<<1|1);
	
	push(x<<1);
	push(x<<1|1);
	t[x]=max(t[x<<1], t[x<<1|1]);
	
	if(t[x]==t[x<<1])p[x].F=p[x<<1].F;
	else p[x].F=p[x<<1|1].F;
	
	if(t[x]==t[x<<1|1])p[x].S=p[x<<1|1].S;
	else p[x].S=p[x<<1].S;
}
pair<int, int> ffm(int l, int r, int L, int R, int x){
	if(l>r)return make_pair(-1, -1);
	if(L==R)return make_pair(L, t[x]+tt[x]);
	int mid=L+R>>1;
	push(x);
	push(x<<1);
	push(x<<1|1);
	if(t[x<<1]==t[x]&&p[x<<1].S>=l)return ffm(l, min(mid, r), L, mid, x<<1);
	else return ffm(max(l, mid+1), r, mid+1, R, x<<1|1);
}
int prev(int x){
	set<int>::iterator it=s.lower_bound(x);
	if(it==s.begin())it=s.end();
	it--; 
	return *it;
}
int next(int x){
	set<int>::iterator it=s.lower_bound(x);
	if(it==s.end())it=s.begin();
	return *it;
}
void fm(int l, int r){
	pair<int, int> pp=ffm(l, r, 1, n, 1);
	
	int x=pp.F;
	if(pp.S!=k)return;
	
	if(!s.size()){
		s.insert(x);
		q.insert(make_pair(-n, x));
		dist[x]=n;
		fm(x+1, r);
		return;
	}
	int pr=prev(x);
	int nx=next(x);
	s.insert(x);
	
	pair<int, int> p=make_pair(-dist[nx], nx);
	q.erase(p);
	dist[nx]=(nx+n-x)%n;
	q.insert(make_pair(-dist[nx], nx));
	
	dist[x]=(x+n-pr)%n;
	q.insert(make_pair(-dist[x], x));
	
	fm(x+1, r);
}
void upd(int x){
	upd(x, x, -INF, 1, n, 1);
	int l=x-k, r=x-1;
	l+=(l<1)*n;
	r+=(r<1)*n;
	if(l<=r){
		upd(l, r, 1, 1, n, 1);
		fm(l, r);
	}
	else{
		upd(1, r, 1, 1, n, 1);
		upd(l, n, 1, 1, n, 1);
		fm(1, r);
		fm(l, n);
	}
}

void dfs(int x, int X){
	path[X][x]=1;
	for (int i=0; i<g[x].size(); i++){
		int y=g[x][i];
		dfs(y, X);
	}
}

void Dfs(int x, int X){
	path[X][x]=1;
	for (int i=0; i<gg[x].size(); i++){
		int y=gg[x][i];
		Dfs(y, X);
	}
}
void init(int kk, vector<int> rrr){
	k=kk-1;
	n=rrr.size();
	rr=rrr;
	build(1, n, 1);
	fm(1, n);
	
	while(q.size()){
		Ans++;
 
		while(q.size()>0 && -(*q.begin()).F>k){
			Q.push((*q.begin()).S);
			s.erase((*q.begin()).S);
			q.erase(q.begin());
		}
		while(!Q.empty()){
			
			int x=Q.front();
			if(s.size()>0){
				int nx=next(x);
				int pr=prev(x);
				pair<int, int> p=make_pair(-dist[nx], nx);
				q.erase(p);
				dist[nx]=(nx+n-pr)%n;
				if(dist[nx]==0)dist[nx]=n;
				q.insert(make_pair(-dist[nx], nx));	
			}		
			ans[x]=Ans;
			Q.pop();
			upd(x);
		}
	}	
	
	for (int i=1; i<=n; i++){
		for (int j=i+1; j<=i+k; j++){
			int J=j;
			if(J>n)J-=n;
			if(ans[i]>ans[J]){
				g[i].pb(J);
			}
			if(ans[i]<ans[J]){
				gg[J].pb(i);
			}
		}
	}
	
	for (int i=1; i<=n; i++){
		dfs(i, i);
		Dfs(i, i);
	}
	
}
int compare_plants(int x, int y) {
	return path[x+1][y+1]-path[y+1][x+1];
}

Compilation message

plants.cpp: In function 'void build(int, int, int)':
plants.cpp:19:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |  int mid=l+r>>1;
      |          ~^~
plants.cpp: In function 'void upd(int, int, int, int, int, int)':
plants.cpp:40:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |  int mid=L+R>>1;
      |          ~^~
plants.cpp: In function 'std::pair<int, int> ffm(int, int, int, int, int)':
plants.cpp:57:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |  int mid=L+R>>1;
      |          ~^~
plants.cpp: In function 'void dfs(int, int)':
plants.cpp:121:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |  for (int i=0; i<g[x].size(); i++){
      |                ~^~~~~~~~~~~~
plants.cpp: In function 'void Dfs(int, int)':
plants.cpp:129:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |  for (int i=0; i<gg[x].size(); i++){
      |                ~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 60 ms 3320 KB Output is correct
7 Runtime error 119 ms 12664 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Execution timed out 4029 ms 384 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Execution timed out 4029 ms 384 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Runtime error 63 ms 5752 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 22 ms 1528 KB Output is correct
8 Execution timed out 4050 ms 1152 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Runtime error 9 ms 896 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 60 ms 3320 KB Output is correct
7 Runtime error 119 ms 12664 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -