Submission #883538

#TimeUsernameProblemLanguageResultExecution timeMemory
883538DAleksaSparklers (JOI17_sparklers)C++17
0 / 100
1 ms600 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e5 + 10; int n, k, t; int a[N]; long long x[N]; set<long long> L, R; signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> k >> t; for(int i = 1; i <= n; i++) cin >> a[i]; int l = 1, r = 1e9; int ans = r; while(l <= r) { int mid = (l + r) / 2; if(2LL * mid * t > 1e9) { ans = mid; r = mid - 1; continue; } for(int i = 1; i <= n; i++) x[i] = a[i] - 2LL * mid * i * t; L.clear(); R.clear(); L.insert(x[k]); R.insert(x[k]); int i = k, j = k; while(true) { int change = 0; auto it = R.begin(); if(i > 1) it = R.upper_bound(x[i - 1]); while(i > 1 && it != R.begin()) { change++; i--; L.insert(x[i]); if(i > 1) it = R.upper_bound(x[i - 1]); } if(j < n) it = L.lower_bound(x[j + 1]); while(j < n && it != L.end()) { change++; j++; R.insert(x[j]); if(j < n) it = L.lower_bound(x[j + 1]); } if(change == 0) break; } if(i != 1 || j != n) { l = mid + 1; continue; } L.clear(); R.clear(); L.insert(x[1]); R.insert(x[n]); if(x[1] < x[n]) { l = mid + 1; continue; } i = 1, j = n; while(true) { int change = 0; auto it = R.begin(); if(i < k) it = R.upper_bound(x[i + 1]); while(i < k && it != R.begin()) { change++; i++; L.insert(x[i]); if(i < k) it = R.upper_bound(x[i + 1]); } if(j > k) it = L.lower_bound(x[j - 1]); while(j > k && it != L.end()) { change++; j--; R.insert(x[j]); if(j > k) it = L.lower_bound(x[j - 1]); } if(change == 0) break; } if(i != k || j != k) { l = mid + 1; continue; } ans = mid; r = mid - 1; } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...