Submission #891679

#	Time	Username	Problem	Language	Result	Execution time	Memory
891679		hafo	Snowball (JOI21_ho_t2)	C++14	0 / 100	1 ms	4444 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 2e5 + 7;
const ll oo = 1e18 + 69;

int n, t, p[maxn], idl[maxn], idr[maxn];
ll x[maxn], w, res[maxn], cntl, cntr, cnt;
priority_queue<pall, vector<pall>, greater<pall>> q;

int find_node(int u) {
    return p[u] < 0 ? u:p[u] = find_node(p[u]);
} 

void do_l() {
    w = -w;
    cnt -= w;
    while(Size(q) && q.top().fi <= w) {
        auto top = q.top();
        q.pop();

        int u = top.se;
        int v = u + 1;
        u = find_node(u);
        v = find_node(v);
        // hop v vao u
        res[idl[v]] += cntl + max(0LL, top.fi - cntr - cntl);
        res[idr[u]] += cntr;
        p[u] += p[v];
        p[v] = u;
        idr[u] = idr[v];
    }
    if(cnt > 0) maxi(cntr, cnt);
    if(cnt < 0) maxi(cntl, -cnt);
}

void do_r() {
    cnt += w;
    while(Size(q) && q.top().fi <= w) {
        auto top = q.top();
        q.pop();

        int u = top.se;
        int v = top.se + 1;
        u = find_node(u);
        v = find_node(v);

        // hop u vao v
        res[idr[u]] += cntr + max(0LL, top.fi - cntl - cntr);
        res[idl[v]] += cntl;
        p[v] += p[u];
        p[u] = v;
        idl[v] = idl[u];
    }
    if(cnt > 0) maxi(cntr, cnt);
    if(cnt < 0) maxi(cntl, -cnt);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    cin>>n>>t;
    for(int i = 1; i <= n; i++) {
        cin>>x[i];
        p[i] = -1;
        idl[i] = idr[i] = i;
    }

    for(int i = 1; i < n; i++) {
        q.push({x[i + 1] - x[i], i});
    }

    while(t--) {
        cin>>w;
        if(w < 0) do_l();
        else do_r();
    }

    for(int i = 1; i <= n; i++) {
        if(find_node(i) == i) {
            res[idl[i]] += cntl;
            res[idr[i]] += cntr;
        }
    }
    for(int i = 1; i <= n; i++) cout<<res[i]<<"\n";
    return 0;
}   

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