Submission #1031587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031587		underwaterkillerwhale	Snowball (JOI21_ho_t2)	C++17	33 / 100	2537 ms	11488 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];

struct fenwick_Treemx {
    ll fen[N];
    void update (int pos, ll val) {
        for (; pos <= Q; pos += pos & -pos) fen[pos] = max(fen[pos], val);
    }
    ll get (int pos) {
        ll res = 0;
        for (; pos > 0 ; pos -= pos & -pos) res = max(res, fen[pos]);
        return res;
    }
}fenmx;

struct fenwick_Treemn {
    ll fen[N];
    void update (int pos, ll val) {
        for (; pos <= Q; pos += pos & -pos) fen[pos] = min(fen[pos], val);
    }
    ll get (int pos) {
        ll res = 0;
        for (; pos > 0 ; pos -= pos & -pos) res = min(res, fen[pos]);
        return res;
    }
}fenmn;

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);
//        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] + fenmx.get(mid) >= X) rt = mid;
                        else lf = mid + 1;
                    }
                    if (a[i] + fenmx.get(rt) >= X) posR = rt;
                    else posR = -1;
                }
                if (posR == -1 || a[i + 1] + fenmn.get(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] + fenmn.get(mid) <= X) rt = mid;
                        else lf = mid + 1;
                    }
                    if (a[i] + fenmn.get(rt) <= X) posL = rt;
                    else posL = -1;
                }
//                cout << i << " "<<X << " "<<a[i] + fenmn.get(Q) <<"\n";
                if (posL == -1 || a[i - 1] + fenmx.get(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:73:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |                 ll X = lf + rt + 1 >> 1;
      |                        ~~~~~~~~^~~
Main.cpp:77:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |                         int mid = lf + rt >> 1;
      |                                   ~~~^~~~
Main.cpp:92:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |                 ll X = lf + rt >> 1;
      |                        ~~~^~~~

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