Submission #388172

#	Time	Username	Problem	Language	Result	Execution time	Memory
388172		BartolM	Snowball (JOI21_ho_t2)	C++17	100 / 100	126 ms	15468 KiB

Main

#define DEBUG 0
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=2e5+5;

int n, q;
ll p[N], que[N], sol[N];
vector <pair <ll, int> > v;

void solve() {
    for (int i=1; i<n; ++i) v.pb(mp(p[i]-p[i-1], i-1));
    sort(v.begin(), v.end());
    int j=0;
    ll mini=0, maxi=0, curr=0;
    for (int i=0; i<q; ++i) {
        curr+=que[i];
        mini=min(mini, curr); maxi=max(maxi, curr);
        #if DEBUG
            printf("i: %d, curr: %lld\n", i, curr);
        #endif
        while (j!=(int)v.size() && v[j].X<=maxi-mini) {
            if (que[i]>0) sol[v[j].Y]+=v[j].X+mini, sol[v[j].Y+1]-=mini;
            else sol[v[j].Y]+=maxi, sol[v[j].Y+1]+=v[j].X-maxi;

            #if DEBUG
                printf("index: %d, raz: %lld, mini: %lld, maxi: %lld\n", v[j].Y, v[j].X, mini, maxi);
            #endif // DEBUG

            j++;
        }
    }

    while (j<(int)v.size()) sol[v[j].Y]+=maxi, sol[v[j++].Y+1]-=mini;

    sol[0]-=mini; sol[n-1]+=maxi;
    for (int i=0; i<n; ++i) printf("%lld\n", sol[i]);
}

void load() {
    scanf("%d %d", &n, &q);
    for (int i=0; i<n; ++i) scanf("%lld", p+i);
    for (int i=0; i<q; ++i) scanf("%lld", que+i);
}

int main() {
    load();
    solve();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void load()':
Main.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:54:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |     for (int i=0; i<n; ++i) scanf("%lld", p+i);
      |                             ~~~~~^~~~~~~~~~~~~
Main.cpp:55:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |     for (int i=0; i<q; ++i) scanf("%lld", que+i);
      |                             ~~~~~^~~~~~~~~~~~~~~

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