oj.uz

Submission #302806

# Submission time Handle Problem Language Result Execution time Memory
302806 2020-09-19T08:43:21 Z David_M Comparing Plants (IOI20_plants) C++14
44 / 100
 778 ms 51304 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;
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);
		}
	}	
}
int compare_plants(int x, int y) {
	return (int)(ans[x+1]>ans[y+1])-(ans[y+1]>ans[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;
      |          ~^~

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

Subtask #2
14.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 Correct 1 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 4 ms 512 KB Output is correct
7 Correct 82 ms 3704 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 4 ms 512 KB Output is correct
10 Correct 81 ms 3704 KB Output is correct
11 Correct 77 ms 3528 KB Output is correct
12 Correct 81 ms 4220 KB Output is correct
13 Correct 81 ms 3700 KB Output is correct

Subtask #3
13.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 Correct 1 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 4 ms 512 KB Output is correct
7 Correct 82 ms 3704 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 4 ms 512 KB Output is correct
10 Correct 81 ms 3704 KB Output is correct
11 Correct 77 ms 3528 KB Output is correct
12 Correct 81 ms 4220 KB Output is correct
13 Correct 81 ms 3700 KB Output is correct
14 Correct 118 ms 4864 KB Output is correct
15 Correct 722 ms 16944 KB Output is correct
16 Correct 144 ms 4984 KB Output is correct
17 Correct 770 ms 16972 KB Output is correct
18 Correct 430 ms 16888 KB Output is correct
19 Correct 713 ms 34168 KB Output is correct
20 Correct 670 ms 16888 KB Output is correct

Subtask #4
17.0 / 17.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 74 ms 3448 KB Output is correct
4 Correct 531 ms 28536 KB Output is correct
5 Correct 644 ms 19576 KB Output is correct
6 Correct 778 ms 17144 KB Output is correct
7 Correct 755 ms 17016 KB Output is correct
8 Correct 734 ms 17016 KB Output is correct
9 Correct 668 ms 17928 KB Output is correct
10 Correct 611 ms 19320 KB Output is correct
11 Correct 325 ms 17016 KB Output is correct
12 Correct 660 ms 51304 KB Output is correct
13 Correct 415 ms 16892 KB Output is correct

Subtask #5
0 / 11.0

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

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