Submission #1161288

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161288		tw20000807	Snowball (JOI21_ho_t2)	C++20	100 / 100	85 ms	6728 KiB

Main

#include<bits/stdc++.h>
#define int long long
#define all(v) v.begin(), v.end()
#define SZ(x) (int)x.size()
#define pii pair<int, int>
#define X first
#define Y second

using namespace std;
const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;//    998244353;
const int llmx = 8e18;

void sol(){
    int n, m;
    cin >> n >> m;
    vector< int > v(n + 2);
    v[0] = -llmx;
    v[n + 1] = llmx;
    for(int i = 1; i <= n; ++i){
        cin >> v[i];
    }
    vector< pii > t(m + 1);
    int now = 0;
    for(int i = 1; i <= m; ++i){
        int x; cin >> x;
        now += x;
        t[i] = t[i - 1];
        t[i].X = min(t[i].X, now);
        t[i].Y = max(t[i].Y, now);
        // cerr << t[i].X << " " << t[i].Y << "..\n";
    }
    for(int i = 1; i <= n; ++i){
        int ret = 0;
        {
            int l = 0, r = m, ans = 0;
            while(l <= r){
                int mid = (l + r) >> 1;
                ans = max(ans, min(-t[mid].X, v[i] - (v[i - 1] + t[mid].Y)));
                if(v[i - 1] + t[mid].Y <= v[i] + t[mid].X){
                    l = mid + 1;
                }
                else r = mid - 1;
            }
            // cerr << "L : " << ans << "..\n";
            if(ans > 0) ret += ans;
        }
        {
            int l = 0, r = m, ans = 0;
            while(l <= r){
                int mid = (l + r) >> 1;
                ans = max(ans, min(t[mid].Y, v[i + 1] + t[mid].X - v[i]));
                // cerr << mid << "!\n" << " " << t[mid].Y << " " << v[i + 1] + t[mid].X - v[i] << "!!\n";;
                if(v[i + 1] + t[mid].X >= v[i] + t[mid].Y){
                    l = mid + 1;
                }
                else r = mid - 1;
            }
            // cerr << "R : " << ans << "..\n";
            if(ans > 0) ret += ans;
        }
        cout << ret << "\n";
    }
}
/*
4 3
-2 3 5 8
2
-4
7

// 5
// 4
// 2
// 6


1 4
1000000000000
1000000000000
-1000000000000
-1000000000000
-1000000000000

// 3000000000000

10 10
-56 -43 -39 -31 -22 -5 0 12 18 22
-3
0
5
-4
-2
10
-13
-1
9
6


// 14
// 8
// 7
// 9
// 11
// 10
// 9
// 8
// 5
// 10


3 3
1 3 5
100
100
100

*/
signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cerr.tie(0);
    int t = 1; //cin >> t;
    while(t--) sol();
}

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