oj.uz

Submission #1050045

# Submission time Handle Problem Language Result Execution time Memory
1050045 2024-08-09T07:00:39 Z fuad27 Comparing Plants (IOI20_plants) C++17
25 / 100
 4000 ms 25824 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++) {
		H.push_back(H[i]);
	}
	for(int i =0 ;i<2*n;i++) {
		int nxtmn = -1;
		for(int j = i+1;j<min(2*n, i+k);j++) {
			if(H[j] < H[i] and (nxtmn == -1 or H[nxtmn] < H[j])) {
				nxtmn = j;
			}
		}
		sml[i] = nxtmn;
		nxtmn = -1;
		for(int j = i+1;j<min(2*n, i+k);j++) {
			if(H[j] > H[i] and (nxtmn == -1 or H[nxtmn] > H[j])) {
				nxtmn = j;
			}
		}
		grt[i] = nxtmn;
//		cout << i << " " <<  H[i] << " " << sml[i] << " " << grt[i] << endl;
	}
	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;
		if(b < a)b+=n;
		while(a!=-1 and a + k -1 < b) {
			a=grt[a];
		}
		if(a!=-1 and H[a]<H[b])return -1;
		a=x;
		while(a!=-1 and a + k -1 < b) {
			a=sml[a];
		}
		if(a!=-1 and H[a]>H[b])return 1;
	}
	{
		int a = y, b = x;
		if(b<a)b+=n;
		while(a!=-1 and a + k -1 < b) {
			a=grt[a];
		}
		if(a!=-1 and H[a]<H[b])return 1;
		a=y;
		while(a!=-1 and a + k -1 < b) {
			a=sml[a];
		}
		if(a!=-1 and H[a]>H[b])return -1;
	}
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 28 ms 9160 KB Output is correct
7 Correct 89 ms 10360 KB Output is correct
8 Runtime error 148 ms 21572 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.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 1 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 6 ms 6492 KB Output is correct
7 Correct 166 ms 9568 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 6 ms 6492 KB Output is correct
10 Correct 148 ms 9584 KB Output is correct
11 Correct 153 ms 9392 KB Output is correct
12 Correct 156 ms 9648 KB Output is correct
13 Correct 193 ms 9524 KB Output is correct

Subtask #3
0 / 13.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 1 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 6 ms 6492 KB Output is correct
7 Correct 166 ms 9568 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 6 ms 6492 KB Output is correct
10 Correct 148 ms 9584 KB Output is correct
11 Correct 153 ms 9392 KB Output is correct
12 Correct 156 ms 9648 KB Output is correct
13 Correct 193 ms 9524 KB Output is correct
14 Correct 1732 ms 10320 KB Output is correct
15 Execution timed out 4053 ms 21416 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 2 ms 6492 KB Output is correct
3 Correct 109 ms 9556 KB Output is correct
4 Runtime error 3631 ms 25824 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 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 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 9 ms 7084 KB Output is correct
8 Correct 9 ms 7004 KB Output is correct
9 Correct 11 ms 7100 KB Output is correct
10 Correct 8 ms 6988 KB Output is correct
11 Correct 11 ms 7004 KB Output is correct
12 Correct 14 ms 7096 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 6392 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 3 ms 6492 KB Output is correct
6 Runtime error 369 ms 21428 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 2 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 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 28 ms 9160 KB Output is correct
7 Correct 89 ms 10360 KB Output is correct
8 Runtime error 148 ms 21572 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -