oj.uz

Submission #800264

# Submission time Handle Problem Language Result Execution time Memory
800264 2023-08-01T12:52:55 Z alvingogo Comparing Plants (IOI20_plants) C++14
44 / 100
 383 ms 23740 KB 
#include "plants.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

vector<int> rk;
struct ST{
	struct no{
		pair<int,int> mn;
		int tag=0;
	};
	vector<no> st;
	void init(int x){
		st.resize(4*x);
	}
	void build(int v,int L,int R,vector<int>& a){
		if(L==R){
			st[v].mn={a[L],L};
			return;
		}
		int m=(L+R)/2;
		build(2*v+1,L,m,a);
		build(2*v+2,m+1,R,a);
		st[v].mn=min(st[2*v+1].mn,st[2*v+2].mn);
	}
	void upd(int v,int t){
		st[v].tag+=t;
		st[v].mn.fs+=t;
	}
	void pudo(int v){
		if(st[v].tag==0){
			return;
		}
		upd(2*v+1,st[v].tag);
		upd(2*v+2,st[v].tag);
		st[v].tag=0;
	}
	void update(int v,int L,int R,int l,int r,int t){
		if(l==L && r==R){
			upd(v,t);
			return;
		}
		pudo(v);
		int m=(L+R)/2;
		if(r<=m){
			update(2*v+1,L,m,l,r,t);
		}
		else if(l>m){
			update(2*v+2,m+1,R,l,r,t);
		}
		else{
			update(2*v+1,L,m,l,m,t);
			update(2*v+2,m+1,R,m+1,r,t);
		}
		st[v].mn=min(st[2*v+1].mn,st[2*v+2].mn);
	}
	pair<int,int> query(int v,int L,int R,int l,int r){
		if(L==l && r==R){
			return st[v].mn;
		}
		pudo(v);
		int m=(L+R)/2;
		if(r<=m){
			return query(2*v+1,L,m,l,r);
		}
		else if(l>m){
			return query(2*v+2,m+1,R,l,r);
		}
		else{
			return min(query(2*v+1,L,m,l,m),query(2*v+2,m+1,R,m+1,r));
		}
	}
}st;
int n,k;
set<int> s,ab;
void add(int x){
	if(!s.size()){
		s.insert(x);
		ab.insert(x);
		return;
	}
	auto a=s.lower_bound(x);
	auto b=a;
	if(a==s.end()){
		a=s.begin();
	}
	if(a==s.begin()){
		b=prev(s.end());
	}
	else{
		b=prev(a);
	}
	if((x-(*b)+n)%n>=k){
		ab.insert(x);
	}
	if(((*a)-x+n)%n<k){
		ab.erase(*a);
	}
	s.insert(x);
}
void del(int x){
	ab.erase(x);
	s.erase(x);
	if(!s.size()){
		return;
	}
	auto a=s.lower_bound(x);
	auto b=a;
	if(a==s.end()){
		a=s.begin();
	}
	if(a==s.begin()){
		b=prev(s.end());
	}
	else{
		b=prev(a);
	}
	ab.insert(*a);
}
void update(int l,int r){
	if(l>r){
		st.update(0,0,n-1,l,n-1,-1);
		st.update(0,0,n-1,0,r,-1);
		while(1){
			auto h=st.query(0,0,n-1,0,r);
			if(h.fs>0){
				break;
			}
			add(h.sc);
			st.update(0,0,n-1,h.sc,h.sc,10000008);
		}
		while(1){
			auto h=st.query(0,0,n-1,l,n-1);
			if(h.fs>0){
				break;
			}
			add(h.sc);
			st.update(0,0,n-1,h.sc,h.sc,10000008);
		}
	}
	else{
		st.update(0,0,n-1,l,r,-1);
		while(1){
			auto h=st.query(0,0,n-1,l,r);
			if(h.fs>0){
				break;
			}
			add(h.sc);
			st.update(0,0,n-1,h.sc,h.sc,10000008);
		}
	}
}
void init(int K, vector<int> r) {
	n=r.size();
	k=K;
	rk.resize(n);
	st.init(n);
	st.build(0,0,n-1,r);
	for(int i=0;i<n;i++){
		if(r[i]==0){
			add(i);
			st.update(0,0,n-1,i,i,10000007);
		}
	}
	for(int i=0;i<n;i++){
		auto h=*ab.begin();
		auto xl=(h+1-k+n)%n;
		auto xr=(h-1+n)%n;
		rk[h]=i;
		del(h);
		update(xl,xr);
	}
	return;
}

int compare_plants(int x, int y) {
	return rk[x]<rk[y]?1:-1;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 0 ms 212 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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 44 ms 3448 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 44 ms 3424 KB Output is correct
11 Correct 41 ms 3448 KB Output is correct
12 Correct 41 ms 3432 KB Output is correct
13 Correct 43 ms 3404 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 44 ms 3448 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 44 ms 3424 KB Output is correct
11 Correct 41 ms 3448 KB Output is correct
12 Correct 41 ms 3432 KB Output is correct
13 Correct 43 ms 3404 KB Output is correct
14 Correct 65 ms 4212 KB Output is correct
15 Correct 353 ms 14392 KB Output is correct
16 Correct 67 ms 4216 KB Output is correct
17 Correct 337 ms 14284 KB Output is correct
18 Correct 253 ms 19020 KB Output is correct
19 Correct 202 ms 14304 KB Output is correct
20 Correct 337 ms 14288 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 43 ms 3176 KB Output is correct
4 Correct 221 ms 17520 KB Output is correct
5 Correct 265 ms 15084 KB Output is correct
6 Correct 348 ms 14456 KB Output is correct
7 Correct 342 ms 14400 KB Output is correct
8 Correct 383 ms 14392 KB Output is correct
9 Correct 238 ms 16628 KB Output is correct
10 Correct 244 ms 15084 KB Output is correct
11 Correct 196 ms 23740 KB Output is correct
12 Correct 180 ms 14504 KB Output is correct
13 Correct 252 ms 20848 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

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