oj.uz

Submission #132807

# Submission time Handle Problem Language Result Execution time Memory
132807 2019-07-19T15:36:16 Z sebinkim Sparklers (JOI17_sparklers) C++14
0 / 100
 2 ms 376 KB 
#include <bits/stdc++.h>

using namespace std;

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

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

bool check(ll v)
{
	ll i, a, b, s;
	
	L.clear(); R.clear();
	
	for(i=1; i<k; i++){
		a = X[i + 1] - X[i]; b = 2 * t * v - a;
		for(; !L.empty() && b <= 0; L.pop_back()){
			a = max(a, L.back().first);
			b += L.back().second;
		}
		L.emplace_back(a, b);
	}
	
	for(i=n; i>k; i--){
		a = X[i] - X[i - 1]; b = 2 * t * v - a;
		for(; !R.empty() && b <= 0; R.pop_back()){
			a = max(a, R.back().first);
			b += R.back().second;
		}
		R.emplace_back(a, b);
	}
		
	s = 2 * t * v;
	
	for(; ; ){
		if(!L.empty() && s >= L.back().first && L.back().second > 0){
			s += L.back().second; L.pop_back();
		}
		else if(!R.empty() && s >= R.back().first && R.back().second > 0){
			s += R.back().second; R.pop_back();
		}
		else break;
	}
	
	if(L.size() > 1 || R.size() > 1) return 0;
	else if(L.empty() && R.empty()) return 1;
	else if(L.empty()) return s >= R[0].first;
	else if(R.empty()) return s >= L[0].first;
	else return (s >= L[0].first && s + L[0].second >= R[0].first)
			|| (s >= R[0].first && s + R[0].second >= L[0].first);
}

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

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

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -