oj.uz

Submission #1050022

# Submission time Handle Problem Language Result Execution time Memory
1050022 2024-08-09T06:55:30 Z fuad27 Comparing Plants (IOI20_plants) C++17
25 / 100
 4000 ms 25172 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 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 1 ms 6492 KB Output is correct
6 Correct 35 ms 9152 KB Output is correct
7 Correct 95 ms 10076 KB Output is correct
8 Correct 145 ms 20636 KB Output is correct
9 Correct 187 ms 20560 KB Output is correct
10 Correct 624 ms 20572 KB Output is correct
11 Execution timed out 4072 ms 20688 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 1 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 8 ms 6492 KB Output is correct
7 Correct 211 ms 9396 KB Output is correct
8 Correct 2 ms 6488 KB Output is correct
9 Correct 8 ms 6492 KB Output is correct
10 Correct 202 ms 9296 KB Output is correct
11 Correct 109 ms 9296 KB Output is correct
12 Correct 110 ms 9548 KB Output is correct
13 Correct 260 ms 9528 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 1 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 8 ms 6492 KB Output is correct
7 Correct 211 ms 9396 KB Output is correct
8 Correct 2 ms 6488 KB Output is correct
9 Correct 8 ms 6492 KB Output is correct
10 Correct 202 ms 9296 KB Output is correct
11 Correct 109 ms 9296 KB Output is correct
12 Correct 110 ms 9548 KB Output is correct
13 Correct 260 ms 9528 KB Output is correct
14 Correct 1992 ms 10340 KB Output is correct
15 Execution timed out 4091 ms 20648 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 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 121 ms 9416 KB Output is correct
4 Execution timed out 4075 ms 25172 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 6488 KB Output is correct
2 Correct 1 ms 6744 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 2 ms 6492 KB Output is correct
7 Correct 10 ms 7096 KB Output is correct
8 Correct 8 ms 7004 KB Output is correct
9 Correct 11 ms 7004 KB Output is correct
10 Correct 8 ms 7004 KB Output is correct
11 Correct 11 ms 7072 KB Output is correct
12 Correct 10 ms 7256 KB Output is correct
13 Correct 8 ms 7004 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 2 ms 6492 KB Output is correct
4 Correct 1 ms 6332 KB Output is correct
5 Correct 3 ms 6492 KB Output is correct
6 Correct 523 ms 20900 KB Output is correct
7 Correct 1937 ms 20828 KB Output is correct
8 Execution timed out 4043 ms 20644 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 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 1 ms 6492 KB Output is correct
6 Correct 35 ms 9152 KB Output is correct
7 Correct 95 ms 10076 KB Output is correct
8 Correct 145 ms 20636 KB Output is correct
9 Correct 187 ms 20560 KB Output is correct
10 Correct 624 ms 20572 KB Output is correct
11 Execution timed out 4072 ms 20688 KB Time limit exceeded
12 Halted 0 ms 0 KB -