Submission #607397

#	Time	Username	Problem	Language	Result	Execution time	Memory
607397		okaybody10	Snowball (JOI21_ho_t2)	C++17	100 / 100	111 ms	13944 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;
#define MAX LLONG_MAX/3
#define x first
#define y second

int p;
ll l, r, v;
vector<pli> co;
ll a[200006], ans[200006];

int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    a[0] = -MAX, a[n+1] = MAX;
    for(int i = 1; i<=n;i++) scanf("%lld", &a[i]), co.push_back({a[i]-a[i-1], i-1}); // range
    co.push_back({a[n+1]-a[n], n});
    sort(co.begin(), co.end());
    while(q--) {
        ll t;
        scanf("%lld", &t);
        if(t>=0) {
            // if t > 0, wind is east direction
            // That means, snowball goes to right, so update right value
            // If |now wind value| > |before wind value|, update. else, not update => max operation
            v += t;
            r = max(r, v);
            // if l + r > (range) + wind east, so Left snowball will be moved
            // Right snowball's weight: L, Left snowball's weight: (range)-L
            // After that, doesn't remain weight => skip
            while(p<=n && co[p].x <= l+r) {
                ans[co[p].y+1] += l;
                ans[co[p].y] += co[p].x - l;
                ++p;
            }
        }
        else {
            // if t < 0, wind is west direction
            // That means, snowball goes to left, so update left value
            // If |now wind value| > |before wind value|, update. else, not update => max operation
            v += t;
            l = max(l, -v);
            while(p<=n && co[p].x <= l+r) {
                ans[co[p].y] += r;
                ans[co[p].y+1] += co[p].x - r;
                ++p;
            }
        }
    }
    while(p<=n) {
        ans[co[p].y] += r;
        ans[co[p].y + 1] += l;
        ++p;
    }
    for(int i=1; i<=n;i++) printf("%lld\n", ans[i]);
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:18:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     for(int i = 1; i<=n;i++) scanf("%lld", &a[i]), co.push_back({a[i]-a[i-1], i-1}); // range
      |                              ~~~~~^~~~~~~~~~~~~~~
Main.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         scanf("%lld", &t);
      |         ~~~~~^~~~~~~~~~~~

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