oj.uz

Submission #1064207

# Submission time Handle Problem Language Result Execution time Memory
1064207 2024-08-18T10:24:40 Z n1k Comparing Plants (IOI20_plants) C++17
44 / 100
 2691 ms 54864 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;
		}
	}
	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;
		}
	}
};

vector<int> h;

void init(int k, std::vector<int> r) {
	int n = r.size(), t=n;
	node seg{0, n-1};
	seg.bld(r);
	h.assign(n, 0);

	auto find = [&](int lb, int rb){
		while(lb<rb){
			int mb = (lb+rb+1)/2;
			if(seg.qry(mb, rb).x==0){
				lb=mb;
			}else{
				rb=mb-1;
			}
		}
		return seg.qry(lb, lb).x==0 ? lb : int(-1e9);
	};
	function<void(int)> get = [&](int id){
		// find 0 in range (id-k+1, id-1)
		// if (id-k+1)<0
		int lb = id - k + 1, rb = id-1;

		while(1){
			int nid = -1e9;
			if(rb>=0){
				nid = max(nid, find(max(lb, 0), rb));
			}if(lb<0 and nid<0){
				nid=max(nid, find((lb+n)%n, n-1));
			}

			if(nid>=0)
				get(nid);
			else
				break;
		}
		if(rb>=0){
			seg.upd(max(lb, 0), rb, -1);
		}if(lb<0){
			seg.upd((lb+n)%n, n-1, -1);
		}
		seg.upd(id, id, 1e9);
		h[id]=t--;
	};
	while(find(0, n-1)>=0){
		//cerr << find(0, n-1) << endl;
		get(find(0, n-1));
		//for(int i=0; i<n; i++) cerr << seg.qry(i, i).x << " "; cout << endl;
	}
	//for(auto x:h) cerr << x-1 << " "; cerr<<endl;
}

int compare_plants(int x, int y) {
	return h[x]>h[y] ? 1 : -1;
}

Subtask #1
0 / 5.0

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

Subtask #2
14.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 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 5 ms 604 KB Output is correct
7 Correct 65 ms 5464 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 4 ms 628 KB Output is correct
10 Correct 58 ms 5456 KB Output is correct
11 Correct 51 ms 5800 KB Output is correct
12 Correct 49 ms 5712 KB Output is correct
13 Correct 60 ms 5484 KB Output is correct

Subtask #3
13.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 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 5 ms 604 KB Output is correct
7 Correct 65 ms 5464 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 4 ms 628 KB Output is correct
10 Correct 58 ms 5456 KB Output is correct
11 Correct 51 ms 5800 KB Output is correct
12 Correct 49 ms 5712 KB Output is correct
13 Correct 60 ms 5484 KB Output is correct
14 Correct 168 ms 7596 KB Output is correct
15 Correct 2526 ms 27476 KB Output is correct
16 Correct 167 ms 7504 KB Output is correct
17 Correct 2502 ms 27476 KB Output is correct
18 Correct 1413 ms 41044 KB Output is correct
19 Correct 1473 ms 27472 KB Output is correct
20 Correct 2691 ms 27628 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 35 ms 5168 KB Output is correct
4 Correct 522 ms 33876 KB Output is correct
5 Correct 588 ms 28752 KB Output is correct
6 Correct 1000 ms 27392 KB Output is correct
7 Correct 1566 ms 27236 KB Output is correct
8 Correct 2358 ms 27484 KB Output is correct
9 Correct 426 ms 30548 KB Output is correct
10 Correct 418 ms 29768 KB Output is correct
11 Correct 176 ms 54864 KB Output is correct
12 Correct 845 ms 26960 KB Output is correct
13 Correct 1284 ms 46676 KB Output is correct

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 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.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 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

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