oj.uz

Submission #817159

# Submission time Handle Problem Language Result Execution time Memory
817159 2023-08-09T09:57:45 Z 이성호(#10126) Ants and Sugar (JOI22_sugar) C++17
26 / 100
 712 ms 57568 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;
const int inf = 1e15;

pair<int, int> X[250005];
pair<int, int> Y[250005];
pair<int, int> query[250005];
int prf[250005];
int prf2[250005];
int ant[250005];

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 ? prf2[e] : 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] = -ant[s] + prf[s];
    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, 250005, 1);
    for (int i = 0; i < Q / 2; i++) {
        int t, x, a; cin >> t >> x >> a;
        X[i] = make_pair(x, a);
        cout << 0 << '\n';
    }
    for (int i = Q / 2; i < Q; i++) {
        int t, x, a; cin >> t >> x >> a;
        Y[i-Q/2] = query[i-Q/2] = make_pair(x, a);
    }
    sort(Y, Y + Q/2);
    for (int i = 0; i < Q / 2; i++) {
        int l = lower_bound(Y, Y + Q / 2, make_pair(X[i].first - L, -inf)) - Y;
        int r = lower_bound(Y, Y + Q / 2, make_pair(X[i].first + L + 1, -inf)) - Y - 1;
        if (l <= r) {
            prf[l] += X[i].second;
            prf[r+1] -= X[i].second;
            prf2[l] -= X[i].second;
            prf2[r] += X[i].second;
        }
    }
    for (int i = 1; i < Q / 2; i++) {
        prf[i] += prf[i-1];
        prf2[i] += prf2[i-1];
    }
    int tot = 0;
    seg.init(0, 250005, 1);
    for (int i = 0; i < Q / 2; i++) {
        Node nd = def(i);
        seg.update(1, i, nd);
    }
    for (int i = 0; i < Q / 2; i++) {
        tot += query[i].second;
        int pos = lower_bound(Y, Y + Q / 2, query[i]) - Y;
        ant[pos] += query[i].second;
        Node nd = def(pos);
        seg.update(1, pos, nd);
        cout << tot + seg.query() << '\n';
    }
    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 24916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 24916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24900 KB Output is correct
2 Correct 198 ms 34724 KB Output is correct
3 Correct 288 ms 38476 KB Output is correct
4 Correct 423 ms 46920 KB Output is correct
5 Correct 419 ms 46944 KB Output is correct
6 Correct 541 ms 42408 KB Output is correct
7 Correct 42 ms 26828 KB Output is correct
8 Correct 235 ms 37404 KB Output is correct
9 Correct 366 ms 43560 KB Output is correct
10 Correct 644 ms 57328 KB Output is correct
11 Correct 676 ms 57404 KB Output is correct
12 Correct 629 ms 57392 KB Output is correct
13 Correct 664 ms 57328 KB Output is correct
14 Correct 640 ms 57416 KB Output is correct
15 Correct 633 ms 57216 KB Output is correct
16 Correct 678 ms 57420 KB Output is correct
17 Correct 675 ms 57400 KB Output is correct
18 Correct 658 ms 57468 KB Output is correct
19 Correct 639 ms 57404 KB Output is correct
20 Correct 656 ms 57568 KB Output is correct
21 Correct 695 ms 57532 KB Output is correct
22 Correct 712 ms 57460 KB Output is correct
23 Correct 624 ms 57484 KB Output is correct
24 Correct 616 ms 57508 KB Output is correct
25 Correct 666 ms 57460 KB Output is correct

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 24916 KB Output isn't correct
2 Halted 0 ms 0 KB -