Submission #922823

#TimeUsernameProblemLanguageResultExecution timeMemory
922823penguin133Snowball (JOI21_ho_t2)C++17
100 / 100
872 ms12548 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pi pair<int, int> #define pii pair<int, pi> #define fi first #define se second #ifdef _WIN32 #define getchar_unlocked _getchar_nolock #endif mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); vector <int> pos, neg; int n, q, X[200005]; void solve(){ cin >> n >> q; for(int i = 1; i <= n; i++)cin >> X[i]; X[n + 1] = 1e18; int cur = 0, mx = 0, mn = 0; for(int i = 1; i <= q; i++){ int x; cin >> x; cur += x; mx = max(mx, cur); mn = min(mn, cur); pos.push_back(mx); neg.push_back(-mn); } int prv = X[1] + mn; for(int i = 1; i <= n; i++){ int lp = max(prv, X[i] + mn); int lo = X[i], hi = X[i + 1], ans = lo; while(lo <= hi){ int mid = (lo + hi) >> 1; int tmp = lower_bound(pos.begin(), pos.end(), mid - X[i]) - pos.begin(); int tmp2 = lower_bound(neg.begin(), neg.end(), X[i + 1] - mid + 1) - neg.begin(); if(tmp < tmp2)ans = mid, lo = mid + 1; else hi = mid - 1; } //cout << ans << ' ' << lp << ' '; cout << ans - lp << '\n'; prv = ans; } } main(){ ios::sync_with_stdio(0);cin.tie(0); int tc = 1; //cin >> tc; for(int tc1=1;tc1<=tc;tc1++){ // cout << "Case #" << tc1 << ": "; solve(); } }

Compilation message (stderr)

Main.cpp:46:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   46 | main(){
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...