oj.uz

Submission #1056103

# Submission time Handle Problem Language Result Execution time Memory
1056103 2024-08-13T07:46:43 Z onbert Distributing Candies (IOI21_candies) C++17
100 / 100
 1090 ms 56736 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node {
    pair<int,int> mn, mx;
};
const int maxn = 2e5 + 5, maxN = 8e5 + 5, INF = 1e18;
int n;
node seg[maxN];
int lazy[maxN];
void build(int id, int l, int r) {
    lazy[id] = 0;
    if (l==r) {
        seg[id] = {{0, l}, {0, l}};
        return;
    }
    int mid = (l+r)/2;
    build(id*2, l, mid); build(id*2+1, mid+1, r);
    seg[id].mn = min(seg[id*2].mn, seg[id*2+1].mn);
    seg[id].mx = max(seg[id*2].mx, seg[id*2+1].mx);
}
void push(int id) {
    seg[id].mn.first += lazy[id], seg[id].mx.first += lazy[id];
    if (id*2<maxN) lazy[id*2] += lazy[id];
    if (id*2+1<maxN) lazy[id*2+1] += lazy[id];
    lazy[id] = 0;
}
bool ck = false;
void update(int id, int l, int r, int findl, int findr, int val) {
    push(id);
    if (r<findl || findr<l) return;
    if (findl<=l && r<=findr) {
        if (ck) {
            seg[id].mx.first = val;
        } else {
            lazy[id] += val;
            push(id);
        }
        return;
    }
    int mid = (l+r)/2;
    update(id*2, l, mid, findl, findr, val); update(id*2+1, mid+1, r, findl, findr, val);
    seg[id].mn = min(seg[id*2].mn, seg[id*2+1].mn);
    seg[id].mx = max(seg[id*2].mx, seg[id*2+1].mx);
}
node qry(int id, int l, int r, int findl, int findr) {
    push(id);
    if (r<findl || findr<l) return {{INF, INF}, {-INF, -INF}};
    if (findl<=l && r<=findr) return seg[id];
    int mid = (l+r)/2;
    node lhs = qry(id*2, l, mid, findl, findr);
    node rhs = qry(id*2+1, mid+1, r, findl, findr);
    return {min(lhs.mn, rhs.mn), max(lhs.mx, rhs.mx)};
}

vector<int32_t> distribute_candies(vector<int32_t> a, vector<int32_t> L,
                                    vector<int32_t> R, vector<int32_t> V) {
    n = a.size();
    int q = L.size();
    vector<pair<int,int>> add[n], del[n];
    for (int i=0;i<q;i++) {
        add[L[i]].push_back({i+1, V[i]});
        del[R[i]].push_back({i+1, V[i]});
    }
    build(1, 0, q);
    vector<int32_t> ans(n);
    for (int i=0;i<n;i++) {
        for (auto [pos, val]:add[i]) update(1, 0, q, pos, q, val);
        ck = true;
        update(1, 0, q, 0, 0, a[i]);
        ck = false;
        int l = 0, r = q;
        while (l<r) {
            int mid = (l+r+1)/2;
            node cur = qry(1, 0, q, mid, q);
            if (cur.mx.first - cur.mn.first > a[i]) l = mid;
            else r = mid-1;
        }
        int shift = 0;
        node cur = qry(1, 0, q, l, q);
        if (cur.mx.first - cur.mn.first > a[i]) {
            if (cur.mn.second > cur.mx.second) shift = -cur.mn.first;
            else shift = -(cur.mx.first - a[i]);
        }
        // cout << cur.mn.first << " " << cur.mn.second << endl;
        // cout << cur.mx.first << " " << cur.mx.second << endl;
        ans[i] = qry(1, 0, q, q, q).mx.first + shift;
        for (auto [pos, val]:del[i]) update(1, 0, q, pos, q, -val);
    }
    return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 4 ms 4884 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 910 ms 49932 KB Output is correct
2 Correct 959 ms 54100 KB Output is correct
3 Correct 964 ms 53956 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 167 ms 38648 KB Output is correct
3 Correct 358 ms 17596 KB Output is correct
4 Correct 1090 ms 50044 KB Output is correct
5 Correct 973 ms 56148 KB Output is correct
6 Correct 880 ms 56736 KB Output is correct
7 Correct 848 ms 55892 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 123 ms 35084 KB Output is correct
4 Correct 268 ms 16472 KB Output is correct
5 Correct 851 ms 46636 KB Output is correct
6 Correct 866 ms 46180 KB Output is correct
7 Correct 836 ms 46624 KB Output is correct
8 Correct 894 ms 45884 KB Output is correct
9 Correct 992 ms 46232 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 4 ms 4884 KB Output is correct
6 Correct 910 ms 49932 KB Output is correct
7 Correct 959 ms 54100 KB Output is correct
8 Correct 964 ms 53956 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 167 ms 38648 KB Output is correct
11 Correct 358 ms 17596 KB Output is correct
12 Correct 1090 ms 50044 KB Output is correct
13 Correct 973 ms 56148 KB Output is correct
14 Correct 880 ms 56736 KB Output is correct
15 Correct 848 ms 55892 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 0 ms 2396 KB Output is correct
18 Correct 123 ms 35084 KB Output is correct
19 Correct 268 ms 16472 KB Output is correct
20 Correct 851 ms 46636 KB Output is correct
21 Correct 866 ms 46180 KB Output is correct
22 Correct 836 ms 46624 KB Output is correct
23 Correct 894 ms 45884 KB Output is correct
24 Correct 992 ms 46232 KB Output is correct
25 Correct 1 ms 2392 KB Output is correct
26 Correct 276 ms 17736 KB Output is correct
27 Correct 166 ms 41220 KB Output is correct
28 Correct 988 ms 54588 KB Output is correct
29 Correct 940 ms 54868 KB Output is correct
30 Correct 901 ms 55028 KB Output is correct
31 Correct 901 ms 55120 KB Output is correct
32 Correct 886 ms 55380 KB Output is correct