Submission #1194258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194258		ildar1	Comparing Plants (IOI20_plants)	C++20	27 / 100	544 ms	14700 KiB

plants

#include <iostream>
#include <vector>
#include <cassert>
#include <stack>

#define MAXN 200001

using namespace std;
using ll = long long;

int ans[MAXN];  //ans[x] = rank of h[x]
int myr[MAXN];

int k_save;

int next_bigger[31][MAXN]; //next_bigger[x] = index between x+1 and x+k-1 so that h[bigger[x]]
int prev_bigger[31][MAXN]; //prev_bigger[x] = index between x-k+1 and x-1 so that h[prev_bigger[x]] is smallest term bigger than it else -1
stack<int> s;


int n;

int h;

bool comparePairs(const pair<int,int> &p1, const pair<int,int> &p2) {
	if (p1.first < p2.first) return true;
	if (p1.first > p2.first) return false;
	if (p1.first==p2.first) {
		return p1.second >= p2.second;
	}
}

struct Seg{

	pair<int,int> tree[2*MAXN];
	int lazy[MAXN];

	int last_seen_left[2*MAXN];

	int last_seen_right[2*MAXN];

	void make() {
		for (int i=0; i<n; i++) {
			tree[i+n].first = myr[i];
			tree[i+n].second = i;
			last_seen_left[i+n] = -1;
			last_seen_right[i+n] = -1;
		}
		for (int i=n-1; i>0; i--) {
			tree[i] = min(tree[i<<1], tree[i<<1|1], comparePairs);
			last_seen_left[i] = -1;
			last_seen_right[i] = -1;
		}
	}

	void apply_last(int p, int val, int dir) {
		if (dir==-1){
			last_seen_left[p] = val;
		} else {
			last_seen_right[p] = val;
		}
	}

	void push_last(int p, int dir) {
		if (dir==-1) {
			for (int i=h; i>0; i--) {
				int j = p>>i;
				if (last_seen_left[j]!=-1) {
					apply_last(j<<1, last_seen_left[j], dir);
					apply_last(j<<1|1, last_seen_left[j], dir);
					last_seen_left[j] = -1;
				}

			}
		} else {
			for (int i=h; i>0; i--) {
				int j = p>>i;
				if (last_seen_right[j]!=-1) {
					apply_last(j<<1, last_seen_right[j], dir);
					apply_last(j<<1|1, last_seen_right[j], dir);
					last_seen_right[j] = -1;
				}
			}
		}
	}

	void incre_last(int l, int r, int val, int dir) {
		if (l>=r) return;
		l+=n;
		r+=n;
		push_last(l, dir);
		push_last(r-1, dir);
		

		if (dir==-1) {
			for (;l<r;l>>=1, r>>=1) {
				if (l&1) last_seen_left[l++] = val;
				if (r&1) last_seen_left[--r] = val;
			}

		} else {
			for (; l<r; l>>=1, r>>=1) {
				if (l&1) last_seen_right[l++] = val;
				if (r&1) last_seen_right[--r] = val;
			}
		}
	}

	int query_last(int ind, int dir) {
		ind+=n;
		push_last(ind, dir);

		if (dir==-1) return last_seen_left[ind];
		else return last_seen_right[ind];
	}

	void apply(int p, int val) {
		tree[p].first += val;
		if (p<n) lazy[p] += val;
	} 

	void build(int p) {
		while (p>1) {
			p>>=1;
			pair<int,int> tmp1 = tree[p<<1];
			tmp1.first += lazy[p];
			pair<int, int> tmp2 = tree[p<<1|1];
			tmp2.first += lazy[p];
			tree[p] = min(tmp1, tmp2, comparePairs);
		}
	}

	void push(int p) {
		for (int i=h; i>0; i--) {
			int j = p>>i;
			if (lazy[j] != 0) {
				apply(j<<1, lazy[j]);
				apply(j<<1|1, lazy[j]);
				lazy[j] = 0;
			}
		}
	}

	void increm(int l, int r, int val) {
		l+=n;
		r+=n;
		int l0 = l;
		int r0 = r;
		for (; l<r; l>>=1, r>>=1) {
			if (l&1) apply(l++, val);
			if (r&1) apply(--r, val);
		}
		build(l0);
		build(r0-1);
	}

	pair<int, int> query(int l, int r) {
		l+=n;
		r+=n;
		push(l);
		push(r-1);
		pair<int,int> res = {2e9, -1};
		for (; l<r; l>>=1, r>>=1) {
			if (l&1) res = min(res, tree[l++]);
			if (r&1) res = min(res, tree[--r]);
		}
		return res;
	}

} seg;

