oj.uz

Submission #446577

# Submission time Handle Problem Language Result Execution time Memory
446577 2021-07-22T13:23:16 Z blue Distributing Candies (IOI21_candies) C++17
100 / 100
 1699 ms 64336 KB 
#include "candies.h"
#include <vector>
#include <iostream>
using namespace std;
 
const long long INF = 1'000'000'000'000'000'000;
 
struct segtree //min, max, range add
{
    long long l;
    long long r;
 
    long long mn = 0;
    long long mx = 0;
    long long lp = 0;
 
    segtree* left = NULL;
    segtree* right = NULL;
 
    segtree()
    {
        ;
    }
 
    segtree(long long L, long long R)
    {
        l = L;
        r = R;
        if(l == r) return;
        long long m = (l+r+10)/2 - 5;
        left = new segtree(l, m);
        right = new segtree(m+1, r);
    }
 
    long long rangemin(long long L, long long R)
    {
        if(R < l || r < L) return INF;
        else if(L <= l && r <= R) return mn;
        else return lp + min(left->rangemin(L, R), right->rangemin(L, R));
    }
 
    long long rangemax(long long L, long long R)
    {
        if(R < l || r < L) return -INF;
        else if(L <= l && r <= R) return mx;
        else return lp + max(left->rangemax(L, R), right->rangemax(L, R));
    }
 
    void add(long long L, long long R, long long V)
    {
        if(R < l || r < L) return;
 
        // cerr << "adding to " << l << ' ' << r << ": " << L << ' ' << R << ' ' << V << '\n';
 
        if(L <= l && r <= R)
        {
            mn += V;
            mx += V;
            lp += V;
        }
        else
        {
            left->add(L, R, V);
            right->add(L, R, V);
            mn = lp + min(left->mn, right->mn);
            mx = lp + max(left->mx, right->mx);
        }
    }
};
 
vector<int> distribute_candies(vector<int> c1, vector<int> l1, vector<int> r1, vector<int> v1)
{
 
    long long N = c1.size();
    long long Q = l1.size();
 
 
    vector<long long> c(N);
    vector<long long> l(Q), r(Q), v(Q);
 
    for(int i = 0; i < N; i++) c[i] = c1[i];
    for(int j = 0; j < Q; j++)
    {
        l[j] = l1[j];
        r[j] = r1[j];
        v[j] = v1[j];
    }
 
    segtree S(-3, Q-1);
 
    S.add(-3, -3, -INF);
    S.add(-2, -2, +INF);
 
    vector<long long> insertions[N], removals[N];
    for(long long i = 0; i < Q; i++)
    {
        insertions[ l[i] ].push_back(i);
        removals[ r[i] ].push_back(i);
    }
 
    vector<long long> res(N, 0);
    long long curr_upd_sum = 0;
 
    // for(long long j = -1; j <= Q-1; j++) cerr << S.rangemax(j, j) << ' ';
    // cerr << '\n';
 
    for(long long i = 0; i < N; i++)
    {
        // cerr << "i = " << i << '\n';
        for(long long o: insertions[i])
        {
            // cerr << "inserting " << o << ": " << l[o] << ' ' << r[o] << ' ' << v[o] << '\n';
            S.add(o, Q-1, +v[o]);
            curr_upd_sum += v[o];
 
            // cerr << "segment tree: ";
            // for(long long j = -1; j <= Q-1; j++) cerr << S.rangemax(j, j) << ' ';
            // cerr << '\n';
        }
 
        long long lower_bound = 0;
 
        // cerr << S.rangemax(-1, Q-1) << ' ' << S.rangemin(-1, Q-1) << '\n';
 
 
        long long last_good = Q-1;
        // for(last_good = Q-1; last_good >= 0; last_good--)
        // {
        //     if(S.rangemax(last_good-1, Q-1) - S.rangemin(last_good-1, Q-1) > (long long)c[i])
        //         break;
        // }
        // cerr << "last_good = " << last_good << '\n';
 
        for(long long bit = 19; bit >= 0; bit--)
        {
            long long new_good = last_good - (1 << bit);
            if(new_good < -1) continue;
            if(S.rangemax(new_good, Q-1) - S.rangemin(new_good, Q-1) <= (long long)c[i])
                last_good = new_good;
        }
        // cerr << "last_good = " << last_good << '\n';
 
        if(0 <= S.rangemin(0, Q-1) && S.rangemax(0, Q-1) <= c[i])
            lower_bound = 0;
        else if(S.rangemax(last_good-1, last_good-1) < S.rangemax(last_good, last_good))
            lower_bound = S.rangemax(last_good, Q-1) - (long long)c[i];
        else
            lower_bound = S.rangemin(last_good, Q-1);
 
        // cerr << "curr_upd_sum = " << curr_upd_sum << ", lower_bound = " << lower_bound << '\n';
 
        res[i] = (curr_upd_sum - lower_bound);
 
        for(long long o: removals[i])
        {
            // cerr << "removing " << o << '\n';
            S.add(o, Q-1, -v[o]);
            curr_upd_sum -= v[o];
        }
 
        // cerr << "\n\n";
    }
 
    vector<int> res1(N);
    for(int i = 0; i < N; i++) res1[i] = res[i];
 
    return res1;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 716 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 6 ms 844 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1571 ms 62384 KB Output is correct
2 Correct 1653 ms 61644 KB Output is correct
3 Correct 1699 ms 61448 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 409 ms 43436 KB Output is correct
3 Correct 355 ms 17800 KB Output is correct
4 Correct 1359 ms 63452 KB Output is correct
5 Correct 1558 ms 63848 KB Output is correct
6 Correct 1389 ms 64336 KB Output is correct
7 Correct 1376 ms 63580 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 162 ms 40760 KB Output is correct
4 Correct 324 ms 16744 KB Output is correct
5 Correct 1018 ms 56220 KB Output is correct
6 Correct 1022 ms 56856 KB Output is correct
7 Correct 981 ms 57468 KB Output is correct
8 Correct 923 ms 56112 KB Output is correct
9 Correct 833 ms 57588 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 716 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 6 ms 844 KB Output is correct
6 Correct 1571 ms 62384 KB Output is correct
7 Correct 1653 ms 61644 KB Output is correct
8 Correct 1699 ms 61448 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 409 ms 43436 KB Output is correct
11 Correct 355 ms 17800 KB Output is correct
12 Correct 1359 ms 63452 KB Output is correct
13 Correct 1558 ms 63848 KB Output is correct
14 Correct 1389 ms 64336 KB Output is correct
15 Correct 1376 ms 63580 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 162 ms 40760 KB Output is correct
19 Correct 324 ms 16744 KB Output is correct
20 Correct 1018 ms 56220 KB Output is correct
21 Correct 1022 ms 56856 KB Output is correct
22 Correct 981 ms 57468 KB Output is correct
23 Correct 923 ms 56112 KB Output is correct
24 Correct 833 ms 57588 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 312 ms 16936 KB Output is correct
27 Correct 385 ms 43048 KB Output is correct
28 Correct 1261 ms 62088 KB Output is correct
29 Correct 1374 ms 62488 KB Output is correct
30 Correct 1423 ms 62756 KB Output is correct
31 Correct 1411 ms 62868 KB Output is correct
32 Correct 1370 ms 63168 KB Output is correct