oj.uz

Submission #816765

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

int cnt[500005];

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[1<<20];
    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 1 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 494 ms 39508 KB Output is correct
5 Correct 235 ms 22472 KB Output is correct
6 Correct 647 ms 42076 KB Output is correct
7 Correct 250 ms 22536 KB Output is correct
8 Correct 851 ms 45232 KB Output is correct
9 Correct 538 ms 45772 KB Output is correct
10 Correct 839 ms 45192 KB Output is correct
11 Correct 517 ms 45744 KB Output is correct
12 Correct 227 ms 20208 KB Output is correct
13 Correct 361 ms 35608 KB Output is correct
14 Correct 519 ms 42384 KB Output is correct
15 Correct 533 ms 42420 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 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 1 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -