Submission #363768

#	Time	Username	Problem	Language	Result	Execution time	Memory
363768		dennisstar	Comparing Plants (IOI20_plants)	C++17	0 / 100	49 ms	6892 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 init(int i, int s, int e, vector<int> &r) {
	if (s==e) {
		st[i]=r[s-1];
		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 spr(int i, bool b) {
	if (st[i]<0) return ;
	st[i]+=lz[i];
	if (!b) for (auto &j:{i*2, i*2+1}) lz[j]+=lz[i];
	lz[i]=0;
}
void getmax(int i, int s, int e, vector<int> &r) {
	spr(i, s==e);
	if (st[i]!=st[1]||(r.size()&&e<=r.back()+K-1)) return ;
	if (s==e) { r.emplace_back(s); return ; }
	int m=(s+e)/2;
	getmax(i*2, s, m, r);
	getmax(i*2+1, m+1, e, r);
}
void upd(int i, int s, int e, int l, int r) {
	spr(i, s==e);
	if (e<l||r<s||r<l) return ;
	if (l<=s&&e<=r) {
		lz[i]=1;
		spr(i, s==e);
		return ;
	}
	int m=(s+e)/2;
	upd(i*2, s, m, l, r);
	upd(i*2+1, m+1, e, l, r);
	st[i]=max(st[i*2], st[i*2+1]);
}
void erase(int i, int s, int e, vector<int> &r) {
	spr(i, s==e);
	if (r.empty()) return ;
	if (s==e) { st[i]=-1; return ; }
	int m=(s+e)/2;
	vector<int> lv, rv;
	for (auto &j:r) (j<=m?lv:rv).emplace_back(j);
	erase(i*2, s, m, lv);
	erase(i*2+1, m+1, e, rv);
	st[i]=max(st[i*2], st[i*2+1]);
}

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

void init(int K, vector<int> r) {
	::N=r.size();
	::K=K;
	for (auto &i:r) i=K-1-i;
	init(1, 1, N, r);
	lv.resize(N+1);
	int t=0;
	while (st[1]>=0) {
		t++;
		vector<int> k;
		getmax(1, 1, N, k);
		if (k.size()>1&&k.back()+K-1>N&&k[0]<(k.back()+K-2)%N+1) {
			vector<int> kk;
			for (int i=1; i<k.size(); i++) kk.emplace_back(k[i]);
			swap(kk, k);
		}
		for (auto &i:k)
			lv[i]=t,
			upd(1, 1, N, max(1, i-K+1), i-1),
			upd(1, 1, N, min(i-K+1+N, N+1), N);
		erase(1, 1, N, k);
	}

	set<pair<int, int>> lr;
	L.resize(N+1);
	for (int i=N-K+2; i<=N; i++) lr.emplace(lv[i], i);
	for (int i=1; i<=N; i++) {
		auto k=lr.upper_bound({lv[i], 0});
		if (k!=lr.end()) L[i].emplace_back((N+i-(k->second))%N, k->second);
		int e=(i-K+N)%N+1;
		lr.erase({lv[e], e});
		lr.emplace(lv[i], i);
	}
	lr.clear();
	R.resize(N+1);
	for (int i=1; i<=K-1; i++) lr.emplace(lv[i], i);
	for (int i=N; i>=1; i--) {
		auto k=lr.upper_bound({lv[i], 0});
		if (k!=lr.end()) R[i].emplace_back(((k->second)-i+N)%N, k->second);
		int e=(i+K-2)%N+1;
		lr.erase({lv[e], e});
		lr.emplace(lv[i], i);
	}
	for (int j=1; j<20; j++) for (int i=1; i<=N; i++) {
		if (L[i].size()>=j&&L[L[i][j-1].second].size()>=j) {
			int e=L[i][j-1].second;
			L[i].emplace_back(L[i][j-1].first+L[e][j-1].first, L[e][j-1].second);
		}
		if (R[i].size()>=j&&R[R[i][j-1].second].size()>=j) {
			int e=R[i][j-1].second;
			R[i].emplace_back(R[i][j-1].first+R[e][j-1].first, R[e][j-1].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[l][i].first, r=R[r][i].second;
	}
	for (int i=-1; i<=1; i++) if (x-ld-K+1<=y+N*i<=x+rd+K-1) return true;
	return false;
}

int compare_plants(int x, int y) {
	x++; 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:75:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |    for (int i=1; i<k.size(); i++) kk.emplace_back(k[i]);
      |                  ~^~~~~~~~~
plants.cpp:106: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]
  106 |   if (L[i].size()>=j&&L[L[i][j-1].second].size()>=j) {
      |       ~~~~~~~~~~~^~~
plants.cpp:106:49: 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]
  106 |   if (L[i].size()>=j&&L[L[i][j-1].second].size()>=j) {
      |                       ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
plants.cpp:110: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]
  110 |   if (R[i].size()>=j&&R[R[i][j-1].second].size()>=j) {
      |       ~~~~~~~~~~~^~~
plants.cpp:110:49: 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]
  110 |   if (R[i].size()>=j&&R[R[i][j-1].second].size()>=j) {
      |                       ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
plants.cpp: In function 'bool cmp(int, int)':
plants.cpp:122: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]
  122 |   if (L[l].size()>i&&lv[L[l][i].second]<lv[y]) ld+=L[l][i].first, l=L[l][i].second;
      |       ~~~~~~~~~~~^~
plants.cpp:123: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]
  123 |   if (R[r].size()>i&&lv[R[r][i].second]<lv[y]) rd+=R[l][i].first, r=R[r][i].second;
      |       ~~~~~~~~~~~^~
plants.cpp:125:40: warning: comparisons like 'X<=Y<=Z' do not have their mathematical meaning [-Wparentheses]
  125 |  for (int i=-1; i<=1; i++) if (x-ld-K+1<=y+N*i<=x+rd+K-1) return true;
      |                                ~~~~~~~~^~~~~~~

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