Submission #364360

#	Time	Username	Problem	Language	Result	Execution time	Memory
364360		dennisstar	Comparing Plants (IOI20_plants)	C++17	100 / 100	3474 ms	223504 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int N, K;

int st[1<<19], lz[1<<19];
void spr(int i, bool b) {
	st[i]+=lz[i];
	if (!b) for (auto &j:{i*2, i*2+1}) lz[j]+=lz[i];
	lz[i]=0;
}
void init(int i, int s, int e, vector<int> &r) {
	if (s==e) { st[i]=r[s]; return ; }
	int m=(s+e)/2;
	init(i*2, s, m, r);
	init(i*2+1, m+1, e, r);
	st[i]=max(st[i*2], st[i*2+1]);
}
void upd(int i, int s, int e, int l, int r, int v) {
	spr(i, s==e);
	if (e<l||r<s||r<l) return ;
	if (l<=s&&e<=r) {
		lz[i]=v;
		spr(i, s==e);
		return ;
	}
	int m=(s+e)/2;
	upd(i*2, s, m, l, r, v);
	upd(i*2+1, m+1, e, l, r, v);
	st[i]=max(st[i*2], st[i*2+1]);
}
int get(int i, int s, int e, int l, int r) {
	spr(i, s==e);
	if (st[i]!=K-1||e<l||r<s||r<l) return -1;
	if (s==e) return s;
	int m=(s+e)/2, v=get(i*2, s, m, l, r);
	return v!=-1?v:get(i*2+1, m+1, e, l, r);
}
int get(int l, int r) {
	if (l<0) {
		int v=get(1, 0, N-1, l+N, N-1);
		return v!=-1?v:get(1, 0, N-1, 0, r);
	}
	if (r>=N) {
		int v=get(1, 0, N-1, l, N-1);
		return v!=-1?v:get(1, 0, N-1, 0, r-N);
	}
	return get(1, 0, N-1, l, r);
}
int val(int i, int s, int e, int t) {
	spr(i, s==e);
	if (s==e) return st[i];
	int m=(s+e)/2;
	if (t<=m) return val(i*2, s, m, t);
	return val(i*2+1, m+1, e, t);
}

vector<int> lv;
vector<vector<pair<ll, int>>> L, R;

void init(int K, vector<int> r) {
	auto val = [&](int x) {
		if (get(x, x)==-1||get(x-K+1, x-1)!=-1) return false;
		return true;
	};
	auto upd = [&](int l, int r, int v) {
		if (l<0) {
			::upd(1, 0, N-1, 0, r, v);
			::upd(1, 0, N-1, l+N, N-1, v);
		}
		else ::upd(1, 0, N-1, l, r, v);
	};

	::N=r.size(), ::K=K;
	for (auto &i:r) i=K-1-i;
	init(1, 0, N-1, r);

	lv.resize(N);
	int t=0;
	vector<int> lg;
	for (int i=0; i<N; i++) if (val(i)) lg.emplace_back(i);
	while (st[1]>=0) {
		++t;
		vector<int> nx;
		for (auto &i:lg) {
			if (lv[i]) continue;
			lv[i]=t;
			upd(i, i, -(1e9));
			upd(i-K+1, i-1, 1);
			int li=get(i-K+1, i-1), ri=get(i+1, i+K-1);
			if (li!=-1&&val(li)) nx.emplace_back(li);
			if (ri!=-1&&val(ri)) nx.emplace_back(ri);
		}
		swap(lg, nx);
	}

	L.resize(N);
	R.resize(N);
	set<pair<ll, int>> lr;
	for (int i=N-K+1; i<N; i++) lr.emplace(lv[i], i);
	for (int i=0; i<N; i++) {
		auto k=lr.lower_bound({lv[i], i});
		if (k!=lr.end()) L[i].emplace_back((i-(k->second)+N)%N, k->second);
		int b=(i-K+1+N)%N;
		lr.erase({lv[b], b});
		lr.emplace(lv[i], i);
	}
	lr.clear();
	for (int i=0; i<K-1; i++) lr.emplace(lv[i], i);
	for (int i=N-1; i>=0; i--) {
		auto k=lr.lower_bound({lv[i], i});
		if (k!=lr.end()) R[i].emplace_back(((k->second)-i+N)%N, k->second);
		int b=(i+K-1)%N;
		lr.erase({lv[b], b});
		lr.emplace(lv[i], i);
	}
	for (int j=0; j<20; j++) for (int i=0; i<N; i++) {
		if (L[i].size()>j&&L[L[i][j].second].size()>j) {
			int b=L[i][j].second;
			L[i].emplace_back(L[b][j].first+L[i][j].first, L[b][j].second);
		}
		if (R[i].size()>j&&R[R[i][j].second].size()>j) {
			int b=R[i][j].second;
			R[i].emplace_back(R[b][j].first+R[i][j].first, R[b][j].second);
		}
	}
}

bool cmp(int x, int y) {
	if (lv[x]>=lv[y]) return false;
	int l=x, r=x;
	ll ld=0, rd=0;
	for (int i=19; i>=0; i--) {
		if (L[l].size()>i&&lv[L[l][i].second]<lv[y]) ld+=L[l][i].first, l=L[l][i].second;
		if (R[r].size()>i&&lv[R[r][i].second]<lv[y]) rd+=R[r][i].first, r=R[r][i].second;
	}
	for (int i=-1; i<=1; i++) if (x-ld-K+1<=y+N*i&&y+N*i<=x+rd+K-1) return true;
	return false;
}

int compare_plants(int x, int y) {
	if (cmp(x, y)) return 1;
	if (cmp(y, x)) return -1;
	return 0;
}

Compilation message (stderr)

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:121:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  121 |   if (L[i].size()>j&&L[L[i][j].second].size()>j) {
      |       ~~~~~~~~~~~^~
plants.cpp:121:46: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  121 |   if (L[i].size()>j&&L[L[i][j].second].size()>j) {
      |                      ~~~~~~~~~~~~~~~~~~~~~~~~^~
plants.cpp:125:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  125 |   if (R[i].size()>j&&R[R[i][j].second].size()>j) {
      |       ~~~~~~~~~~~^~
plants.cpp:125:46: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  125 |   if (R[i].size()>j&&R[R[i][j].second].size()>j) {
      |                      ~~~~~~~~~~~~~~~~~~~~~~~~^~
plants.cpp: In function 'bool cmp(int, int)':
plants.cpp:137:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  137 |   if (L[l].size()>i&&lv[L[l][i].second]<lv[y]) ld+=L[l][i].first, l=L[l][i].second;
      |       ~~~~~~~~~~~^~
plants.cpp:138:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  138 |   if (R[r].size()>i&&lv[R[r][i].second]<lv[y]) rd+=R[r][i].first, r=R[r][i].second;
      |       ~~~~~~~~~~~^~

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