Submission #133378

#	Time	Username	Problem	Language	Result	Execution time	Memory
133378		sebinkim	Sparklers (JOI17_sparklers)	C++14	100 / 100	32 ms	2940 KiB

sparklers

#include <bits/stdc++.h>

using namespace std;

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

vector <pll> L, R;
ll X[101010], D[101010];
ll n, k, t;

bool check(ll v)
{
	ll i, j, l, r, f, l1, l2, r1, r2;
	
	for(i=1; i<=n; i++){
		D[i] = 2 * v * t * i - X[i];
	}
	
	if(D[1] > D[n]) return 0;
	
	for(l=k, r=k, i=k-1, j=k+1, f=0; ; f=0){
		for(; i >= 1 && D[i] > D[l] && D[i] <= D[r]; i--);
		for(; j <= n && D[j] < D[r] && D[j] >= D[l]; j++);
		
		if(i >= 1 && D[i] <= D[l]) l = i --, f = 1;
		if(j <= n && D[j] >= D[r]) r = j ++, f = 1;
		if(!f) break;
	}
	
	l1 = l; r1 = r;
//	cout << l1 << " " << r1 << "\n";
	
	for(l=1, r=n, i=2, j=n-1, f=0; ; f=0){
		for(; i <= k && D[i] > D[l] && D[i] <= D[r]; i++);
		for(; j >= k && D[j] < D[r] && D[j] >= D[l]; j--);
		
		if(i <= k && D[i] <= D[l]) l = i ++, f = 1;
		if(j >= k && D[j] >= D[r]) r = j --, f = 1;
		if(!f) break;
	}
	
	l2 = l; r2 = r;
//	cout << l2 << " " << r2 << "\n";
	
	return (l1 <= l2) && (r2 <= r1);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	ll i, s, e;
	
	cin >> n >> k >> t;
	
	for(i=1; i<=n; i++){
		cin >> X[i];
	}
		
	for(s=0, e=1e12/t; s<=e; ){
		if(check(s + e >> 1)) e = (s + e >> 1) - 1;
		else s = (s + e >> 1) + 1;
	}
	
	cout << e + 1 << "\n";
	
	return 0;
}

Compilation message (stderr)

sparklers.cpp: In function 'int main()':
sparklers.cpp:63:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   if(check(s + e >> 1)) e = (s + e >> 1) - 1;
            ~~^~~
sparklers.cpp:63:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   if(check(s + e >> 1)) e = (s + e >> 1) - 1;
                              ~~^~~
sparklers.cpp:64:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   else s = (s + e >> 1) + 1;
             ~~^~~

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