Submission #132807

#TimeUsernameProblemLanguageResultExecution timeMemory
132807sebinkimSparklers (JOI17_sparklers)C++14
0 / 100
2 ms376 KiB
#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 (stderr)

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;
             ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...