oj.uz

Submission #531847

# Submission time Handle Problem Language Result Execution time Memory
531847 2022-03-01T16:56:02 Z kazak Distributing Candies (IOI21_candies) C++17
100 / 100
 1251 ms 53316 KB 
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define forn(i, x, y) for(int i = (x); i < (y); i++)
 
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("unroll-loops")
 
#define int long long
#define double long double
 
const int maxn = 2e5 + 5, inf = 1e18;
 
struct node {
    int sum, mx, mn;
    node(): sum(0), mx(-0), mn(0) {}
    node(int x): sum(x), mx(max(0ll, x)), mn(min(0ll, x)) {}
} d[maxn * 4];
 
node merge(node a, node b) {
    node res;
    res.sum = a.sum + b.sum;
    res.mx = max(a.mx, b.mx + a.sum);
    res.mn = min(a.mn, b.mn + a.sum);
    return res;
}
 
void change(int v, int tl, int tr, int idx, int val) {
    if(tl == tr) {
        d[v] = node(val);
        return;
    }
    int tm = (tl + tr) / 2;
    if(idx <= tm) {
        change(2*v, tl, tm, idx, val);
    }
    else {
        change(2*v+1, tm+1, tr, idx, val);
    }
    d[v] = merge(d[2*v], d[2*v+1]);
}
 
node get(int v, int tl, int tr, int l, int r) {
    if(l > r) {
        return node(); /// check this
    }
    if(l == tl && r == tr) {
        return d[v];
    }
    int tm = (tl + tr) / 2;
    node x = get(2*v, tl, tm, l, min(r, tm));
    node y = get(2*v+1, tm+1, tr, max(l, tm+1), r);
    return merge(x, y);
}
 
void debug(int v, int tl, int tr) {
    if(tl == tr) {
        cout << d[v].sum << " ";
        return;
    }
    int tm = (tl + tr) / 2;
    debug(2*v, tl, tm);
    debug(2*v+1, tm+1, tr);
}
 
vector<signed> distribute_candies(vector<signed> C, vector<signed> L, vector<signed> R, vector<signed> V) {
    int n = C.size(), q = L.size();
    vector<int> c(n);
    forn(i, 0, n) {
        c[i] = C[i];
    }
    q += 3;
    vector<int> val(q);
    val[0] = inf;
    val[1] = -inf;
    val[q-1] = 0;
    vector<vector<int>> st(n), en(n);
    st[0].push_back(0);
    st[0].push_back(1);
    en[n-1].push_back(0);
    en[n-1].push_back(1);
    forn(i, 2, q-1) {
        int l, r, x;
        l = L[i-2];
        r = R[i-2];
        val[i] = V[i-2];
        st[l].push_back(i);
        en[r].push_back(i);
    }
 
    vector<signed> ans(n);
    forn(i, 0, n) {
        for(auto it : st[i]) {
            change(1, 0, q-1, it, val[it]);
        }
 
        //cout << i << ": \n";
        //debug(1, 0, q-1);
        //cout << "\n";
 
        int l = 0, r = q-1;
        while(l < r) {
            int mid = (l + r) / 2;
            node cur = get(1, 0, q-1, mid, q-1);
            if(cur.mx - cur.mn > c[i]) {
                l = mid + 1;
            }
            else {
                r = mid;
            }
        }
        node prev = get(1, 0, q-1, l, q-1);
        node nxt = get(1, 0, q-1, l-1, q-1);
        nxt.mn -= val[l-1];
        nxt.mx -= val[l-1];
        node total = get(1, 0, q-1, l, q-1);
        int real;
        if(prev.mx == nxt.mx) {
            real = c[i] - (prev.mx - total.sum);
        }
        else {
            real = total.sum - prev.mn;
        }
 
        ans[i] = real;
//        cout << real << " ";
 
        for(auto it : en[i]) {
            change(1, 0, q-1, it, 0);
        }
    }
    return ans;
}
 
//signed main()
//{
////    ios_base::sync_with_stdio(0);
////    cin.tie(0);
////    cout.tie(0);
//
//    vector<int> ans = distribute_candies({10, 15, 13}, {0, 0}, {2, 1}, {20, -11});
//    for(auto it : ans) {
//        cout << it << " ";
//    }
//
//    return 0;
//}
 
 
/*
 
1 7
3
0 0 -100
0 0 10
0 0 1
0 0 -5
0 0 1
0 0 -5
0 0 5
 
*/

Compilation message

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:83:19: warning: unused variable 'x' [-Wunused-variable]
   83 |         int l, r, x;
      |                   ^

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19072 KB Output is correct
2 Correct 10 ms 19020 KB Output is correct
3 Correct 10 ms 19224 KB Output is correct
4 Correct 11 ms 19148 KB Output is correct
5 Correct 14 ms 19332 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1186 ms 46604 KB Output is correct
2 Correct 1233 ms 50672 KB Output is correct
3 Correct 1226 ms 50492 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19148 KB Output is correct
2 Correct 201 ms 34040 KB Output is correct
3 Correct 383 ms 34692 KB Output is correct
4 Correct 1156 ms 52516 KB Output is correct
5 Correct 1146 ms 52912 KB Output is correct
6 Correct 1201 ms 53316 KB Output is correct
7 Correct 1125 ms 52676 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19020 KB Output is correct
2 Correct 12 ms 19072 KB Output is correct
3 Correct 124 ms 31384 KB Output is correct
4 Correct 390 ms 33832 KB Output is correct
5 Correct 1018 ms 45320 KB Output is correct
6 Correct 1010 ms 45996 KB Output is correct
7 Correct 1010 ms 46576 KB Output is correct
8 Correct 1012 ms 45216 KB Output is correct
9 Correct 967 ms 46692 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19072 KB Output is correct
2 Correct 10 ms 19020 KB Output is correct
3 Correct 10 ms 19224 KB Output is correct
4 Correct 11 ms 19148 KB Output is correct
5 Correct 14 ms 19332 KB Output is correct
6 Correct 1186 ms 46604 KB Output is correct
7 Correct 1233 ms 50672 KB Output is correct
8 Correct 1226 ms 50492 KB Output is correct
9 Correct 9 ms 19148 KB Output is correct
10 Correct 201 ms 34040 KB Output is correct
11 Correct 383 ms 34692 KB Output is correct
12 Correct 1156 ms 52516 KB Output is correct
13 Correct 1146 ms 52912 KB Output is correct
14 Correct 1201 ms 53316 KB Output is correct
15 Correct 1125 ms 52676 KB Output is correct
16 Correct 9 ms 19020 KB Output is correct
17 Correct 12 ms 19072 KB Output is correct
18 Correct 124 ms 31384 KB Output is correct
19 Correct 390 ms 33832 KB Output is correct
20 Correct 1018 ms 45320 KB Output is correct
21 Correct 1010 ms 45996 KB Output is correct
22 Correct 1010 ms 46576 KB Output is correct
23 Correct 1012 ms 45216 KB Output is correct
24 Correct 967 ms 46692 KB Output is correct
25 Correct 8 ms 19020 KB Output is correct
26 Correct 410 ms 33784 KB Output is correct
27 Correct 221 ms 33580 KB Output is correct
28 Correct 1248 ms 51148 KB Output is correct
29 Correct 1212 ms 51544 KB Output is correct
30 Correct 1215 ms 51732 KB Output is correct
31 Correct 1251 ms 51940 KB Output is correct
32 Correct 1194 ms 52136 KB Output is correct