oj.uz

Submission #1064777

# Submission time Handle Problem Language Result Execution time Memory
1064777 2024-08-18T17:39:48 Z n1k Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 34384 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(h1[x]>h1[y] and h2[x]>h2[y]) return 1;
	if(h1[x]<h1[y] and 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 1 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 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 7 ms 604 KB Output is correct
7 Correct 82 ms 5704 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 7 ms 604 KB Output is correct
10 Correct 84 ms 5712 KB Output is correct
11 Correct 64 ms 5708 KB Output is correct
12 Correct 65 ms 5712 KB Output is correct
13 Correct 84 ms 5712 KB Output is correct

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 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 7 ms 604 KB Output is correct
7 Correct 82 ms 5704 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 7 ms 604 KB Output is correct
10 Correct 84 ms 5712 KB Output is correct
11 Correct 64 ms 5708 KB Output is correct
12 Correct 65 ms 5712 KB Output is correct
13 Correct 84 ms 5712 KB Output is correct
14 Correct 291 ms 7444 KB Output is correct
15 Execution timed out 4053 ms 28244 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.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 39 ms 5088 KB Output is correct
4 Correct 1076 ms 34384 KB Output is correct
5 Correct 1327 ms 29288 KB Output is correct
6 Correct 1975 ms 27988 KB Output is correct
7 Correct 3021 ms 27984 KB Output is correct
8 Execution timed out 4075 ms 28352 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 1307 ms 26928 KB Output is correct
7 Incorrect 1880 ms 27216 KB Output isn't correct
8 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 1 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 -