oj.uz

Submission #1065660

# Submission time Handle Problem Language Result Execution time Memory
1065660 2024-08-19T10:35:26 Z n1k Comparing Plants (IOI20_plants) C++17
5 / 100
 3997 ms 96832 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 31 ms 4072 KB Output is correct
7 Correct 383 ms 13840 KB Output is correct
8 Correct 3572 ms 94760 KB Output is correct
9 Correct 3826 ms 94760 KB Output is correct
10 Correct 3551 ms 94844 KB Output is correct
11 Correct 3997 ms 94728 KB Output is correct
12 Correct 3693 ms 94756 KB Output is correct
13 Correct 3660 ms 94720 KB Output is correct
14 Correct 3674 ms 94880 KB Output is correct

Subtask #2
0 / 14.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 84 ms 5628 KB Output is correct
4 Correct 3986 ms 94660 KB Output is correct
5 Runtime error 1165 ms 96832 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 5 ms 348 KB Output is correct
7 Correct 15 ms 1420 KB Output is correct
8 Runtime error 7 ms 1884 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 440 KB Output is correct
5 Runtime error 6 ms 860 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 31 ms 4072 KB Output is correct
7 Correct 383 ms 13840 KB Output is correct
8 Correct 3572 ms 94760 KB Output is correct
9 Correct 3826 ms 94760 KB Output is correct
10 Correct 3551 ms 94844 KB Output is correct
11 Correct 3997 ms 94728 KB Output is correct
12 Correct 3693 ms 94756 KB Output is correct
13 Correct 3660 ms 94720 KB Output is correct
14 Correct 3674 ms 94880 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Runtime error 2 ms 604 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -