oj.uz

Submission #436818

# Submission time Handle Problem Language Result Execution time Memory
436818 2021-06-25T02:00:45 Z edenooo Distributing Candies (IOI21_candies) C++17
29 / 100
 468 ms 63644 KB 
#include "candies.h"

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

#define INF 1234567890
#define ll long long

ll last = 0;
pair<ll, ll> seg[530000];
ll lazy[530000];
pair<ll, ll> Merge(pair<ll, ll> l, pair<ll, ll> r)
{
    return {min(l.first,r.first), max(l.second, r.second)};
}
void Propagate(int n, int l, int r) // add
{
    if (lazy[n])
    {
        if (l != r)
        {
            lazy[n<<1] += lazy[n];
            lazy[n<<1|1] += lazy[n];
        }
        seg[n].first += lazy[n];
        seg[n].second += lazy[n];
        lazy[n] = 0;
    }
}
pair<ll, ll> Update(int L, int R, ll val, int n, int l, int r)
{
    Propagate(n, l, r);
    if (r < L || R < l) return seg[n];
    if (L <= l && r <= R)
    {
        lazy[n] += val; // add
        Propagate(n, l, r);
        return seg[n];
    }
    int mid = l+r>>1;
    return seg[n] = Merge(Update(L, R, val, n<<1, l, mid), Update(L, R, val, n<<1|1, mid+1, r));
}
ll Kth(ll C, ll mn, ll mx, int n, int l, int r) // 1 <= k <= propagated_seg[1]
{
    if (l == r)
    {
        mn = min(mn, seg[n].first);
        mx = max(mx, seg[n].second);
        assert(mx - mn >= C);
        if (mn == seg[n].first) return C - (mx - last);
        else return last - mn;
    }
    int mid = l+r>>1;
    Propagate(n, l, r);
    Propagate(n<<1|1, mid+1, r);
    ll next_mn = min(mn, seg[n<<1|1].first), next_mx = max(mx, seg[n<<1|1].second);
    if (next_mx - next_mn >= C) return Kth(C, mn, mx, n<<1|1, mid+1, r);
    return Kth(C, next_mn, next_mx, n<<1, l, mid);
}

int N, Q;
vector<pair<int, int> > D[200201];

vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
    N = C.size(); Q = L.size();
    // INF와 0을 맨 앞에 끼워넣어서 예외 처리
    D[0].push_back({0, INF});
    D[0].push_back({1, -INF});
    for(int i=0; i<Q; i++)
    {
        D[L[i]].push_back({i+2, V[i]});
        D[R[i]+1].push_back({i+2, -V[i]});
    }

    vector<int> res(N);
    for(int i=0; i<N; i++)
    {
        for(auto [idx,val] : D[i])
        {
            last += val;
            Update(idx, Q+1, val, 1, 0, Q+1); //
        }
        res[i] = Kth(C[i], (ll)1e18, (ll)-1e18, 1, 0, Q+1);
    }
    return res;
}

// int main() {}

Compilation message

candies.cpp: In function 'std::pair<long long int, long long int> Update(int, int, long long int, int, int, int)':
candies.cpp:40:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     int mid = l+r>>1;
      |               ~^~
candies.cpp: In function 'long long int Kth(long long int, long long int, long long int, int, int, int)':
candies.cpp:53:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |     int mid = l+r>>1;
      |               ~^~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Runtime error 9 ms 9944 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 468 ms 63644 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 9932 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 156 ms 25192 KB Output is correct
4 Correct 104 ms 7564 KB Output is correct
5 Correct 236 ms 27428 KB Output is correct
6 Correct 246 ms 27432 KB Output is correct
7 Correct 248 ms 27392 KB Output is correct
8 Correct 232 ms 27524 KB Output is correct
9 Correct 284 ms 27428 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Runtime error 9 ms 9944 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -