Submission #1065660

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065660		n1k	Comparing Plants (IOI20_plants)	C++17	5 / 100	3997 ms	96832 KiB

plants

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

using namespace std;

using ll = long long;

struct E {
	ll x = 1e15, lz=0;
	E(){};
	E(ll xx){x=xx;};
	friend E operator+(E a, E b){
		return min(a.x, b.x);
	}
	void aply(ll add){
		x+=add;
		lz+=add;
	}
};

struct node{
	int lb, rb;
	E x;
	node *l=nullptr, *r=nullptr;
	bool ext(){
		if(lb<rb and not l){
			int mb = (lb + rb) / 2;
			l = new node{lb, mb}, r = new node{mb+1, rb};
		}
		// push
		if(l){
			l->x.aply(x.lz);
			r->x.aply(x.lz);
			x.lz=0;
		}
		return l;
	}
	E qry(int lo, int hi){
		if(hi<lb or rb<lo) return E();
		if(lo<=lb and rb<=hi) return x;
		if(ext()) {
			E y = l->qry(lo, hi) + r->qry(lo, hi);
			return y;
		}
		return E();
	}
	void upd(int lo, int hi, ll add){
		if(hi<lb or rb<lo) return;
		if(lo<=lb and rb<=hi) {
			x.aply(add);
			return;
		}
		if(ext()) {
			l->upd(lo, hi, add), r->upd(lo, hi, add);
			x = l->x + r->x;
		}
	}
	int find(){
		if(x.x!=0) return -1;
		if(lb==rb) return lb;
		ext();
		if(l->x.x==0) return l->find();
		else return r->find();
	}
	void bld(vector<int> &v){
		if(lb==rb) x.x = v[lb];
		if(ext()) {
			l->bld(v), r->bld(v);
			x = l->x + r->x;
		}
	}
};

int N, K;

vector<int> topoSort(vector<int> r, int min = 1){
	node seg{0, r.size()-1};
	seg.bld(r);
	vector<int> h(r.size());
	deque<int> todo;
	for(int i=0; i<r.size(); i++){
		int id = seg.find();
		while(id==-1){
			seg.upd(todo.front(), r.size()-1, -1);
			todo.pop_front();
			id = seg.find();
		}
		h[id]=i * min;
		seg.upd(id, id, 1e9);
		seg.upd(max(0, id - K + 1), id-1, -1);
		if(id - K + 1 < 0){
			todo.push_back(r.size() - (id - K + 1));
		}
	}
	return h;
}
vector<int> minord, maxord;
void init(int k, std::vector<int> r) {
	N = r.size();
	K = k;
	for(int i=0; i<N; i++) r.push_back(r[i]);
	for(auto x:r) cerr<<x<<" "; cerr<<endl;

	minord = topoSort(r);
	for(auto &x:r) x = K - x - 1;
	for(auto x:r) cerr<<x<<" "; cerr<<endl;

	maxord = topoSort(r);
	for(auto x:minord) cerr<<x<<" "; cerr<<endl;
	for(auto x:maxord) cerr<<x<<" "; cerr<<endl;
}

int compare_plants(int x, int y) {
	if(minord[x]>minord[y] || maxord[y] > maxord[x + N]) return -1;
	if(maxord[x]>maxord[y] || minord[y] > minord[x + N]) return 1;
	return 0;
}

Compilation message (stderr)

plants.cpp: In function 'std::vector<int> topoSort(std::vector<int>, int)':
plants.cpp:77:22: warning: narrowing conversion of '(r.std::vector<int>::size() - 1)' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   77 |  node seg{0, r.size()-1};
      |              ~~~~~~~~^~
plants.cpp:81:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |  for(int i=0; i<r.size(); i++){
      |               ~^~~~~~~~~
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:102:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  102 |  for(auto x:r) cerr<<x<<" "; cerr<<endl;
      |  ^~~
plants.cpp:102:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  102 |  for(auto x:r) cerr<<x<<" "; cerr<<endl;
      |                              ^~~~
plants.cpp:106:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  106 |  for(auto x:r) cerr<<x<<" "; cerr<<endl;
      |  ^~~
plants.cpp:106:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  106 |  for(auto x:r) cerr<<x<<" "; cerr<<endl;
      |                              ^~~~
plants.cpp:109:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  109 |  for(auto x:minord) cerr<<x<<" "; cerr<<endl;
      |  ^~~
plants.cpp:109:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  109 |  for(auto x:minord) cerr<<x<<" "; cerr<<endl;
      |                                   ^~~~
plants.cpp:110:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  110 |  for(auto x:maxord) cerr<<x<<" "; cerr<<endl;
      |  ^~~
plants.cpp:110:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  110 |  for(auto x:maxord) cerr<<x<<" "; cerr<<endl;
      |                                   ^~~~

• Subtask 1: 5 / 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