oj.uz

Submission #1064795

# Submission time Handle Problem Language Result Execution time Memory
1064795 2024-08-18T17:47:32 Z n1k Comparing Plants (IOI20_plants) C++17
44 / 100
 2595 ms 31284 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> h1, h2;
vector<vector<int>> jl, jr;
int K;

void init(int k, std::vector<int> r) {
	K = k;
	int n = r.size(), t=n;
	node seg{0, n-1};
	h1.assign(n, 0);
	h2.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);
	};
	auto findfirst = [&](int lb, int rb){
		while(lb<rb){
			int mb = (lb+rb)/2;
			if(seg.qry(lb, mb).x==0){
				rb=mb;
			}else{
				lb = mb + 1;
			}
		}
		return seg.qry(lb, lb).x==0 ? lb : int(-1e9);
	};
	function<void(int, vector<int>& )> get = [&](int id, vector<int> &h){
		// 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, h);
			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--;
	};
	/*
	seg.bld(r);
	while(find(0, n-1)>=0){
		get(find(0, n-1), h1);
	}
	*/
	t=n;
	seg.bld(r);
	while(findfirst(0, n-1)>=0){
		get(findfirst(0, n-1), h2);
	}
	//for(auto x:h1) cerr<< x << " "; cerr<<endl;
	//for(auto x:h2) cerr<< x << " "; cerr<<endl;
}

int compare_plants(int x, int y) {
	if( h2[x]>h2[y]) return 1;
	if( h2[x]<h2[y]) return -1;
	return 0;
}

Subtask #1
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 1 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 0 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 4 ms 604 KB Output is correct
7 Correct 57 ms 3580 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 4 ms 604 KB Output is correct
10 Correct 56 ms 3588 KB Output is correct
11 Correct 45 ms 3576 KB Output is correct
12 Correct 45 ms 3924 KB Output is correct
13 Correct 57 ms 3664 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 0 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 4 ms 604 KB Output is correct
7 Correct 57 ms 3580 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 4 ms 604 KB Output is correct
10 Correct 56 ms 3588 KB Output is correct
11 Correct 45 ms 3576 KB Output is correct
12 Correct 45 ms 3924 KB Output is correct
13 Correct 57 ms 3664 KB Output is correct
14 Correct 157 ms 5460 KB Output is correct
15 Correct 2172 ms 24704 KB Output is correct
16 Correct 157 ms 7460 KB Output is correct
17 Correct 2151 ms 28416 KB Output is correct
18 Correct 1229 ms 27996 KB Output is correct
19 Correct 1233 ms 28240 KB Output is correct
20 Correct 2595 ms 28496 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 42 ms 3568 KB Output is correct
4 Correct 515 ms 31284 KB Output is correct
5 Correct 791 ms 26196 KB Output is correct
6 Correct 997 ms 24912 KB Output is correct
7 Correct 1701 ms 24720 KB Output is correct
8 Correct 2255 ms 24700 KB Output is correct
9 Correct 622 ms 29012 KB Output is correct
10 Correct 632 ms 27728 KB Output is correct
11 Correct 485 ms 27616 KB Output is correct
12 Correct 699 ms 27892 KB Output is correct
13 Correct 1158 ms 27732 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 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 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -