Submission #1106957

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106957		elush	단층 (JOI16_ho_t5)	C++14	100 / 100	150 ms	14932 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 seg;
    Seg() {}
    Seg(int m) {
        for (n = 1; n < m; n <<= 1);
        seg.resize(2 * n);
    }
    void Update(int l, int r, pii x) {
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) seg[l++] += x;
            if (r & 1) seg[--r] += x;
        }
    }
    pii Query(int i) {
        pii ans = {0, 0};
        for (i += n; i; i >>= 1) ans += seg[i];
        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 <= 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 begin = 0, end = n + 1, mid;
            while (begin < end) {
                mid = (begin + end) >> 1;
                auto [a, b] = seg.Query(mid);
                if (a + b <= x[i]) begin = mid + 1;
                else end = mid;
            }
            seg.Update(0, end, {-l[i], l[i]});
        } else {
            int begin = 0, end = n + 1, mid;
            while (begin < end) {
                mid = (begin + end) >> 1;
                auto [a, b] = seg.Query(mid);
                if (a - b <= x[i]) begin = mid + 1;
                else end = mid;
            }
            seg.Update(end, n + 1, {l[i], l[i]});
        }
    }
    vi ans(n);
    for (int i = 1; i <= n; i++) ans[i - 1] = seg.Query(i).y;
    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';
}

Compilation message (stderr)

2016_ho_t5.cpp: In function 'vi Solve(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
2016_ho_t5.cpp:49:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |                 auto [a, b] = seg.Query(mid);
      |                      ^
2016_ho_t5.cpp:58:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |                 auto [a, b] = seg.Query(mid);
      |                      ^

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