Submission #671810

#	Time	Username	Problem	Language	Result	Execution time	Memory
671810		amunduzbaev	Sparklers (JOI17_sparklers)	C++17	100 / 100	385 ms	7064 KiB

sparklers

#include "bits/stdc++.h"
using namespace std;

#define ar array
typedef long long ll;
#define int ll

const int N = 1e5 + 5;
int x[N];

struct ST{
	int mx[N << 2], mn[N << 2];
	
	void set(int i, int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx){
			mn[x] = mx[x] = v;
			return; 
		}
		int m = (lx + rx) >> 1;
		if(i <= m) set(i, v, lx, m, x << 1);
		else set(i, v, m + 1, rx, x << 1 | 1);
		mn[x] = min(mn[x << 1], mn[x << 1 | 1]);
		mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
	}
	
	int get_first_big(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return -1;
		if(lx >= l && rx <= r){
			if(mx[x] < v) return -1;
			if(lx == rx) return lx;
			int m = (lx + rx) >> 1;
			if(mx[x << 1] >= v) return get_first_big(l, r, v, lx, m, x << 1);
			else return get_first_big(l, r, v, m + 1, rx, x << 1 | 1);
		} int m = (lx + rx) >> 1;
		int res = get_first_big(l, r, v, lx, m, x << 1);
		if(res == -1) res = get_first_big(l, r, v, m + 1, rx, x << 1 | 1);
		return res;
	}
	
	int get_last_low(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return -1;
		if(lx >= l && rx <= r){
			if(mn[x] > v) return -1;
			if(lx == rx) return lx;
			int m = (lx + rx) >> 1;
			if(mn[x << 1 | 1] <= v) return get_last_low(l, r, v, m + 1, rx, x << 1 | 1);
			else return get_last_low(l, r, v, lx, m, x << 1);
		} int m = (lx + rx) >> 1;
		int res = get_last_low(l, r, v, m + 1, rx, x << 1 | 1);
		if(res == -1) return get_last_low(l, r, v, lx, m, x << 1);
		return res;
	}
}tree;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, k, T; cin >> n >> k >> T;
	for(int i=1;i<=n;i++){
		cin >> x[i];
	}
	
	x[n + 1] = x[n];
	tree.set(n + 1, 1e18);
	
	auto check = [&](int s){
		int t = T * s * 2;
		vector<int> p(n + 1);
		for(int i=1;i<=n;i++){
			p[i] = x[i] - t * i;
			tree.set(i, p[i]);
		} 
				
		//~ for(int i=1;i<=n;i++){
			//~ cout<<p[i]<<" ";
		//~ } cout<<"\n";
		
		int pos = tree.get_first_big(k, n + 1, p[k] + 1) - 1;
		//~ cout<<pos<<" ";
		for(int i=k-1;i>0;i--){
			if(p[i] >= p[i + 1]){
				pos = tree.get_first_big(pos, n + 1, p[i] + 1) - 1;
			} else {
				pos = tree.get_last_low(k, pos, p[i]);
				if(pos == -1) return false;
			}
			//~ cout<<pos<<" ";
		}
		//~ cout<<"\n";
		
		return pos == n;
	};
	
	int l = 0, r = x[n] / (T * 2) + 1;
	while(l < r){
		int m = (l + r) >> 1;
		if(check(m)) r = m;
		else l = m + 1;
	}
	
	cout<<l<<"\n";
}

/*

5 3 1
0 0 3 4 7 

*/

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 50 / 50