oj.uz

Submission #302814

# Submission time Handle Problem Language Result Execution time Memory
302814 2020-09-19T08:52:08 Z David_M Comparing Plants (IOI20_plants) C++14
44 / 100
 787 ms 51364 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;
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 288 KB Output is correct
2 Correct 1 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 4 ms 512 KB Output is correct
7 Correct 82 ms 3596 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 4 ms 512 KB Output is correct
10 Correct 82 ms 3704 KB Output is correct
11 Correct 77 ms 3488 KB Output is correct
12 Correct 84 ms 4196 KB Output is correct
13 Correct 82 ms 3704 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1 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 4 ms 512 KB Output is correct
7 Correct 82 ms 3596 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 4 ms 512 KB Output is correct
10 Correct 82 ms 3704 KB Output is correct
11 Correct 77 ms 3488 KB Output is correct
12 Correct 84 ms 4196 KB Output is correct
13 Correct 82 ms 3704 KB Output is correct
14 Correct 121 ms 4868 KB Output is correct
15 Correct 742 ms 16952 KB Output is correct
16 Correct 122 ms 5112 KB Output is correct
17 Correct 725 ms 16944 KB Output is correct
18 Correct 434 ms 16888 KB Output is correct
19 Correct 726 ms 34168 KB Output is correct
20 Correct 659 ms 17016 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 1 ms 384 KB Output is correct
3 Correct 76 ms 3448 KB Output is correct
4 Correct 536 ms 28332 KB Output is correct
5 Correct 648 ms 19448 KB Output is correct
6 Correct 787 ms 17272 KB Output is correct
7 Correct 753 ms 17016 KB Output is correct
8 Correct 739 ms 16948 KB Output is correct
9 Correct 671 ms 18040 KB Output is correct
10 Correct 626 ms 19320 KB Output is correct
11 Correct 333 ms 16836 KB Output is correct
12 Correct 661 ms 51364 KB Output is correct
13 Correct 414 ms 17108 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 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 -