oj.uz

Submission #1049994

# Submission time Handle Problem Language Result Execution time Memory
1049994 2024-08-09T06:42:04 Z fuad27 Comparing Plants (IOI20_plants) C++17
25 / 100
 4000 ms 25044 KB 
#include "plants.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;

struct lazy_segtree {
	vector<pair<int,int>> T;
	vector<int> lz;
	int n;
	void build(vector<int> &a, int tl, int tr, int v) {
		if(tl == tr) {
			T[v] = {a[tl], tl};
			return;
		}
		int tm = (tl+tr)/2;
		build(a, tl, tm, 2*v);
		build(a, tm+1, tr, 2*v+1);
		T[v] = min(T[2*v], T[2*v+1]);

	}
	lazy_segtree(vector<int> &a) {
		n=a.size();	
		T.resize(4*n);
		lz.resize(4*n);
		build(a, 0, n-1, 1);
	}
	void push(int v){
		lz[2*v] += lz[v];
		lz[2*v+1] += lz[v];
		T[2*v].first += lz[v];
		T[2*v+1].first += lz[v];
		lz[v] = 0;
	}
	void update(int l, int r, int add, int tl, int tr, int v) {
		if(r < tl or tr < l)return;
		if(l <= tl and tr<=r) {
			lz[v]+=add;
			T[v].first+=add;
			return;
		}
		push(v);
		int tm=(tl+tr)/2;
		update(l, r, add, tl, tm, 2*v);
		update(l, r, add, tm+1, tr, 2*v+1);
		T[v] = min(T[2*v], T[2*v+1]);
	}
	pair<int,int> query(int l, int r, int tl, int tr, int v) {
		if(r < tl or tr < l)return {1e9, 1e9};
		if(l <= tl and tr<=r)return T[v];
		push(v);
		int tm=(tl+tr)/2;
		return min(query(l, r, tl, tm, 2*v), query(l, r, tm+1, tr, 2*v+1));
	}
	void update(int l, int r, int add) {
		update(l, r, add, 0, n-1, 1);
	}
	pair<int,int> query(int l, int r) {
		return query(l, r, 0, n-1, 1);
	}
};
const int N = 2e5+10;
vector<int> H;
vector<int> g[N];
int sml[N], grt[N];
int k;
int n;
void init(int K, std::vector<int> r) {
	k=K;
	n = r.size();
	lazy_segtree ls(r);
	int cnt = n;
	H.resize(n, -1);
	auto dfs = [&](int at, auto &&dfs) -> void {
		if(at >= k-1) {
			pair<int,int> val = ls.query(at-k+1, at-1);
			while(val.first == 0) {
				dfs(val.second, dfs);
				val = ls.query(at-k+1, at-1);
			}
			H[at] = cnt--;
			ls.update(at-k+1, at-1, -1);
			ls.update(at, at, 1e9);
		}
		else {
			pair<int,int> val = min(ls.query(0, at-1), ls.query(n-k+at+1, n-1));
			while(val.first == 0) {
				dfs(val.second, dfs);
				val = min(ls.query(0, at-1), ls.query(n-k+at+1, n-1));
			}
			H[at] = cnt--;
			ls.update(0, at-1, -1), ls.update(n-k+at+1, n-1, -1);
			ls.update(at, at, 1e9);
		}
	};
	while(ls.query(0, n-1).first == 0) {
		dfs(ls.query(0, n-1).second, dfs);
	}
	for(int i =0 ;i<n;i++) {
		int nxtmn = -1;
		cnt=0;
		for(int j = (i+1)%n;cnt+1<k;j=(j+1)%n, cnt++) {
			if(H[j] < H[i] and (nxtmn == -1 or H[nxtmn] < H[j])) {
				nxtmn = j;
			}
		}
		sml[i] = nxtmn;
		nxtmn = -1;
		cnt=0;
		for(int j = (i+1)%n;cnt+1<k;j=(j+1)%n, cnt++) {
			if(H[j] > H[i] and (nxtmn == -1 or H[nxtmn] > H[j])) {
				nxtmn = j;
			}
		}
		grt[i] = nxtmn;
	}

	return;
}
int dist(int a, int b) {
	return min({abs(a-b), abs(a+n-b), abs(b+n-a)});
}
int compare_plants(int x, int y) {
	int a = x, b = y;
	while(dist(a, b) >= k) {
		a = grt[a];
		if(a==-1)break;
	}
	if(a!=-1 and H[a] < H[b])return -1;
	a=x, b=y;
	while(dist(a,b) >= k) {
		a = sml[a];
		if(a==-1)break;
	}
	if(a!=-1 and H[a] > H[b])return 1;
	a=x,b=y;
	while(dist(a,b) >= k) {
		b = grt[b];
		if(b==-1)break;
	}
	if(b!=-1 and H[b] < H[a])return 1;
	a=x,b=y;
	while(dist(a,b) >= k) {
		b = sml[b];
		if(b==-1)break;
	}
	if(b!=-1 and H[b] > H[a])return -1;
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 30 ms 9156 KB Output is correct
7 Correct 95 ms 10004 KB Output is correct
8 Correct 148 ms 23564 KB Output is correct
9 Correct 210 ms 23636 KB Output is correct
10 Correct 636 ms 23640 KB Output is correct
11 Execution timed out 4062 ms 23636 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6336 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 8 ms 6652 KB Output is correct
7 Correct 210 ms 9292 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 8 ms 6648 KB Output is correct
10 Correct 197 ms 9532 KB Output is correct
11 Correct 107 ms 9292 KB Output is correct
12 Correct 106 ms 9392 KB Output is correct
13 Correct 261 ms 9524 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6336 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 8 ms 6652 KB Output is correct
7 Correct 210 ms 9292 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 8 ms 6648 KB Output is correct
10 Correct 197 ms 9532 KB Output is correct
11 Correct 107 ms 9292 KB Output is correct
12 Correct 106 ms 9392 KB Output is correct
13 Correct 261 ms 9524 KB Output is correct
14 Correct 2037 ms 10072 KB Output is correct
15 Execution timed out 4093 ms 24348 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 120 ms 9312 KB Output is correct
4 Execution timed out 4083 ms 25044 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 4 ms 6608 KB Output is correct
7 Correct 12 ms 7096 KB Output is correct
8 Correct 8 ms 7004 KB Output is correct
9 Correct 19 ms 7164 KB Output is correct
10 Correct 8 ms 7004 KB Output is correct
11 Correct 11 ms 7084 KB Output is correct
12 Correct 13 ms 7000 KB Output is correct
13 Correct 8 ms 7000 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 3 ms 6492 KB Output is correct
6 Correct 528 ms 20652 KB Output is correct
7 Correct 1965 ms 23364 KB Output is correct
8 Execution timed out 4097 ms 23512 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 30 ms 9156 KB Output is correct
7 Correct 95 ms 10004 KB Output is correct
8 Correct 148 ms 23564 KB Output is correct
9 Correct 210 ms 23636 KB Output is correct
10 Correct 636 ms 23640 KB Output is correct
11 Execution timed out 4062 ms 23636 KB Time limit exceeded
12 Halted 0 ms 0 KB -