oj.uz

답안 #621498

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
621498 2022-08-03T21:53:35 Z resting 사탕 분배 (IOI21_candies) C++17
0 / 100
 465 ms 67768 KB 
#include "candies.h"

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

#define ll long long
#define inf 0x7FFFFFFF
#define ff first
#define ss second

struct info {
    ll mn, mx, sm, mnp, mxp;
    info() : mn(0), mx(0), sm(0), mnp(-1), mxp(-1){};
    info(ll v, ll p) : mn(v), mx(v), sm(v), mnp(p), mxp(p){};
};
struct node {
    ll l, r;  // mleft, right
    info d;
    node() : node(-1, -1){};
    node(ll l, ll r) : l(l), r(r){};
};

struct st {
    vector<node> t;
    const ll n;
    st(ll n) : t(n * 4), n(n) { build(0, n - 1, 0); }
    void build(ll l, ll r, ll x) {
        t[x] = node(l, r);
        if (l == r) return;
        ll m = l + r >> 1;
        build(l, m, x * 2 + 1);
        build(m + 1, r, x * 2 + 2);
        merge(x);
    }

    void upd(ll i, ll v, ll x = 0) {
        if (t[x].l > i || t[x].r < i) return;
        if (t[x].l == t[x].r) {
            t[x].d = info(v, i);
            return;
        }
        upd(i, v, x * 2 + 1);
        upd(i, v, x * 2 + 2);
        merge(x);
    }

    ll q(ll c) {
        info d = query(c);
        if (d.mnp < d.mxp) {
            // touches top wall??
            return c + sum(d.mxp + 1, n - 1);
        } else {
            return sum(d.mnp + 1, n - 1);
        }
    }

    ll sum(ll l, ll r, ll x = 0) {
        if (t[x].l > r || t[x].r < l) return 0;
        if (t[x].l >= l && t[x].r <= r) return t[x].d.sm;
        return sum(l, r, x * 2 + 1) + sum(l, r, x * 2 + 2);
    }

    info query(ll c, info d = info(), ll x = 0) {
        if (t[x].l == t[x].r) return merge(t[x].d, d);
        info tmp = merge(t[x * 2 + 2].d, d);
        if (tmp.mx - tmp.mn >= c) {
            return query(c, d, x * 2 + 2);
        }
        return query(c, tmp, x * 2 + 1);
    }

    void merge(ll x) {
        t[x].d = merge(t[x * 2 + 1].d, t[x * 2 + 2].d);
    }

    info merge(info a, info b) {
        info c;
        c.sm = a.sm + b.sm;
        if (a.mn <= a.sm + b.mn) {
            c.mn = a.mn;
            c.mnp = a.mnp;
        } else {
            c.mn = a.sm + b.mn;
            c.mnp = b.mnp;
        }
        if (a.mx >= a.sm + b.mx) {
            c.mx = a.mx;
            c.mxp = a.mxp;
        } else {
            c.mx = a.sm + b.mxp;
            c.mxp = b.mxp;
        }
        return c;
    }
};

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    const ll n = c.size();
    const ll q = l.size();
    std::vector<int> s(n);
    st ac(q + 2);
    ac.upd(0, -inf);
    ac.upd(1, inf);
    vector<vector<pair<int, int>>> qs(n + 1);
    for (int i = 0; i < q; i++) {
        qs[l[i]].push_back({i + 2, v[i]});
        qs[r[i] + 1].push_back({i + 2, 0});
    }
    for (int i = 0; i < n; i++) {
        for (auto &x : qs[i])
            ac.upd(x.ff, x.ss);
        s[i] = ac.q(c[i]);
    }

    return s;
}

Compilation message

candies.cpp: In member function 'void st::build(long long int, long long int, long long int)':
candies.cpp:30:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |         ll m = l + r >> 1;
      |                ~~^~~

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 465 ms 67768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -