Submission #1106948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106948		elush	단층 (JOI16_ho_t5)	C++14	100 / 100	332 ms	35656 KiB

2016_ho_t5

#include <bits/stdc++.h>
#define chkmax(a, b) a = max(a, b)
#define all(v) v.begin(), v.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pii;
typedef vector<vi> vvi;
typedef vector<pii> vii;

void operator+=(pii &p1, pii p2) {
    p1.x += p2.x, p1.y += p2.y;
}

struct Seg {
    int n;
    vii ri, le, lazy;
    Seg() {}
    Seg(int m) {
        for (n = 1; n < m; n <<= 1);
        ri.resize(2 * n), le.resize(2 * n);
        lazy.resize(2 * n);
    }
    void Push(int i) {
        ri[i << 1] += lazy[i];
        le[i << 1] += lazy[i];
        lazy[i << 1] += lazy[i];
        ri[i << 1 | 1] += lazy[i];
        le[i << 1 | 1] += lazy[i];
        lazy[i << 1 | 1] += lazy[i];
        lazy[i] = {0, 0};
    }
    void Pull(int i) {
        ri[i] = ri[i << 1 | 1];
        le[i] = le[i << 1];
    }
    void Update(int a, int b, pii add, int i, int l, int r) {
        if (a <= l && r <= b) {
            lazy[i] += add;
            le[i] += add;
            ri[i] += add;
            return;
        }
        if (r <= a || b <= l) return;
        Push(i);
        Update(a, b, add, i << 1, l, (l + r) >> 1);
        Update(a, b, add, i << 1 | 1, (l + r) >> 1, r);
        Pull(i);
    }
    void Update(int a, int b, ll x, ll y) {
        Update(a, b, {x, y}, 1, 0, n);
    }
    int QueryPrefix(ll dig) {
        int i = 1;
        while (i < n) {
            Push(i);
            i <<= 1;
            if (ri[i].x + ri[i].y <= dig) i |= 1;
        }
        if (ri[i].x + ri[i].y <= dig) i++;
        return i - n;
    }
    int QuerySuffix(ll dig) {
        int i = 1;
        while (i < n) {
            Push(i);
            i = i << 1 | 1;
            if (le[i].x - le[i].y >= dig) i ^= 1;
        }
        if (le[i].x - le[i].y >= dig) i--;
        return i - n;
    }
    ll Query(int i) {
        ll ans = 0;
        for (i += n; i; i >>= 1) ans += lazy[i].y;
        return ans;
    }
};

vi Solve(int n, int q, vector<int> x, vector<int> d, vector<int> l) {
    Seg seg(n + 1);
    for (int i = 0; i < seg.n; i++) {
        seg.Update(i, i + 1, i, 0);
    }
    reverse(all(x)), reverse(all(d)), reverse(all(l));
    for (int i = 0; i < q; i++) {
        if (d[i] == 1) {
            int r = seg.QueryPrefix(x[i]);
            seg.Update(0, r, -l[i], l[i]);
        } else {
            int le = seg.QuerySuffix(x[i] + 1);
            seg.Update(le + 1, seg.n, l[i], l[i]);
        }
    }
    vi ans(n);
    for (int i = 1; i <= n; i++) ans[i - 1] = seg.Query(i);
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int N, Q;
    cin >> N >> Q;
    std::vector<int> X(Q), D(Q), L(Q);
    for (int i = 0; i < Q; i++) cin >> X[i] >> D[i] >> L[i];
    vi ans = Solve(N, Q, X, D, L);
    for (int i = 0; i < N; i++) cout << ans[i] << '\n';
}

• Subtask 1: 18 / 18
• Subtask 2: 16 / 16
• Subtask 3: 66 / 66