oj.uz

Submission #826914

# Submission time Handle Problem Language Result Execution time Memory
826914 2023-08-16T06:32:32 Z tomruk Comparing Plants (IOI20_plants) C++17
0 / 100
 46 ms 5208 KB 
#include "plants.h"
#include <bits/stdc++.h>
#define N 200005
using namespace std;
struct SegTree{
	vector<pair<int,int>> t;
	vector<int> lazy;
	int n;
	SegTree(int sz,vector<int> a){
		n = sz;
		t.assign(4*n,{0,0});
		lazy.assign(4*n,0);
		build(1,0,n-1,a);
	}
	void build(int v,int tl,int tr,vector<int> &a){
		if(tl == tr){
			t[v] = {a[tl],tl};
			return;
		}
		int tm = (tl + tr)/2;
		build(v*2,tl,tm,a);
		build(v*2 + 1,tm+1,tr,a);
		t[v] = t[v*2];
		if(t[v*2 + 1].first < t[v].first)
			t[v] = t[v*2+1];
	}
	void push(int v){
		t[v*2].first += lazy[v];
		lazy[v*2] += lazy[v];
		t[v*2 + 1].first += lazy[v];
		lazy[v*2 + 1] += lazy[v];
	}
	void upd(int v,int tl,int tr,int l,int r,int val){
		if(tr < l || r < tl)
			return;
		if(l <= tl && tr <= r){
			t[v].first += val;
			lazy[v] += val;
			return;
		}
		push(v);
		int tm = (tl + tr)/2;
		upd(v*2,tl,tm,l,r,val);
		upd(v * 2 + 1,tm+1,tr,l,r,val);
		t[v] = t[v*2];
		if(t[v*2 + 1].first < t[v].first)
			t[v] = t[v*2+1];
	}
	pair<int,int> get(int v,int tl,int tr,int l,int r){
		if(tr < l || r < tl)
			return {1e9,0};
		if(l <= tl && tr <= r){
			return t[v];
		}
		push(v);
		int tm = (tl + tr)/2;
		auto a = get(v*2,tl,tm,l,r);
		auto b = get(v*2+1,tm+1,tr,l,r);
		if(b.first < a.first)
			return b;
		return a;
	}
	void upd(int l,int r,int val){
		upd(1,0,n-1,l,r,val);
	}
	pair<int,int> get(int l,int r){
		return get(1,0,n-1,l,r);
	}
};
int k;
int a[N];
void init(int k, vector<int> r) {
	int n  = r.size();
	SegTree t(n,r);
	for(int i = n-1;i>=0;i--){
		auto p1 = t.get(0,n-1);
		auto p2 = t.get(p1.second + k,n-1);
		if(p2.first == 0)
			p1 = p2;
		a[p1.second] = i;
		t.upd(max(0,p1.second-k + 1),p1.second - 1,-1);
		if(p1.second - k + 1 < 0){
			t.upd(p1.second-k + 1 + n,n-1,-1);
		}
		t.upd(p1.second,p1.second,1e9);
		// cout << i << ' ' << p1.second << endl;
	}
}

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

Subtask #1
0 / 5.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 312 KB Output is correct
3 Incorrect 46 ms 5208 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 312 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 312 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 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 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -