oj.uz

Submission #428920

# Submission time Handle Problem Language Result Execution time Memory
428920 2021-06-15T15:28:48 Z Keshi Comparing Plants (IOI20_plants) C++17
27 / 100
 536 ms 24644 KB 
//In the name of God
#include <bits/stdc++.h>
#include "plants.h"
using namespace std;

typedef int ll;
typedef pair<ll, ll> pll;

const ll maxn = 2e5 + 100;
const ll mod = 1e9 + 7;
const ll inf = 1e9;

#define fast_io ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define Mp make_pair
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define Sz(x) ll((x).size())
#define lc (id << 1)
#define rc (lc | 1)

ll n, k, dd, a[maxn], b[maxn];

inline ll dis(ll i, ll j){
	if(i < j) return j - i;
	return j - i + n;
}

struct node{
	ll mn, lx, rx, lz;
	pll ok;
	node(){
		mn = lx = inf;
		rx = -inf;
		ok = Mp(-1, -1);
		lz = 0;
	}
};

node seg[maxn << 2];

void mrg(ll id){
	seg[id] = node();
	seg[id].mn = min(seg[lc].mn, seg[rc].mn);
	seg[id].ok = max(seg[lc].ok, seg[rc].ok);
	if(seg[id].mn != seg[lc].mn){
		seg[id].lx = seg[rc].lx;
		seg[id].rx = seg[rc].rx;
	}
	else if(seg[id].mn != seg[rc].mn){
		seg[id].lx = seg[lc].lx;
		seg[id].rx = seg[lc].rx;
	}
	else{
		seg[id].lx = seg[lc].lx;
		seg[id].rx = seg[rc].rx;
		if(seg[rc].lx - seg[lc].rx >= dd){
			seg[id].ok = Mp(seg[rc].lx, seg[lc].rx);
		}
	}
}
void shift(ll id){
	seg[lc].mn += seg[id].lz;
	seg[lc].lz += seg[id].lz;
	seg[rc].mn += seg[id].lz;
	seg[rc].lz += seg[id].lz;
	seg[id].lz = 0;
}

void bld(ll id, ll s, ll e){
	if(e - s == 1){
		seg[id].lx = seg[id].rx = s;
		seg[id].mn = a[s];
		return;
	}
	ll mid = (s + e) >> 1;
	bld(lc, s, mid);
	bld(rc, mid, e);
	mrg(id);
	return;
}

void upd(ll id, ll s, ll e, ll l, ll r, ll x){
	if(r <= s || e <= l) return;
	if(l <= s && e <= r){
		seg[id].mn += x;
		seg[id].lz += x;
		return;
	}
	shift(id);
	ll mid = (s + e) >> 1;
	upd(lc, s, mid, l, r, x);
	upd(rc, mid, e, l, r, x);
	mrg(id);
	return;
}


void init(int K, vector<int> R){
	k = K;
	n = Sz(R);
	for(ll i = 0; i < n; i++){
		a[i] = R[i];
	}
	dd = k;
	bld(1, 0, n);
	for(ll i = n; i--;){
		ll x;
		if(~seg[1].ok.F) x = seg[1].ok.F;
		else x = seg[1].lx;
		b[x] = i;
		ll y = x - k + 1;
		if(y < 0) y += n;
		upd(1, 0, n, x, x + 1, inf);
		if(y < x){
			upd(1, 0, n, y, x, -1);
		}
		else{
			upd(1, 0, n, 0, x, -1);
			upd(1, 0, n, y, n, -1);
		}
	}
	return;
}

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19064 KB Output is correct
2 Correct 11 ms 19036 KB Output is correct
3 Correct 12 ms 19000 KB Output is correct
4 Incorrect 11 ms 19020 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 11 ms 19048 KB Output is correct
2 Correct 10 ms 19020 KB Output is correct
3 Correct 11 ms 19020 KB Output is correct
4 Correct 11 ms 19020 KB Output is correct
5 Correct 11 ms 19112 KB Output is correct
6 Correct 14 ms 19148 KB Output is correct
7 Correct 75 ms 21956 KB Output is correct
8 Correct 12 ms 19148 KB Output is correct
9 Correct 14 ms 19148 KB Output is correct
10 Correct 77 ms 21980 KB Output is correct
11 Correct 73 ms 21840 KB Output is correct
12 Correct 72 ms 22112 KB Output is correct
13 Correct 75 ms 21976 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19048 KB Output is correct
2 Correct 10 ms 19020 KB Output is correct
3 Correct 11 ms 19020 KB Output is correct
4 Correct 11 ms 19020 KB Output is correct
5 Correct 11 ms 19112 KB Output is correct
6 Correct 14 ms 19148 KB Output is correct
7 Correct 75 ms 21956 KB Output is correct
8 Correct 12 ms 19148 KB Output is correct
9 Correct 14 ms 19148 KB Output is correct
10 Correct 77 ms 21980 KB Output is correct
11 Correct 73 ms 21840 KB Output is correct
12 Correct 72 ms 22112 KB Output is correct
13 Correct 75 ms 21976 KB Output is correct
14 Correct 111 ms 22140 KB Output is correct
15 Correct 536 ms 24572 KB Output is correct
16 Correct 101 ms 22172 KB Output is correct
17 Correct 523 ms 24632 KB Output is correct
18 Correct 348 ms 24644 KB Output is correct
19 Correct 368 ms 24492 KB Output is correct
20 Correct 498 ms 24572 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19020 KB Output is correct
2 Correct 11 ms 19000 KB Output is correct
3 Incorrect 69 ms 21960 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19020 KB Output is correct
2 Correct 11 ms 18996 KB Output is correct
3 Incorrect 11 ms 19024 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19064 KB Output is correct
2 Correct 11 ms 19036 KB Output is correct
3 Correct 12 ms 19000 KB Output is correct
4 Incorrect 11 ms 19020 KB Output isn't correct
5 Halted 0 ms 0 KB -