Submission #133371

#TimeUsernameProblemLanguageResultExecution timeMemory
133371sebinkimSparklers (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], D[101010]; ll n, k, t; bool check(ll v) { ll i, j, l, r, 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; ; ){ 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 --; if(j <= n && D[j] >= D[r]) r = j ++; if(l != i && r != j) break; } l1 = l; r1 = r; // cout << l1 << " " << r1 << "\n"; for(l=1, r=n, i=2, j=n-1; ; ){ 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 ++; if(j >= k && D[j] >= D[r]) r = j --; if(l != i && r != j) 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;
             ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...