oj.uz

Submission #435428

# Submission time Handle Problem Language Result Execution time Memory
435428 2021-06-23T10:12:34 Z prvocislo Distributing Candies (IOI21_candies) C++17
100 / 100
 509 ms 34164 KB 
#include "candies.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int maxn = 1 << 18;
struct node 
{
    ll pfmin, pfmax, sum;
    bool up;
    void init(int val)
    {
        up = (val >= 0);
        pfmin = min(0, val), pfmax = max(0, val), sum = val;
    }
    void merge(node a, node b)
    {
        up = a.up;
        pfmin = min(a.pfmin, a.sum + b.pfmin);
        pfmax = max(a.pfmax, a.sum + b.pfmax);
        sum = a.sum + b.sum;
    }
};
vector<node> st(2*maxn);
void update(int i, int val)
{
    st[i += maxn].init(val);
    for (i = (i >> 1); i > 0; i >>= 1) st[i].merge(st[i<<1], st[(i<<1)|1]);
}
vector<int> distribute_candies(vector<int> c, vector<int> l,
                               vector<int> r, vector<int> v) {
    int n = c.size(), q = l.size();
    vector<int> ans(n);
    update(0, -*max_element(c.begin(), c.end()));
    vector<vector<int> > u(n+1);
    for (int i = 0; i < q; i++)
    {
        u[l[i]].push_back(i);
        u[r[i]+1].push_back(i);
    }
    for (int i = 0; i < n; i++)
    {
        for (int id : u[i]) 
        {
            if (l[id] == i) update(id+1, v[id]);
            else update(id+1, 0);
        }
        node suf; suf.init(0);
        int vr = 1;
        while (vr < maxn) 
        {
            vr = (vr << 1) | 1; // pravy syn
            node nw; nw.merge(st[vr], suf);
            if (nw.pfmax - nw.pfmin < c[i]) // posunieme sa o krok dolava
                suf = nw, vr--;
        }
        suf.merge(st[vr], suf); // urobime to trosku vacsie ako c[i]
        if (suf.up) // ideme nahor, vyska od hornej steny je ok
            ans[i] = (ll)c[i] - (suf.pfmax - suf.sum);
        else // ideme nadol, vyska od dolnej steny je ok
            ans[i] = suf.sum - suf.pfmin;
    }
    return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16716 KB Output is correct
2 Correct 10 ms 16616 KB Output is correct
3 Correct 12 ms 16716 KB Output is correct
4 Correct 13 ms 16716 KB Output is correct
5 Correct 13 ms 16872 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 34048 KB Output is correct
2 Correct 491 ms 34052 KB Output is correct
3 Correct 479 ms 34048 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16760 KB Output is correct
2 Correct 232 ms 23748 KB Output is correct
3 Correct 105 ms 23900 KB Output is correct
4 Correct 406 ms 34052 KB Output is correct
5 Correct 509 ms 33996 KB Output is correct
6 Correct 460 ms 33988 KB Output is correct
7 Correct 451 ms 34036 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16716 KB Output is correct
2 Correct 12 ms 16664 KB Output is correct
3 Correct 115 ms 23224 KB Output is correct
4 Correct 106 ms 23832 KB Output is correct
5 Correct 168 ms 30136 KB Output is correct
6 Correct 177 ms 30156 KB Output is correct
7 Correct 209 ms 30136 KB Output is correct
8 Correct 193 ms 30284 KB Output is correct
9 Correct 176 ms 30200 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16716 KB Output is correct
2 Correct 10 ms 16616 KB Output is correct
3 Correct 12 ms 16716 KB Output is correct
4 Correct 13 ms 16716 KB Output is correct
5 Correct 13 ms 16872 KB Output is correct
6 Correct 459 ms 34048 KB Output is correct
7 Correct 491 ms 34052 KB Output is correct
8 Correct 479 ms 34048 KB Output is correct
9 Correct 10 ms 16760 KB Output is correct
10 Correct 232 ms 23748 KB Output is correct
11 Correct 105 ms 23900 KB Output is correct
12 Correct 406 ms 34052 KB Output is correct
13 Correct 509 ms 33996 KB Output is correct
14 Correct 460 ms 33988 KB Output is correct
15 Correct 451 ms 34036 KB Output is correct
16 Correct 10 ms 16716 KB Output is correct
17 Correct 12 ms 16664 KB Output is correct
18 Correct 115 ms 23224 KB Output is correct
19 Correct 106 ms 23832 KB Output is correct
20 Correct 168 ms 30136 KB Output is correct
21 Correct 177 ms 30156 KB Output is correct
22 Correct 209 ms 30136 KB Output is correct
23 Correct 193 ms 30284 KB Output is correct
24 Correct 176 ms 30200 KB Output is correct
25 Correct 12 ms 16668 KB Output is correct
26 Correct 85 ms 24004 KB Output is correct
27 Correct 223 ms 23752 KB Output is correct
28 Correct 407 ms 34044 KB Output is correct
29 Correct 415 ms 33916 KB Output is correct
30 Correct 426 ms 33988 KB Output is correct
31 Correct 405 ms 33996 KB Output is correct
32 Correct 437 ms 34164 KB Output is correct