oj.uz

답안 #1102242

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1102242 2024-10-17T19:20:28 Z epicci23 사탕 분배 (IOI21_candies) C++17
100 / 100
 696 ms 56140 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1000000 + 10;
const int MAXQ = 1000000 + 10;
const long long INF = (long long)(1e18);

struct SegmentTree {
    int n;
    long long vmin[(MAXN + MAXQ) * 4], vmax[(MAXN + MAXQ) * 4], lazy[(MAXN + MAXQ) * 4];

    void init(int _n) {
        n = _n;
        for(int i = 0; i <= 4 * n; ++i) vmin[i] = vmax[i] = lazy[i] = 0;
    }

    void lazy_update(int node, int from, int to) {
        vmin[node] += lazy[node]; vmax[node] += lazy[node];
        if (from < to) {
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
        lazy[node] = 0;
    }

    void update(int node, int from, int to, int L, int R, int add) {
        lazy_update(node, from, to);
        if (from > R || to < L) return;
        if (L <= from && to <= R) {
            lazy[node] += add;
            lazy_update(node, from, to);
            return;
        }
        int mid = (from + to) / 2;
        update(node * 2, from, mid, L, R, add);
        update(node * 2 + 1, mid + 1, to, L, R, add);
        vmin[node] = min(vmin[node * 2], vmin[node * 2 + 1]);
        vmax[node] = max(vmax[node * 2], vmax[node * 2 + 1]);
    }

    long long get(int node, int from, int to, int lowerbound) {
        lazy_update(node, from, to);
        if (from == to) return vmin[node];
        int mid = (from + to) / 2;
        if (vmax[node * 2 + 1] + lazy[node * 2 + 1] >= lowerbound)
            return get(node * 2 + 1, mid + 1, to, lowerbound);
        return min( vmin[node * 2 + 1] + lazy[node * 2 + 1], get(node * 2, from, mid, lowerbound) );
    }

    void add_range(int L, int R, int add) {
        update(1, 0, n - 1, L, R, add);
    }

    long long min_suffix(int lowerbound) {
        if (vmax[1] < lowerbound) return -INF;
        return min(0LL, get(1, 0, n - 1, lowerbound));
    }
} T;

vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
    int n = C.size();
    vector<int> A(n);
    int q = L.size();
    vector< vector<int> > begin_at(n, vector<int>()), end_at(n, vector<int>());
    for(int i = 0; i < q; ++i) {
        begin_at[L[i]].push_back(i);
        end_at[R[i]].push_back(i);
    }

    T.init(1 + q);
    vector<int> final_A(n);
    for(int i = 0; i < n; ++i) {
        if (i > 0) {
            //T.add_range(0, 0, -A[i - 1]);
            for(int j : end_at[i - 1]) T.add_range(0, 1 + j, -V[j]);
        }
        //T.add_range(0, 0, A[i]);
        for(int j : begin_at[i]) T.add_range(0, 1 + j, V[j]);

        int low = 1, high = C[i] + 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            long long smin = T.min_suffix(mid);
            if (-smin + mid > C[i]) high = mid - 1;
            else low = mid + 1;
        }
        final_A[i] = high;
    }

    return final_A;
}

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4436 KB Output is correct
2 Correct 1 ms 4436 KB Output is correct
3 Correct 2 ms 4856 KB Output is correct
4 Correct 2 ms 4692 KB Output is correct
5 Correct 4 ms 4692 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 586 ms 54356 KB Output is correct
2 Correct 511 ms 53580 KB Output is correct
3 Correct 506 ms 53324 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4436 KB Output is correct
2 Correct 166 ms 35808 KB Output is correct
3 Correct 264 ms 19284 KB Output is correct
4 Correct 696 ms 55372 KB Output is correct
5 Correct 660 ms 55884 KB Output is correct
6 Correct 659 ms 56140 KB Output is correct
7 Correct 287 ms 55616 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4436 KB Output is correct
2 Correct 1 ms 4436 KB Output is correct
3 Correct 77 ms 34232 KB Output is correct
4 Correct 110 ms 18272 KB Output is correct
5 Correct 267 ms 47548 KB Output is correct
6 Correct 312 ms 48312 KB Output is correct
7 Correct 469 ms 49036 KB Output is correct
8 Correct 250 ms 47804 KB Output is correct
9 Correct 605 ms 48940 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4436 KB Output is correct
2 Correct 1 ms 4436 KB Output is correct
3 Correct 2 ms 4856 KB Output is correct
4 Correct 2 ms 4692 KB Output is correct
5 Correct 4 ms 4692 KB Output is correct
6 Correct 586 ms 54356 KB Output is correct
7 Correct 511 ms 53580 KB Output is correct
8 Correct 506 ms 53324 KB Output is correct
9 Correct 1 ms 4436 KB Output is correct
10 Correct 166 ms 35808 KB Output is correct
11 Correct 264 ms 19284 KB Output is correct
12 Correct 696 ms 55372 KB Output is correct
13 Correct 660 ms 55884 KB Output is correct
14 Correct 659 ms 56140 KB Output is correct
15 Correct 287 ms 55616 KB Output is correct
16 Correct 1 ms 4436 KB Output is correct
17 Correct 1 ms 4436 KB Output is correct
18 Correct 77 ms 34232 KB Output is correct
19 Correct 110 ms 18272 KB Output is correct
20 Correct 267 ms 47548 KB Output is correct
21 Correct 312 ms 48312 KB Output is correct
22 Correct 469 ms 49036 KB Output is correct
23 Correct 250 ms 47804 KB Output is correct
24 Correct 605 ms 48940 KB Output is correct
25 Correct 1 ms 4436 KB Output is correct
26 Correct 93 ms 18404 KB Output is correct
27 Correct 159 ms 35300 KB Output is correct
28 Correct 392 ms 54136 KB Output is correct
29 Correct 465 ms 54392 KB Output is correct
30 Correct 495 ms 54604 KB Output is correct
31 Correct 503 ms 54860 KB Output is correct
32 Correct 567 ms 54980 KB Output is correct