oj.uz

Submission #1039876

# Submission time Handle Problem Language Result Execution time Memory
1039876 2024-07-31T11:19:52 Z amirhoseinfar1385 Comparing Plants (IOI20_plants) C++17
0 / 100
 33 ms 36056 KB 
#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=200000+10,lg=19,kaf=(1<<lg);
long long all[maxn],tr[maxn],fake[maxn],allh[maxn];
long long k,n,vis[maxn],visa[maxn];
vector<long long>adj[maxn];
long long inf=1e15;

struct segment{
	long long lazy[(1<<(lg+1))];
	pair<long long,long long>seg[(1<<(lg+1))];
	segment(){
		for(long long i=(1<<(lg+1));i>=1;i--){
			if(i>=kaf){
				seg[i]=make_pair(0,i-kaf);
			}else{
				seg[i]=min(seg[(i<<1)],seg[(i<<1)^1]);
			}
		}
	}
	void calc(long long i){
		if(i>=kaf){
			seg[i].first+=lazy[i];
			lazy[i]=0;
			return ;
		}
		seg[i]=min(make_pair(seg[(i<<1)].first+lazy[(i<<1)],seg[(i<<1)].second),make_pair(seg[(i<<1)^1].first+lazy[(i<<1)^1],seg[(i<<1)^1].second));
	}
	void shift(long long i){
		if(i>=kaf){
			return ;
		}
		lazy[(i<<1)]+=lazy[i];
		lazy[(i<<1)^1]+=lazy[i];
		lazy[i]=0;
	}
	void upd(long long i,long long l,long long r,long long tl,long long tr,long long w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			lazy[i]+=w;
			shift(i);
			calc(i);
			return ;
		}
		shift(i);
		long long m=(l+r)>>1;
		upd((i<<1),l,m,tl,tr,w);
		upd((i<<1)^1,m+1,r,tl,tr,w);
		calc(i);
		return ;
	}
	pair<long long ,long long> pors(long long i,long long l,long long r,long long tl,long long tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return make_pair(inf,inf);
		}
		shift(i);
		calc(i);
		if(l>=tl&&r<=tr){
			return seg[i];
		}
		long long m=(l+r)>>1;
		return min(pors((i<<1),l,m,tl,tr),pors((i<<1)^1,m+1,r,tl,tr));
	}
}seg;

void init(int k_, std::vector<int> r) {
	k=k_;
	n=(long long)r.size();
	for(long long i=0;i<n;i++){
		all[i]=r[i];
	}
	for(long long i=0;i<n;i++){
		fake[i]=all[i];
		seg.upd(1,0,kaf-1,i,i,all[i]);
	}
	long long cnt=n;
	for(long long i=0;i<n;i++){
		vector<long long>tofy;
		tofy.push_back(seg.pors(1,0,kaf-1,0,n-1).second);
		//cout<<seg.pors(1,0,kaf-1,0,n-1).first<<" "<<seg.pors(1,0,kaf-1,0,n-1).second<<endl;
		//for(long long h=1;h<=k-1;h++){
	//		fake[(tofy.back()-h+n)%n]--;
	//		if(vis[(tofy.back()-h+n)%n]==0){
	//			adj[tofy.back()].push_back((tofy.back()-h+n)%n);
	//		}
	//	}
		if(tofy.back()>=k-1){
			seg.upd(1,0,kaf-1,tofy.back()-k+1,tofy.back()-1,-1);
		}else{
			seg.upd(1,0,kaf-1,0,tofy.back()-1,-1);
			long long l=(tofy.back()-(k-1)+n)%n;
			seg.upd(1,0,kaf-1,l,n-1,-1);
		//	cout<<l<<endl;
		}
		seg.upd(1,0,kaf-1,tofy.back(),tofy.back(),inf);
		vis[tofy.back()]=1;
		fake[tofy.back()]=-1;
		allh[tofy.back()]=cnt;
		cnt--;
	}
}

int compare_plants(int x,int y) {
	if(allh[x]>allh[y]){
		return 1;
	}
	if(allh[y]>allh[x]){
		return -1;
	}
	return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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