void init(int k, vector<int> r) {
	n = r.size();
	h = 31 - __builtin_clz(n);
	k_save = k;

	for (int i=0; i<n; i++) myr[i] = r[i];

	seg.make();

	int ind=seg.query(0,n).second;
	s.push(ind);

	for (int m=0; m<n; m++) {

		while (true) {
			if (!s.empty()) {
				int tmp = s.top();
				if (tmp>=k-1 && seg.query(tmp-k+1, tmp).first>0) {
					s.pop();
					ind = tmp;
					break;
				} else if (tmp>= k-1) {
					s.push(seg.query(tmp-k+1,tmp).second);
				} else if (tmp<k-1 && seg.query(0, tmp).first>0 && seg.query(n-k+tmp+1,n).first>0) {
					s.pop();
					ind = tmp;
					break;
				} else if (tmp<k-1 && seg.query(0,tmp).first>0) {
					s.push(seg.query(n-k+tmp+1,n).second);
				} else {
					s.push(seg.query(0,tmp).second);
				}
			} else {
				if (seg.query(0, ind).first==0) {
					s.push(seg.query(0, ind).second);
				} else {
					s.push(seg.query(0, n).second);
				}

			}
		}

		ans[ind] = n-m;
		


		if (ind >= k-1) {
			seg.increm(ind-k+1, ind, -1);
		} else {
			seg.increm(0, ind, -1);
			seg.increm(n-k+ind+1, n, -1);
		}
		seg.increm(ind, ind+1, n);


		
		int tmp_left =  seg.query_last(ind, -1);
		prev_bigger[0][ind] = (tmp_left!=-1) ? tmp_left: ind;
	
		int tmp_right = seg.query_last(ind, 1);
		next_bigger[0][ind] = (tmp_right!=-1) ? tmp_right : ind;
		
		if (ind-k+1>=0 && ind+k-1<n) {
			seg.incre_last(ind, ind+k, ind, -1);
			seg.incre_last(ind-k+1, ind, ind, 1);
		} else if (ind-k+1>=0) { 
			seg.incre_last(ind-k+1, ind, ind, 1);
			seg.incre_last(ind, n, ind, -1);
			seg.incre_last(0, k+ind-n, ind, -1);
		} else if (ind-k+1<0 && ind+k-1<n) {
			seg.incre_last(0, ind, ind, 1);
			seg.incre_last(ind-k+n+1, n, ind, 1); 
			seg.incre_last(ind, ind+k, ind, -1);
		} else if (ind-k+1<0) {
			seg.incre_last(0, ind, ind, 1);
			seg.incre_last(ind-k+n+1, n, ind, 1);
			seg.incre_last(ind, n, ind, -1);
			seg.incre_last(0, k+ind-n+1, ind, -1);
		}
	}

	for (int i=1; i<=h; i++) {
		prev_bigger[i][ind] = prev_bigger[i-1][prev_bigger[i-1][ind]];
		next_bigger[i][ind] = next_bigger[i-1][next_bigger[i-1][ind]];
	}
}

int compare_plants(int x, int y) {

	if (x==y) return 0;
	if (x>y) return -compare_plants(y,x);

	if (ans[x]>ans[y]) {

		//we need to find the first time y enters a region x<=y<=x+k-1  i.e. [x, x+k-1]
		

		for (int i=h; i>=0; i--) {
			if (ans[prev_bigger[i][y]]>ans[x]) {
				continue;
			} else if (ans[prev_bigger[i][y]]<ans[x]) {
				y = ans[prev_bigger[i][y]];
			} else {
				return 1;
			}
		}
		if ((y-x<=k_save-1 && y>=x) || (x-y<=k_save-1 && x>=y) || (x<k_save-1 && y>=n-k_save+x+1) || (x+k_save-1>=n && y<=k_save+x-n-1)) {


			return 1;

		} 

		for (int i=h; i>=0; i--) {
			if (ans[next_bigger[i][y]]>ans[x]) {
				continue;
			} else if (ans[next_bigger[i][y]]<ans[x]) {
				y = ans[next_bigger[i][y]];
			} else {
				return 1;
			}
		}
		if ((y-x<=k_save-1 && y>=x) || (x-y<=k_save-1 && x>=y) || (x<k_save-1 && y>=n-k_save+x+1) || (x+k_save-1>=n && y<=k_save+x-n-1)) return 1;
	} else if (ans[x]<ans[y]) {

		//we need to find the first time y enters a region x<=y<=x+k-1  i.e. [x, x+k-1]

		for (int i=h; i>=0; i--) {
			if (ans[prev_bigger[i][x]]>ans[y]) {
				continue;
			} else if (ans[prev_bigger[i][x]]<ans[y]) {
				x = ans[prev_bigger[i][x]];
			} else {
				return -1;
			}
		}
		if (y-x<=k_save-1 || x-y<=k_save-1 || (x<k_save-1 && y>=n-k_save+x+1)) return -1;

		for (int i=h; i>=0; i--) {
			if (ans[next_bigger[i][x]]>ans[y]) {
				continue;
			} else if (ans[next_bigger[i][x]]<ans[y]) {
				x = ans[next_bigger[i][x]];
			} else {
				return -1;
			}
		}
		if (y-x<=k_save-1 || x-y<=k_save-1 || (x<k_save-1 && y>=n-k_save+x+1) || (x+k_save-1>=n && y<=k_save+x-n-1)) return -1;
	}

	return 0;


	/* if (ans[x] > ans[y]) {
		return 1;
	} else return -1; */
}

Compilation message (stderr)

plants.cpp: In function 'bool comparePairs(const std::pair<int, int>&, const std::pair<int, int>&)':
plants.cpp:31:1: warning: control reaches end of non-void function [-Wreturn-type]
   31 | }
      | ^

• Subtask 1: 0 / 5
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25