oj.uz

Submission #303533

# Submission time Handle Problem Language Result Execution time Memory
303533 2020-09-20T11:38:39 Z David_M Comparing Plants (IOI20_plants) C++14
15 / 100
 944 ms 29944 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=2000006, INF=1e9+7;
int k, n, t[N], dist[N], tt[N], ans[N], Ans, u, o, f[N], ff[N];
set <int> s;
set <pair<int, int> > q;
pair <int, int> p[N];
vector <int> rr;
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 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);
		}
	}	
	f[1]=ff[1]=1;
	
	q.insert({-ans[1], 1});
	o=2;
	while(q.size() && o<=n){
		int u=-(*q.begin()).F;
		if(ans[o]<u){
			f[o]=1;
			q.insert({-ans[o], o});
		}
		if(o>k&&f[o-k]){
			q.erase({-ans[o-k], o-k});
		}
		o++;
	}
	q.clear();
	q.insert({ans[1], 1});
	o=2;
	while(q.size() && o<=n){
		int u=(*q.begin()).F;
		if(ans[o]>u){
			ff[o]=1;
			q.insert({ans[o], o});
		}
		if(o>k&&ff[o-k]){
			q.erase({ans[o-k], o-k});
		}
		o++;
	}
	q.clear();
	q.insert({-ans[1], 1});
	o=n;
	while(q.size()&&o>1){
		int u=-(*q.begin()).F;
		if(ans[o]<u){
			f[o]=1;
			q.insert({-ans[o], o});
		}
		int h=o+k;
		if(h==n+1)h=1;
		if(o+k<n+2&&f[h]){
			q.erase({-ans[h], h});
		}
		o--;
	}
	q.clear();
	q.insert({ans[1], 1});
	o=n;
	while(q.size()&&o>1){
		int u=(*q.begin()).F;
		if(ans[o]>u){
			ff[o]=1;
			q.insert({ans[o], o});
		}
		int h=o+k;
		if(h==n+1)h=1;
		if(o+k<n+2&&ff[h]){
			q.erase({ans[h], h});
		}		
		o--;
	}
  
}
int compare_plants(int x, int y) {
	return f[y+1]-ff[y+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;
      |          ~^~

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 Incorrect 0 ms 384 KB Output isn't correct
4 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 1 ms 384 KB Output is correct
3 Incorrect 0 ms 384 KB Output isn't correct
4 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 1 ms 384 KB Output is correct
3 Incorrect 0 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.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 Incorrect 0 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 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 3 ms 384 KB Output is correct
6 Correct 938 ms 17400 KB Output is correct
7 Correct 900 ms 18296 KB Output is correct
8 Correct 934 ms 19064 KB Output is correct
9 Correct 944 ms 22648 KB Output is correct
10 Correct 637 ms 18040 KB Output is correct
11 Correct 668 ms 21308 KB Output is correct
12 Correct 533 ms 29944 KB Output is correct
13 Correct 631 ms 20600 KB Output is correct
14 Correct 891 ms 18808 KB Output is correct
15 Correct 904 ms 18936 KB Output is correct
16 Correct 656 ms 22092 KB Output is correct
17 Correct 660 ms 18040 KB Output is correct

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 Incorrect 0 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -