oj.uz

Submission #1050055

# Submission time Handle Problem Language Result Execution time Memory
1050055 2024-08-09T07:04:18 Z fuad27 Comparing Plants (IOI20_plants) C++17
25 / 100
 4000 ms 112568 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];
const int lg = 20;
int sml[N][lg], grt[N][lg];
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][0] = 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][0] = nxtmn;
	}
	for(int i =0 ;i<2*n;i++) {
		if(grt[i][0] == -1)grt[i][0]=2*n;
		if(sml[i][0] == -1)sml[i][0]=2*n;
	}
	sml[2*n][0] = grt[2*n][0] = 2*n;
	for(int i = 1;i<lg;i++) {
		for(int j = 0;j<=2*n;j++) {
			sml[j][i] = sml[sml[j][i-1]][i-1];
			grt[j][i] = grt[grt[j][i-1]][i-1];
		}
	}
	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;
		if(a+k-1 < b) {
			for(int i = lg-1;i>=0;i--) {
				if(grt[a][i] + k - 1 < b) {
					a=grt[a][i];
				}
			}
			a=grt[a][0];
		}
		if(a!=2*n and H[a]<H[b])return -1;
		a=x;
		if(a+k-1 < b) {
			for(int i = lg-1;i>=0;i--) {
				if(sml[a][i] + k - 1 < b) {
					a=sml[a][i];
				}
			}
			a=sml[a][0];
		}
		if(a!=2*n and H[a]>H[b])return 1;
	}
	{
		int a = y, b = x;
		if(b<a)b+=n;
		if(a+k-1 < b) {
			for(int i = lg-1;i>=0;i--) {
				if(grt[a][i] + k - 1 < b) {
					a=grt[a][i];
				}
			}
			a=grt[a][0];
		}
		if(a!=2*n and H[a]<H[b])return 1;
		a=y;
		if(a+k-1 < b) {
			for(int i = lg-1;i>=0;i--) {
				if(sml[a][i] + k - 1 < b) {
					a=sml[a][i];
				}
			}
			a=sml[a][0];
		}
		if(a!=2*n and H[a]>H[b])return -1;
	}
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7516 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 1 ms 7516 KB Output is correct
4 Correct 1 ms 7516 KB Output is correct
5 Correct 2 ms 7512 KB Output is correct
6 Correct 48 ms 10160 KB Output is correct
7 Correct 83 ms 19536 KB Output is correct
8 Runtime error 162 ms 103748 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 2 ms 7516 KB Output is correct
2 Correct 1 ms 7516 KB Output is correct
3 Correct 1 ms 7516 KB Output is correct
4 Correct 1 ms 7516 KB Output is correct
5 Correct 2 ms 7516 KB Output is correct
6 Correct 7 ms 7772 KB Output is correct
7 Correct 162 ms 12676 KB Output is correct
8 Correct 2 ms 7516 KB Output is correct
9 Correct 6 ms 7772 KB Output is correct
10 Correct 141 ms 12548 KB Output is correct
11 Correct 90 ms 12468 KB Output is correct
12 Correct 91 ms 12724 KB Output is correct
13 Correct 190 ms 12724 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7516 KB Output is correct
2 Correct 1 ms 7516 KB Output is correct
3 Correct 1 ms 7516 KB Output is correct
4 Correct 1 ms 7516 KB Output is correct
5 Correct 2 ms 7516 KB Output is correct
6 Correct 7 ms 7772 KB Output is correct
7 Correct 162 ms 12676 KB Output is correct
8 Correct 2 ms 7516 KB Output is correct
9 Correct 6 ms 7772 KB Output is correct
10 Correct 141 ms 12548 KB Output is correct
11 Correct 90 ms 12468 KB Output is correct
12 Correct 91 ms 12724 KB Output is correct
13 Correct 190 ms 12724 KB Output is correct
14 Correct 1699 ms 19540 KB Output is correct
15 Execution timed out 4066 ms 24900 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 7512 KB Output is correct
2 Correct 1 ms 7516 KB Output is correct
3 Correct 54 ms 12628 KB Output is correct
4 Runtime error 186 ms 112568 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 2 ms 7516 KB Output is correct
2 Correct 1 ms 7512 KB Output is correct
3 Correct 1 ms 7516 KB Output is correct
4 Correct 1 ms 7516 KB Output is correct
5 Correct 1 ms 7512 KB Output is correct
6 Correct 2 ms 7516 KB Output is correct
7 Correct 13 ms 8192 KB Output is correct
8 Correct 9 ms 8028 KB Output is correct
9 Correct 12 ms 8020 KB Output is correct
10 Correct 12 ms 8028 KB Output is correct
11 Correct 13 ms 8028 KB Output is correct
12 Correct 12 ms 8096 KB Output is correct
13 Correct 8 ms 8028 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7516 KB Output is correct
2 Correct 2 ms 7528 KB Output is correct
3 Correct 1 ms 7516 KB Output is correct
4 Correct 1 ms 7504 KB Output is correct
5 Correct 3 ms 7772 KB Output is correct
6 Runtime error 293 ms 103748 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 1 ms 7516 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 1 ms 7516 KB Output is correct
4 Correct 1 ms 7516 KB Output is correct
5 Correct 2 ms 7512 KB Output is correct
6 Correct 48 ms 10160 KB Output is correct
7 Correct 83 ms 19536 KB Output is correct
8 Runtime error 162 ms 103748 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -