oj.uz

Submission #1043064

# Submission time Handle Problem Language Result Execution time Memory
1043064 2024-08-03T20:29:09 Z MarwenElarbi Comparing Plants (IOI20_plants) C++17
27 / 100
 4000 ms 19828 KB 
#include <bits/stdc++.h>
#include "plants.h"
using namespace std;
const int nax=4e5+5;
#define fi first
#define se second
int n,k;
pair<int,int> segtree[4*nax];
int lazy[nax*4];
int ans[nax];
int tab[nax];
void build(int pos,int l,int r){
	if(l==r){
		segtree[pos]={tab[l],l};
		return;
	}
	int mid=(r+l)/2;
	build(pos*2+1,l,mid);
	build(pos*2+2,mid+1,r);
	segtree[pos]=min(segtree[pos*2+1],segtree[pos*2+2]);
	return;
}
void propagate(int pos){
	if(lazy[pos]){
		segtree[pos*2+1].fi+=lazy[pos];
		segtree[pos*2+2].fi+=lazy[pos];
		lazy[pos*2+1]+=lazy[pos];
		lazy[pos*2+2]+=lazy[pos];
	}
	lazy[pos]=0;
}
void update(int pos,int l,int r,int left,int right,int value){
	if(l>r||l>right||r<left) return;
	if(l>=left&&r<=right){
		segtree[pos].fi+=value;
		lazy[pos]+=value;
		return;
	}
	int mid=(r+l)/2;
	propagate(pos);
	update(pos*2+1,l,mid,left,right,value);
	update(pos*2+2,mid+1,r,left,right,value);
	segtree[pos]=min(segtree[pos*2+1],segtree[pos*2+2]);
}
pair<int,int> query(int pos,int l,int r,int left,int right){
	if(l>r||l>right||r<left) return {1e9,1e9};
	if(l>=left&&r<=right){
		return segtree[pos];
	}
	int mid=(r+l)/2;
	propagate(pos);
	return min(query(pos*2+1,l,mid,left,right),query(pos*2+2,mid+1,r,left,right));
}
pair<int,int> q(int l,int r){
	if(l>r){
		return min(query(0,0,n-1,0,r),query(0,0,n-1,l,n-1));
	}else return query(0,0,n-1,l,r);
}
int jump(){
	int x=query(0,0,n-1,0,n-1).se;
	while(q((x-k+1+n)%n,(x-1+n)%n).fi==0){
		x=q((x-k+1+n)%n,(x-1+n)%n).se;
	}
	return x;
}
void upd(int l,int r,int value){
	if(l>r){
		update(0,0,n-1,0,r,value);
		update(0,0,n-1,l,n-1,value);
	}else update(0,0,n-1,l,r,value);
}
void init(int K, std::vector<int> r) {
    n=r.size();
    k=K;
    for (int i = 0; i < n; ++i) tab[i]=r[i];
    build(0,0,n-1);
	for (int i = n; i >= 1; --i)
	{
		int x=jump();
		ans[x]=i;
		upd((x-k+1+n)%n,(x-1+n)%n,-1);
		upd(x,x,1e9);
	}
    return;
}
int compare_plants(int x, int y) {
    return ( ans[x]>ans[y] ? 1 : -1);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 0 ms 4444 KB Output is correct
3 Correct 0 ms 4444 KB Output is correct
4 Incorrect 0 ms 4444 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 4444 KB Output is correct
2 Correct 0 ms 4444 KB Output is correct
3 Correct 0 ms 4444 KB Output is correct
4 Correct 0 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 31 ms 9264 KB Output is correct
8 Correct 2 ms 4440 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 31 ms 9208 KB Output is correct
11 Correct 33 ms 9204 KB Output is correct
12 Correct 38 ms 9300 KB Output is correct
13 Correct 32 ms 9300 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 0 ms 4444 KB Output is correct
3 Correct 0 ms 4444 KB Output is correct
4 Correct 0 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 31 ms 9264 KB Output is correct
8 Correct 2 ms 4440 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 31 ms 9208 KB Output is correct
11 Correct 33 ms 9204 KB Output is correct
12 Correct 38 ms 9300 KB Output is correct
13 Correct 32 ms 9300 KB Output is correct
14 Correct 49 ms 10064 KB Output is correct
15 Correct 266 ms 19540 KB Output is correct
16 Correct 49 ms 10068 KB Output is correct
17 Correct 268 ms 19828 KB Output is correct
18 Correct 170 ms 19284 KB Output is correct
19 Correct 172 ms 19700 KB Output is correct
20 Correct 236 ms 19796 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 40 ms 7200 KB Output is correct
4 Execution timed out 4025 ms 18256 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

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

Subtask #7
0 / 25.0

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