oj.uz

답안 #444393

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
444393 2021-07-14T00:29:59 Z JvThunder 사탕 분배 (IOI21_candies) C++17
100 / 100
 1393 ms 48324 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
 
const int MAXQ = 1000005;
const ll INF = (ll)(1e18);
 
struct SegmentTree 
{
    int n;
    ll vmin[MAXQ] = {0};
    ll vmax[MAXQ] = {0};
    ll lazy[MAXQ] = {0};
 
    void init(int _n) { n = _n; }
 
    void lazy_update(int node, int from, int to)
    {
        vmin[node] += lazy[node]; vmax[node] += lazy[node];
        if (from < to) 
        {
            lazy[2*node] += lazy[node];
            lazy[2*node+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(2*node, from, mid, L, R, add);
        update(2*node+1, mid + 1, to, L, R, add);
        vmin[node] = min(vmin[2*node], vmin[2*node+1]);
        vmax[node] = max(vmax[2*node], vmax[2*node+1]);
    }
 
    ll get(int node, int from, int to, int lb) 
    {
        lazy_update(node, from, to);
        if (from == to) return vmin[node];
        int mid = (from + to) / 2;
        if (vmax[2*node+1] + lazy[2*node+1] >= lb)
            return get(2*node+1, mid + 1, to, lb);
        return min( vmin[2*node+1] + lazy[2*node+1], get(2*node, from, mid, lb) );
    }
 
    void add_range(int L, int R, int add) 
    {
        update(1, 0, n - 1, L, R, add);
    }
 
    ll min_suffix(int lb) 
    {
        if (vmax[1] < lb) return -INF;
        return min(0LL, get(1, 0, n - 1, lb));
    }
} T;
 
vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) 
{
    int n = C.size(); int q = L.size();
    vector<int> A(n);
    
    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(q+1);
    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 l = 1, r = C[i] + 1;
        while (l <= r) 
        {
            int mid = (l + r) / 2;
            ll smin = T.min_suffix(mid);
            if (-smin + mid > C[i]) r = mid - 1;
            else l = mid + 1;
        }
        final_A[i] = r;
    }
 
    return final_A;
}

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23676 KB Output is correct
2 Correct 12 ms 23756 KB Output is correct
3 Correct 14 ms 23756 KB Output is correct
4 Correct 14 ms 23756 KB Output is correct
5 Correct 17 ms 24012 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1100 ms 48228 KB Output is correct
2 Correct 1170 ms 48204 KB Output is correct
3 Correct 1131 ms 48284 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23836 KB Output is correct
2 Correct 366 ms 31520 KB Output is correct
3 Correct 528 ms 36548 KB Output is correct
4 Correct 1393 ms 48196 KB Output is correct
5 Correct 1323 ms 48192 KB Output is correct
6 Correct 1330 ms 48192 KB Output is correct
7 Correct 755 ms 48324 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23756 KB Output is correct
2 Correct 13 ms 23852 KB Output is correct
3 Correct 150 ms 30352 KB Output is correct
4 Correct 272 ms 36372 KB Output is correct
5 Correct 548 ms 42800 KB Output is correct
6 Correct 592 ms 42812 KB Output is correct
7 Correct 698 ms 42800 KB Output is correct
8 Correct 543 ms 42812 KB Output is correct
9 Correct 1084 ms 42808 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23676 KB Output is correct
2 Correct 12 ms 23756 KB Output is correct
3 Correct 14 ms 23756 KB Output is correct
4 Correct 14 ms 23756 KB Output is correct
5 Correct 17 ms 24012 KB Output is correct
6 Correct 1100 ms 48228 KB Output is correct
7 Correct 1170 ms 48204 KB Output is correct
8 Correct 1131 ms 48284 KB Output is correct
9 Correct 13 ms 23836 KB Output is correct
10 Correct 366 ms 31520 KB Output is correct
11 Correct 528 ms 36548 KB Output is correct
12 Correct 1393 ms 48196 KB Output is correct
13 Correct 1323 ms 48192 KB Output is correct
14 Correct 1330 ms 48192 KB Output is correct
15 Correct 755 ms 48324 KB Output is correct
16 Correct 12 ms 23756 KB Output is correct
17 Correct 13 ms 23852 KB Output is correct
18 Correct 150 ms 30352 KB Output is correct
19 Correct 272 ms 36372 KB Output is correct
20 Correct 548 ms 42800 KB Output is correct
21 Correct 592 ms 42812 KB Output is correct
22 Correct 698 ms 42800 KB Output is correct
23 Correct 543 ms 42812 KB Output is correct
24 Correct 1084 ms 42808 KB Output is correct
25 Correct 12 ms 23756 KB Output is correct
26 Correct 227 ms 36372 KB Output is correct
27 Correct 362 ms 31432 KB Output is correct
28 Correct 916 ms 48196 KB Output is correct
29 Correct 1010 ms 48196 KB Output is correct
30 Correct 991 ms 48196 KB Output is correct
31 Correct 1040 ms 48196 KB Output is correct
32 Correct 1069 ms 48280 KB Output is correct