Submission #1031595

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031595		underwaterkillerwhale	Snowball (JOI21_ho_t2)	C++17	100 / 100	924 ms	13908 KiB

Main

#include <bits/stdc++.h>
#define se              second
#define fs              first
#define mp              make_pair
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)
using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N = 2e5 + 7;
const int Mod = 1e9 + 7;
const int szBL = 320;
const ll INF = 1e18;
const int BASE = 137;

int n, Q;
ll a[N];
ll qr[N];
ll premx[N], premn[N];

void solution () {
    cin >> n >> Q;
    rep (i, 1, n) cin >> a[i];
    ll pre = 0;
    rep (i, 1, Q) {
        cin >> qr[i];
        pre += qr[i];
//        fenmx.update (i, pre);
//        fenmn.update (i, pre);
        premx[i] = max(premx[i - 1], pre);
        premn[i] = min(premn[i - 1], pre);

//        cout << pre <<"\n";
    }
//    cout << fenmn.get(Q) <<" aa\n";
//    return;
    a[n + 1] = INF;
    a[0] = -INF;
    rep (i, 1, n) {
        ll R; {
            ll lf = a[i], rt = INF;
            while (lf < rt) {
                ll X = lf + rt + 1 >> 1;
                int posR; {
                    int lf = 0, rt = Q;
                    while (lf < rt) {
                        int mid = lf + rt >> 1;
                        if (a[i] + premx[mid] >= X) rt = mid;
                        else lf = mid + 1;
                    }
                    if (a[i] + premx[rt] >= X) posR = rt;
                    else posR = -1;
                }
                if (posR == -1 || a[i + 1] + premn[posR] < X) rt = X - 1;
                else lf = X;
            }
            R = lf;
        }
        ll L; {
            ll lf = -INF, rt = a[i];
            while (lf < rt) {
                ll X = lf + rt >> 1;
                int posL; {
                    int lf = 0, rt = Q;
                    while (lf < rt) {
                        int mid = (lf + rt) / 2;
                        if (a[i] + premn[mid] <= X) rt = mid;
                        else lf = mid + 1;
                    }
                    if (a[i] + premn[rt] <= X) posL = rt;
                    else posL = -1;
                }
//                cout << i << " "<<X << " "<<a[i] + fenmn.get(Q) <<"\n";
                if (posL == -1 || a[i - 1] + premx[posL] > X) lf = X + 1;
                else rt = X;
            }
            L = lf;
        }
        cout << R - L<<"\n";
    }
}

#define file(name) freopen(name".inp", "r", stdin); \
freopen(name".out", "w", stdout);

int main () {
//    file("c");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll num_Test = 1;
//    cin >> num_Test;
    while(num_Test--)
        solution();
}

Compilation message (stderr)

Main.cpp: In function 'void solution()':
Main.cpp:53:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |                 ll X = lf + rt + 1 >> 1;
      |                        ~~~~~~~~^~~
Main.cpp:57:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |                         int mid = lf + rt >> 1;
      |                                   ~~~^~~~
Main.cpp:72:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |                 ll X = lf + rt >> 1;
      |                        ~~~^~~~

• Subtask 1: 33 / 33
• Subtask 2: 67 / 67