oj.uz

Submission #897123

# Submission time Handle Problem Language Result Execution time Memory
897123 2024-01-02T15:05:49 Z TahirAliyev Distributing Candies (IOI21_candies) C++17
29 / 100
 923 ms 42432 KB 
#include "candies.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll, ll>
#define oo 1e16

using namespace std;

int n, q;
const int MAX = 2e5 + 5;
pii tree[4 * MAX];
ll lazy[4 * MAX];
int z = 1;

void relax(int node, int l, int r){
    if(!lazy[node]) return;
    tree[node].first += lazy[node];
    tree[node].second += lazy[node];
    if(l == r){
        lazy[node] = 0;
        return;
    }
    lazy[2 * node] += lazy[node];
    lazy[2 * node + 1] += lazy[node];
    lazy[node] = 0;
}

pii comb(pii a, pii b){
    return {min(a.first, b.first), max(a.second, b.second)};
}

void update(int node, int l, int r, int ul, int ur, int v){
    relax(node, l, r);
    if(ur < l || r < ul){
        return;
    }
    if(ul <= l && r <= ur){
        lazy[node] += v;
        relax(node, l, r);
        return;
    }
    int mid = (l + r) / 2;
    update(2 * node, l, mid, ul, ur, v);
    update(2 * node + 1, mid + 1, r, ul, ur, v);
    tree[node] = comb(tree[2 * node], tree[2 * node + 1]);
}

pii ask(int node, int l, int r, int ql, int qr){
    if(qr < l || r < ql) return {oo, -oo};
    relax(node, l, r);
    if(ql <= l && r <= qr) return tree[node];
    int mid = (l + r) / 2;
    return comb(ask(2 * node, l, mid, ql, qr), ask(2 * node + 1, mid + 1, r, ql, qr));
}

vector<int> distribute_candies(vector<int> c, vector<int> l,
                               vector<int> r, vector<int> v) {

    n = c.size(), q = l.size();
    l.insert(l.begin(), 0);
    r.insert(r.begin(), 0);
    v.insert(v.begin(), 0);
    c.insert(c.begin(), 0);
    
    vector<pii> E[MAX];
    
    for(int i = 0; i <= 4 * q; i++){
        tree[i] = {0, 0};
        lazy[i] = 0;
    }
    for(int i = 1; i <= q; i++){
        l[i]++;
        r[i]++;
        E[l[i]].push_back({i, 1});
        E[r[i]].push_back({i, 0});
    }
    vector<int> res;
    for(int i = 1; i <= n; i++){
        for(pii t : E[i]){
            if(t.second){
                update(1, 0, q, t.first, q, v[t.first]);
            }
        }
        int L = 0, R = q;
        int ans = -1;
        while(L <= R){
            int mid = (L + R) / 2;
            pii a = ask(1, 0, q, mid, q);
            if(a.second - a.first > c[i]){
                L = mid + 1;
                ans = mid;
            }
            else{
                R = mid - 1;
            }
        }
        ll lst = ask(1, 0, q, q, q).first;
        if(ans == -1){
            ll mn = ask(1, 0, q, 0, q).first;
            res.push_back(lst - mn);
            continue;
        }
        pii a = ask(1, 0, q, ans, q);
        ll frs = ask(1, 0, q, ans, ans).first;
        ll bottom =  0;
        if(a.first == frs){
            bottom = a.second - c[i];
        }
        else{
            bottom = a.first;
        }
        res.push_back(lst - bottom);
        for(pii t : E[i]){
            if(!t.second){
                update(1, 0, q, t.first, q, -v[t.first]);
            }
        }
    }
    z++;
    return res;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7004 KB Output is correct
2 Correct 3 ms 7004 KB Output is correct
3 Incorrect 4 ms 9480 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 923 ms 42432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7004 KB Output is correct
2 Incorrect 222 ms 37468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7004 KB Output is correct
2 Correct 3 ms 7004 KB Output is correct
3 Correct 146 ms 38436 KB Output is correct
4 Correct 262 ms 12896 KB Output is correct
5 Correct 741 ms 39628 KB Output is correct
6 Correct 735 ms 38832 KB Output is correct
7 Correct 724 ms 39332 KB Output is correct
8 Correct 754 ms 40124 KB Output is correct
9 Correct 830 ms 38332 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7004 KB Output is correct
2 Correct 3 ms 7004 KB Output is correct
3 Incorrect 4 ms 9480 KB Output isn't correct
4 Halted 0 ms 0 KB -