oj.uz

Submission #1049993

# Submission time Handle Problem Language Result Execution time Memory
1049993 2024-08-09T06:41:33 Z fuad27 Comparing Plants (IOI20_plants) C++17
25 / 100
 2032 ms 38224 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 = 5000+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 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 29 ms 3168 KB Output is correct
7 Runtime error 79 ms 3932 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 7 ms 676 KB Output is correct
7 Correct 218 ms 3564 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 7 ms 672 KB Output is correct
10 Correct 199 ms 3564 KB Output is correct
11 Correct 109 ms 3312 KB Output is correct
12 Correct 104 ms 3508 KB Output is correct
13 Correct 263 ms 3552 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 7 ms 676 KB Output is correct
7 Correct 218 ms 3564 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 7 ms 672 KB Output is correct
10 Correct 199 ms 3564 KB Output is correct
11 Correct 109 ms 3312 KB Output is correct
12 Correct 104 ms 3508 KB Output is correct
13 Correct 263 ms 3552 KB Output is correct
14 Runtime error 2032 ms 4180 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 121 ms 3348 KB Output is correct
4 Runtime error 158 ms 38224 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 9 ms 1116 KB Output is correct
8 Correct 7 ms 1116 KB Output is correct
9 Correct 10 ms 1116 KB Output is correct
10 Correct 13 ms 1100 KB Output is correct
11 Correct 11 ms 1112 KB Output is correct
12 Correct 10 ms 1116 KB Output is correct
13 Correct 7 ms 1116 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Runtime error 205 ms 29260 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 29 ms 3168 KB Output is correct
7 Runtime error 79 ms 3932 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -