oj.uz

답안 #883485

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
883485 2023-12-05T10:55:21 Z vjudge1 Ants and Sugar (JOI22_sugar) C++17
0 / 100
 408 ms 34560 KB 
// https://oj.uz/problem/view/JOI22_sugar

#include <bits/stdc++.h>
using namespace std;

/*

Hall's theorem
Answer = A - max(|S| - |NG(S)|)

*/

const int64_t inf = 1e18;

class segtree_t {
       public:
        segtree_t *left, *right;
        int l, r, m;
        int64_t x[2][2], lazyx, lazy_mid, mid;

        segtree_t(int l, int r) : l(l), r(r), m(l + r >> 1) {
                for (int i = 0; i < 2; i++) {
                        for (int j = 0; j < 2; j++) {
                                x[i][j] = 0;
                        }
                }
                if (l == r) return;
                left = new segtree_t(l, m);
                right = new segtree_t(m + 1, r);
        }

        void Update(int s, int t, int64_t val) {
                if (l > t || r < s) return;
                if (s <= l && r <= t) {
                        for (int i = 0; i < 2; i++) {
                                for (int j = 0; j < 2; j++) {
                                        x[i][j] += val;
                                }
                        }
                        lazyx += val;
                        lazy_mid += val;
                        mid += val;
                        return;
                }
                Down();
                if (s <= m && m < t) mid += val;
                left->Update(s, t, val);
                right->Update(s, t, val);
                Up();
        }

        void Down() {
                for (int i = 0; i < 2; i++) {
                        for (int j = 0; j < 2; j++) {
                                left->x[i][j] += lazyx;
                                right->x[i][j] += lazyx;
                        }
                }
                left->lazy_mid += lazy_mid;
                left->lazyx += lazyx;
                left->mid += lazy_mid;
                right->lazy_mid += lazy_mid;
                right->lazyx += lazyx;
                right->mid += lazy_mid;
                lazy_mid = lazyx = 0;
        }

        void Up() {
                for (int i = 0; i < 2; i++) {
                        for (int j = 0; j < 2; j++) {
                                x[i][j] = -inf;
                                for (int k = 0; k < 2; k++) {
                                        x[i][j] = max<int64_t>(x[i][j], left->x[i][k] + right->x[k][j] - 1ll * k * mid);
                                }
                        }
                }
                for (int i = 0; i < 2; i++) {
                        x[i][0] = max(x[i][0], left->x[i][0]);
                        x[0][i] = max(x[0][i], right->x[0][i]);
                }
        }
};

int32_t main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);

        int q, L;
        cin >> q >> L;
        vector<int> t(q), a(q), x(q);
        for (int i = 0; i < q; i++) cin >> t[i] >> x[i] >> a[i];
        vector<int> cord;
        for (int i = 0; i < q; i++) {
                if (t[i] == 1) cord.emplace_back(x[i]);
        }
        sort(cord.begin(), cord.end());
        cord.resize(unique(cord.begin(), cord.end()) - cord.begin());
        int N = cord.size();

        segtree_t* tree = new segtree_t(0, N);

        int64_t A = 0;

        for (int i = 0; i < q; i++) {
                if (t[i] == 1) {
                        A += a[i];
                        int y = lower_bound(cord.begin(), cord.end(), x[i]) - cord.begin();
                        tree->Update(y, y, +a[i]);
                } else {
                        int u = lower_bound(cord.begin(), cord.end(), x[i] - L) - cord.begin();
                        int v = upper_bound(cord.begin(), cord.end(), x[i] + L) - cord.begin() - 1;
                        tree->Update(u, v, -a[i]);
                }
                cout << A - max<int64_t>(0, tree->x[0][0]) << '\n';
        }
}

Compilation message

sugar.cpp: In constructor 'segtree_t::segtree_t(int, int)':
sugar.cpp:21:51: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |         segtree_t(int l, int r) : l(l), r(r), m(l + r >> 1) {
      |                                                 ~~^~~

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 2 ms 604 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 408 ms 34560 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 194 ms 29056 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 2 ms 604 KB Output isn't correct
7 Halted 0 ms 0 KB -