oj.uz

Submission #302864

# Submission time Handle Problem Language Result Execution time Memory
302864 2020-09-19T10:16:29 Z David_M Comparing Plants (IOI20_plants) C++14
11 / 100
 128 ms 12792 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];
		if(!path[X][y])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];
		if(!path[X][y])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

# Verdict Execution time Memory 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 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 64 ms 3268 KB Output is correct
7 Runtime error 128 ms 12792 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory 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 0 ms 384 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Runtime error 11 ms 768 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory 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 0 ms 384 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Runtime error 11 ms 768 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Runtime error 62 ms 5752 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 544 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 3 ms 512 KB Output is correct
7 Correct 16 ms 1408 KB Output is correct
8 Correct 20 ms 1536 KB Output is correct
9 Correct 23 ms 1408 KB Output is correct
10 Correct 21 ms 1536 KB Output is correct
11 Correct 17 ms 1408 KB Output is correct
12 Correct 18 ms 1408 KB Output is correct
13 Correct 24 ms 1920 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory 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 Runtime error 9 ms 896 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory 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 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 64 ms 3268 KB Output is correct
7 Runtime error 128 ms 12792 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -