oj.uz

답안 #583251

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
583251 2022-06-25T06:43:51 Z SlavicG 사탕 분배 (IOI21_candies) C++17
67 / 100
 2120 ms 176944 KB 
#include "bits/stdc++.h"
#include "candies.h"
using namespace std;

using ll = long long;
const ll inf = 1e16;
const int N = 4e5 + 10;
struct node {
    ll mn, mx, posmn, posmx;
};
node neutral = {inf, -inf, -1, -1};

node t[4 * N];
ll lazy[4 * N];

void push(int i, int l, int r) {
    if(!lazy[i]) return;
    t[i].mn += lazy[i];
    t[i].mx += lazy[i];
    if(l != r) {
        lazy[2 * i] += lazy[i];
        lazy[2 * i + 1] += lazy[i];
    }
    lazy[i] = 0;
}

node merge(node a, node b) {
    if(a.mn == -1) return b;
    if(b.mn == -1) return a;
    node c;
    c.mn = min(a.mn, b.mn);
    c.mx = max(a.mx, b.mx);
    c.posmn = (a.mn < b.mn ? a.posmn : b.posmn);
    c.posmx = (a.mx > b.mx ? a.posmx : b.posmx);
    return c;
}

void modif(int i, int l, int r, int tl, int tr, ll val) {
    push(i, l, r);
    if(l > tr || r < tl) return;
    if(l >= tl && r <= tr) {
        lazy[i] += val;
        push(i, l, r);
        return;
    }
    int mid = l + r >> 1;
    modif(2 * i, l, mid, tl, tr, val);
    modif(2 * i + 1, mid + 1, r, tl, tr, val);
    t[i] = merge(t[2 * i], t[2 * i + 1]);
}
node query(int i, int l, int r, int tl, int tr) {
    push(i, l, r);
    if(l > tr || r < tl) return neutral;
    if(l >= tl && r <= tr) return t[i];
    int mid = l + r >> 1;
    return merge(query(2 * i, l, mid, tl, tr), query(2 * i + 1, mid + 1, r, tl, tr));
}
void build(int i, int l, int r) {
    if(l > r) return;
    if(l == r) {
        t[i].mx = t[i].mn = 0;
        t[i].posmn = t[i].posmx = l;
        lazy[i] = 0;
        return;
    }
    int mid = l + r >> 1;
    build(2 * i, l, mid);
    build(2 * i + 1, mid + 1, r);
    t[i] = merge(t[2 * i], t[2 * i + 1]);
}
std::vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    for(int i = 0; i < 4 * N; ++i) t[i] = neutral, lazy[i] = 0;
    int n = c.size(), q = l.size();
    build(1, 0, q);

    vector<ll> a(n, 0);
    vector<vector<int>> st(n + 1), en(n + 1);
    for(int i = 0; i < q; ++i) {
        st[l[i]].push_back(i);
        en[r[i] + 1].push_back(i);
    }

    for(int i = 0; i < n; ++i) {
        for(auto j: en[i]) {
            modif(1, 0, q, j + 1, q, -v[j]);
        }
        for(auto j: st[i]) {
            modif(1, 0, q, j + 1, q, v[j]);
        }
        if(query(1, 0, q, q, q).mx - query(1, 0, q, q - 1, q - 1).mx >= c[i]) {
            a[i] = c[i];
            continue;
        }
        if(query(1, 0, q, q, q).mn - query(1, 0, q, q - 1, q - 1).mn <= -c[i]) {
            a[i] = 0;
            continue;
        }
        int l = 0, r = q - 1, pos = -1;
        while(l <= r) {
            int mid = l + r >> 1;
            node x = query(1, 0, q, mid, q);
            if(x.mx - x.mn >= c[i]) {
                pos = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        if(pos != -1) {
            node x = query(1, 0, q, pos, q);
            if(x.posmx < x.posmn) {
                a[i] = 0;
            } else {
                a[i] = c[i];
            }
            int j = max(x.posmn, x.posmx);
            if(j + 1 <= q) {
                node x = query(1, 0, q, j + 1, q);
                ll MN = x.mn - query(1, 0, q, j, j).mn;
                ll MX = x.mx - query(1, 0, q, j, j).mn;
                assert(MN > -c[i]);
                assert(MX < c[i]);
                if(!a[i] && MN < 0) a[i] -= MN;
                else if(a[i] == c[i] && MX > 0) a[i] -= MX;
                a[i] += query(1, 0, q, q, q).mx - query(1, 0, q, j, j).mx;
                assert(a[i] >= 0 && a[i] <= c[i]);
            }
        } else {
            node x = query(1, 0, q, q, q);
            a[i] = x.mx;
            x = query(1, 0, q, 0, q);
            if(x.mn < 0) a[i] -= x.mn;
            assert(a[i] >= 0 && a[i] <= c[i]);
        }
    }
    vector<int> cc(n);
    for(int i = 0; i < n; ++i) cc[i] = a[i];
    return cc;
}
/*
3
10 15 13
2
0 2 20
0 1 -11
*/

Compilation message

candies.cpp: In function 'void modif(int, int, int, int, int, ll)':
candies.cpp:46:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |     int mid = l + r >> 1;
      |               ~~^~~
candies.cpp: In function 'node query(int, int, int, int, int)':
candies.cpp:55:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |     int mid = l + r >> 1;
      |               ~~^~~
candies.cpp: In function 'void build(int, int, int)':
candies.cpp:66:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |     int mid = l + r >> 1;
      |               ~~^~~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:100:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |             int mid = l + r >> 1;
      |                       ~~^~~

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 62804 KB Output is correct
2 Correct 30 ms 62928 KB Output is correct
3 Correct 26 ms 62932 KB Output is correct
4 Correct 26 ms 62896 KB Output is correct
5 Correct 30 ms 63060 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1865 ms 88248 KB Output is correct
2 Correct 1912 ms 88108 KB Output is correct
3 Correct 1941 ms 88100 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 62932 KB Output is correct
2 Correct 318 ms 70576 KB Output is correct
3 Correct 769 ms 76388 KB Output is correct
4 Correct 2058 ms 88100 KB Output is correct
5 Correct 2120 ms 88104 KB Output is correct
6 Correct 1927 ms 88112 KB Output is correct
7 Correct 2059 ms 88116 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 62932 KB Output is correct
2 Correct 23 ms 62968 KB Output is correct
3 Correct 152 ms 69548 KB Output is correct
4 Correct 431 ms 76284 KB Output is correct
5 Correct 1111 ms 82724 KB Output is correct
6 Correct 1414 ms 82720 KB Output is correct
7 Correct 482 ms 82668 KB Output is correct
8 Correct 1221 ms 82712 KB Output is correct
9 Correct 1489 ms 82724 KB Output is correct

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 62804 KB Output is correct
2 Correct 30 ms 62928 KB Output is correct
3 Correct 26 ms 62932 KB Output is correct
4 Correct 26 ms 62896 KB Output is correct
5 Correct 30 ms 63060 KB Output is correct
6 Correct 1865 ms 88248 KB Output is correct
7 Correct 1912 ms 88108 KB Output is correct
8 Correct 1941 ms 88100 KB Output is correct
9 Correct 25 ms 62932 KB Output is correct
10 Correct 318 ms 70576 KB Output is correct
11 Correct 769 ms 76388 KB Output is correct
12 Correct 2058 ms 88100 KB Output is correct
13 Correct 2120 ms 88104 KB Output is correct
14 Correct 1927 ms 88112 KB Output is correct
15 Correct 2059 ms 88116 KB Output is correct
16 Correct 23 ms 62932 KB Output is correct
17 Correct 23 ms 62968 KB Output is correct
18 Correct 152 ms 69548 KB Output is correct
19 Correct 431 ms 76284 KB Output is correct
20 Correct 1111 ms 82724 KB Output is correct
21 Correct 1414 ms 82720 KB Output is correct
22 Correct 482 ms 82668 KB Output is correct
23 Correct 1221 ms 82712 KB Output is correct
24 Correct 1489 ms 82724 KB Output is correct
25 Correct 25 ms 62832 KB Output is correct
26 Correct 588 ms 76388 KB Output is correct
27 Correct 343 ms 70580 KB Output is correct
28 Runtime error 1884 ms 176944 KB Execution killed with signal 6
29 Halted 0 ms 0 KB -