Submission #701272

#	Time	Username	Problem	Language	Result	Execution time	Memory
701272		stevancv	Snowball (JOI21_ho_t2)	C++14	100 / 100	122 ms	16868 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 2e5 + 2;
const int inf = 2e9;
ll a[N], b[N], mn[N], mx[N], l[N], r[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) cin >> b[i];
    ll s = 0;
    for (int i = 1; i <= m; i++) {
        s += b[i];
        mn[i] = min(mn[i - 1], s);
        mx[i] = max(mx[i - 1], s);
    }
    for (int i = 1; i <= n; i++) {
        l[i] = a[i] + mn[m];
        r[i] = a[i] + mx[m];
    }
    for (int i = 2; i <= n; i++) {
        int lo = 1, hi = m, pos = -1;
        while (lo <= hi) {
            int mid = lo + hi >> 1;
            if (mx[mid] - mn[mid] >= a[i] - a[i - 1]) {
                pos = mid;
                hi = mid - 1;
            }
            else lo = mid + 1;
        }
        if (pos == -1) continue;
        if (b[pos] < 0) r[i - 1] = l[i] = a[i - 1] + mx[pos - 1];
        else r[i - 1] = l[i] = a[i] + mn[pos - 1];
    }
    for (int i = 1; i <= n; i++) cout << r[i] - l[i] << en;
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:33:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |             int mid = lo + hi >> 1;
      |                       ~~~^~~~

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