oj.uz

Submission #363794

# Submission time Handle Problem Language Result Execution time Memory
363794 2021-02-07T09:33:47 Z dennisstar Comparing Plants (IOI20_plants) C++17
0 / 100
 53 ms 7020 KB 
#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;
}
int get(int i, int s, int e, int l, int r) {
	spr(i, s==e);
	if (e<l||r<s||r<l) return 0;
	if (st[i]!=K-1) return 0;
	if (s==e) return s;
	int m=(s+e)/2, x=get(i*2, s, m, l, r);
	if (x) return x;
	return get(i*2+1, m+1, e, l, 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) {
	auto val = [&](int x) {
		if (get(1, 1, N, x, x)==0
			||get(1, 1, N, max(1, x-K+1), x-1)
			||get(1, 1, N, min(x-K+1+N, N+1), N)) return false;
		return true;
	};
	auto get = [&](int s, int e) {
		if (s<=0) {
			int x=::get(1, 1, N, s+N, N);
			return x?x:(::get(1, 1, N, 1, e));
		}
		if (e>N) {
			int x=::get(1, 1, N, s, N);
			return x?x:(::get(1, 1, N, 1, e-N));
		}
		return ::get(1, 1, N, s, e);
	};

	::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;
	vector<int> lg;
	for (int i=1; i<=N; i++) if (val(i)) lg.emplace_back(i);
	while (st[1]>=0) {
		t++;
		vector<int> k;
		for (auto &i:lg) {
			assert(!lv[i]);
			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, lg);
		for (auto &i:lg) {
			int lm=get(i-K+1, i-1);
			int rm=get(i+1, i+K-1);
			if (lm&&val(lm)) k.emplace_back(lm);
			if (rm&&val(rm)) k.emplace_back(rm);
		}
		sort(k.begin(), k.end());
		k.resize(unique(k.begin(), k.end())-k.begin());
		swap(lg, 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

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:133: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]
  133 |   if (L[i].size()>=j&&L[L[i][j-1].second].size()>=j) {
      |       ~~~~~~~~~~~^~~
plants.cpp:133: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]
  133 |   if (L[i].size()>=j&&L[L[i][j-1].second].size()>=j) {
      |                       ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
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 (R[i].size()>=j&&R[R[i][j-1].second].size()>=j) {
      |       ~~~~~~~~~~~^~~
plants.cpp:137: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]
  137 |   if (R[i].size()>=j&&R[R[i][j-1].second].size()>=j) {
      |                       ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
plants.cpp: In function 'bool cmp(int, int)':
plants.cpp:149: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]
  149 |   if (L[l].size()>i&&lv[L[l][i].second]<lv[y]) ld+=L[l][i].first, l=L[l][i].second;
      |       ~~~~~~~~~~~^~
plants.cpp:150: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]
  150 |   if (R[r].size()>i&&lv[R[r][i].second]<lv[y]) rd+=R[l][i].first, r=R[r][i].second;
      |       ~~~~~~~~~~~^~
plants.cpp:152:40: warning: comparisons like 'X<=Y<=Z' do not have their mathematical meaning [-Wparentheses]
  152 |  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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Runtime error 1 ms 492 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Runtime error 1 ms 492 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Runtime error 53 ms 7020 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Incorrect 0 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Runtime error 1 ms 492 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -