oj.uz

Submission #751485

# Submission time Handle Problem Language Result Execution time Memory
751485 2023-05-31T16:03:03 Z Ronin13 Distributing Candies (IOI21_candies) C++17
100 / 100
 1075 ms 50840 KB 
#include "candies.h"
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define epb emplace_back
#define f first
#define s second
#define pii pair<int, int>
#define pll pair<ll,ll>
#include <vector>

/*
3
10 15 13
2
0 2 20
0 1 -11
*/

using namespace std;
const int nmax = 200001;
struct node{
    ll sum, mn, mx;
    int mni, mxi;
    node(){
        sum = 0;
        mn = 1e18;
        mx = -1e18;
    }
}t[4 * nmax];

node merg(node a, node b){
    node c;
    c.sum = a.sum + b.sum;
    if(a.mn < a.sum + b.mn){
        c.mn = a.mn, c.mni = a.mni;
    }
    else c.mn = a.sum + b.mn, c.mni = b.mni;
    if(a.mx > a.sum + b.mx){
        c.mx = a.mx, c.mxi = a.mxi;
    }
    else c.mx = a.sum + b.mx, c.mxi = b.mxi;
    return c;
}


node get(int v, int l, int r, int st, int fin){
    if(l > fin || r < st){
        return {};
    }
    if(l >= st && r <= fin){
        return t[v];
    }
    int m = (l + r) / 2;
    return merg(get(2 * v ,l, m, st, fin),
                get(2 * v + 1, m + 1, r, st, fin));
}

void update(int v, int l, int r, int pos, ll val){
    if(l > pos || r < pos)
        return;
    if(l == r){
        t[v].mn = t[v].mx = t[v].sum = val;
        t[v].mni = t[v].mxi = l;
        return;
    }
    int m = (l + r) / 2;
    update(2 * v, l, m, pos, val);
    update(2 * v + 1, m + 1, r, pos, val);
    t[v] = merg(t[2 * v], t[2 * v + 1]);
}

ll getsum(int v, int l, int r, int st, int fin){
    if(l > fin || r < st)
        return 0;
    if(l >= st && r <= fin)
        return t[v].sum;
    int m = (l + r) / 2;
    return getsum(2 * v, l, m, st, fin) + getsum(2 * v + 1, m + 1, r, st, fin);
}

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int n = c.size();
    vector <int> ans(n);
    int m = l.size();
    update(1, 1, m + 2, 1, 1e18);
    update(1, 1, m + 2, 2, -1e18);
    vector <vector <pii> > in(n + 1);
    for(int i = 0; i < m; i++){
        in[l[i]].pb({v[i], i + 3});
        in[r[i] + 1].pb({0, i + 3});
    }
    for(int i = 0; i < n; i++){
        for(auto to : in[i]){
            update(1, 1, m + 2, to.s, to.f);
        }
        int l = 0, r = m + 3;
        while(l + 1 < r){
            int mid = (l + r) / 2;
            node x = get(1, 1, m + 2, mid, m + 2);
            if(x.mx - x.mn >= c[i]) l = mid;
            else r = mid;
        }
        //cout << l << "\n";
        node x = get(1, 1, m + 2, l, m + 2);
        if(x.mni < x.mxi){
            ans[i] = c[i] - getsum(1, 1, m + 2, 1, l - 1) - x.mx + t[1].sum;
        }
        else ans[i] = t[1].sum - getsum(1, 1, m + 2, 1, l - 1) - x.mn;
    }
    return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25300 KB Output is correct
2 Correct 11 ms 25300 KB Output is correct
3 Correct 13 ms 25360 KB Output is correct
4 Correct 12 ms 25428 KB Output is correct
5 Correct 17 ms 25532 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 981 ms 48988 KB Output is correct
2 Correct 996 ms 48220 KB Output is correct
3 Correct 1008 ms 48048 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25300 KB Output is correct
2 Correct 234 ms 37588 KB Output is correct
3 Correct 333 ms 34760 KB Output is correct
4 Correct 1075 ms 50064 KB Output is correct
5 Correct 978 ms 50488 KB Output is correct
6 Correct 952 ms 50840 KB Output is correct
7 Correct 880 ms 50176 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 25352 KB Output is correct
2 Correct 10 ms 25352 KB Output is correct
3 Correct 110 ms 36112 KB Output is correct
4 Correct 289 ms 33700 KB Output is correct
5 Correct 751 ms 43900 KB Output is correct
6 Correct 736 ms 44720 KB Output is correct
7 Correct 730 ms 45356 KB Output is correct
8 Correct 771 ms 43768 KB Output is correct
9 Correct 888 ms 45304 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25300 KB Output is correct
2 Correct 11 ms 25300 KB Output is correct
3 Correct 13 ms 25360 KB Output is correct
4 Correct 12 ms 25428 KB Output is correct
5 Correct 17 ms 25532 KB Output is correct
6 Correct 981 ms 48988 KB Output is correct
7 Correct 996 ms 48220 KB Output is correct
8 Correct 1008 ms 48048 KB Output is correct
9 Correct 11 ms 25300 KB Output is correct
10 Correct 234 ms 37588 KB Output is correct
11 Correct 333 ms 34760 KB Output is correct
12 Correct 1075 ms 50064 KB Output is correct
13 Correct 978 ms 50488 KB Output is correct
14 Correct 952 ms 50840 KB Output is correct
15 Correct 880 ms 50176 KB Output is correct
16 Correct 10 ms 25352 KB Output is correct
17 Correct 10 ms 25352 KB Output is correct
18 Correct 110 ms 36112 KB Output is correct
19 Correct 289 ms 33700 KB Output is correct
20 Correct 751 ms 43900 KB Output is correct
21 Correct 736 ms 44720 KB Output is correct
22 Correct 730 ms 45356 KB Output is correct
23 Correct 771 ms 43768 KB Output is correct
24 Correct 888 ms 45304 KB Output is correct
25 Correct 11 ms 25344 KB Output is correct
26 Correct 302 ms 33740 KB Output is correct
27 Correct 243 ms 37204 KB Output is correct
28 Correct 1004 ms 48708 KB Output is correct
29 Correct 980 ms 49080 KB Output is correct
30 Correct 974 ms 49216 KB Output is correct
31 Correct 926 ms 49472 KB Output is correct
32 Correct 950 ms 49740 KB Output is correct