oj.uz

Submission #816761

# Submission time Handle Problem Language Result Execution time Memory
816761 2023-08-09T06:31:40 Z 이성호(#10126) Ants and Sugar (JOI22_sugar) C++17
0 / 100
 38 ms 49052 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;
const int inf = 1e15;

int cnt[100005];

struct Node
{
    int s, e;
    int val[2][2];
    Node operator+(const Node &nd) {
        Node ret;
        ret.s = s;
        ret.e = nd.e;
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                ret.val[i][j] = inf;
                for (int k = 0; k < 2; k++) {
                    for (int l = 0; l < 2; l++) {
                        ret.val[i][j] = min(ret.val[i][j], val[i][k] + nd.val[l][j] - ((k == 1 && l == 1 ? cnt[2*e+2] : 0)));
                    }
                }
            }
        }
        return ret;
    }
};

struct SegTree
{
    Node tree[500005];
    void init(int s, int e, int node)
    {
        tree[node].s = s, tree[node].e = e;
        if (s != e) {
            init(s, (s+e)/2, 2*node);
            init((s+e)/2+1, e, 2*node+1);
        }
    }
    void update(int node, int id, Node x) {
        if (tree[node].e < id || id < tree[node].s) return;
        if (tree[node].s == tree[node].e) {
            tree[node] = x;
            return;
        }
        update(2*node, id, x);
        update(2*node+1, id, x);
        tree[node] = tree[2*node] + tree[2*node+1];
    }
    int query()
    {
        return min(min(tree[1].val[0][0], tree[1].val[0][1]), min(tree[1].val[1][0], tree[1].val[1][1]));
    }
};

SegTree seg;

Node def(int s)
{
    Node nd; nd.s = nd.e = s;
    nd.val[1][1] = cnt[2*s] + cnt[2*s+2] - cnt[2*s+1];
    nd.val[0][0] = 0;
    nd.val[0][1] = nd.val[1][0] = inf;  
    return nd;
}

signed main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int Q, L; cin >> Q >> L;
    seg.init(0, Q/2+5, 1);
    int cur = 0;
    for (int i = 1; i <= Q; i++) {
        int t, x, a; cin >> t >> x >> a;
        cnt[x] += a;
        if (t == 1) {
            cur += a;
            Node nd = def(x/2);
            seg.update(1, x/2, nd);
        }
        else {
            if (x) {
                Node nd = def(x/2-1);
                seg.update(1, x/2-1, nd);
            }
            Node nd = def(x/2);
            seg.update(1, x/2, nd);
        }
        cout << cur + seg.query() << '\n';
    }
    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Runtime error 38 ms 49052 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -