oj.uz

Submission #1050059

# Submission time Handle Problem Language Result Execution time Memory
1050059 2024-08-09T07:07:02 Z fuad27 Comparing Plants (IOI20_plants) C++17
25 / 100
 248 ms 49728 KB 
#include "plants.h"
#include <bits/stdc++.h>
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;
//	}
	set<pair<int,int>> s;
	s.insert({-1e9, 2*n});
	s.insert({1e9, 2*n});
	for(int i = 2*n-1;i>=0;i--) {
		if(i+k < 2*n) {
			s.erase({H[i+k], i+k});
		}
		grt[i][0] = (*s.lower_bound(pair{H[i], i})).second;
		sml[i][0] = (*(--s.lower_bound(pair{H[i], i}))).second;
		s.insert({H[i], i});
	}
	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 7512 KB Output is correct
2 Correct 1 ms 7516 KB Output is correct
3 Correct 1 ms 7512 KB Output is correct
4 Correct 1 ms 7516 KB Output is correct
5 Correct 1 ms 7512 KB Output is correct
6 Correct 68 ms 10196 KB Output is correct
7 Correct 74 ms 19468 KB Output is correct
8 Runtime error 147 ms 40876 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 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 1 ms 7564 KB Output is correct
6 Correct 3 ms 7772 KB Output is correct
7 Correct 35 ms 12944 KB Output is correct
8 Correct 2 ms 7512 KB Output is correct
9 Correct 3 ms 7772 KB Output is correct
10 Correct 36 ms 12724 KB Output is correct
11 Correct 39 ms 12720 KB Output is correct
12 Correct 37 ms 12848 KB Output is correct
13 Correct 35 ms 12980 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 7564 KB Output is correct
6 Correct 3 ms 7772 KB Output is correct
7 Correct 35 ms 12944 KB Output is correct
8 Correct 2 ms 7512 KB Output is correct
9 Correct 3 ms 7772 KB Output is correct
10 Correct 36 ms 12724 KB Output is correct
11 Correct 39 ms 12720 KB Output is correct
12 Correct 37 ms 12848 KB Output is correct
13 Correct 35 ms 12980 KB Output is correct
14 Correct 67 ms 19796 KB Output is correct
15 Runtime error 248 ms 40880 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.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 52 ms 12576 KB Output is correct
4 Runtime error 156 ms 49728 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 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 1 ms 7516 KB Output is correct
6 Correct 2 ms 7516 KB Output is correct
7 Correct 13 ms 8100 KB Output is correct
8 Correct 9 ms 8284 KB Output is correct
9 Correct 13 ms 8172 KB Output is correct
10 Correct 9 ms 8024 KB Output is correct
11 Correct 13 ms 8172 KB Output is correct
12 Correct 12 ms 8028 KB Output is correct
13 Correct 9 ms 8284 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 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 7772 KB Output is correct
6 Runtime error 179 ms 40876 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 7512 KB Output is correct
2 Correct 1 ms 7516 KB Output is correct
3 Correct 1 ms 7512 KB Output is correct
4 Correct 1 ms 7516 KB Output is correct
5 Correct 1 ms 7512 KB Output is correct
6 Correct 68 ms 10196 KB Output is correct
7 Correct 74 ms 19468 KB Output is correct
8 Runtime error 147 ms 40876 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -