oj.uz

Submission #443180

# Submission time Handle Problem Language Result Execution time Memory
443180 2021-07-10T04:20:07 Z blue Distributing Candies (IOI21_candies) C++17
0 / 100
 5000 ms 48856 KB 
#include "candies.h"
#include <vector>
#include <iostream>
using namespace std;
 
const long long INF = 3'000'000'000;
 
struct segtree //min, max, range add
{
    int l;
    int r;
 
    long long mn = 0;
    long long mx = 0;
    long long lp = 0;
 
    segtree* left = NULL;
    segtree* right = NULL;
 
    segtree()
    {
        ;
    }
 
    segtree(int L, int R)
    {
        l = L;
        r = R;
        if(l == r) return;
        int m = (l+r+10)/2 - 5;
        left = new segtree(l, m);
        right = new segtree(m+1, r);
    }
 
    long long rangemin(int L, int 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(int L, int 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(int L, int 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> c, vector<int> l, vector<int> r, vector<int> v)
{
    int N = c.size();
    int Q = l.size();
 
    vector<int> insertions[N], removals[N];
    for(int j = 0; j < Q; j++)
    {
        insertions[ l[j] ].push_back(j);
        removals[ r[j] ].push_back(j);
    }
 
    segtree S(-1, Q-1);
    long long curr_upd_sum = 0;
 
    vector<int> res(N);
 
    for(int i = 0; i < N; i++)
    {
        // cerr << "i = " << i << '\n';
        for(int o: insertions[i])
        {
            S.add(o, Q-1, +v[o]);
            curr_upd_sum += v[o];
        }
 
        // cerr << "segtree: ";
        // for(int j = 0; j < Q; j++) cerr << S.rangemin(j, j) << ' ';
        // cerr << '\n';
 
        long long lower_bound;
 
        long long MN = S.rangemin(0, Q-1), MX = S.rangemax(0, Q-1);
 
        if(0 <= MN && MX <= (long long)c[i])
        {
            lower_bound = 0;
        }
        else if(MN < 0 && MX - MN <= (long long)c[i])
        {
            lower_bound = MN;
        }
        else
        {
            int last_good = Q-1;
           // for(int bit = 19; bit >= 0; bit--)
            for(int bit = 0; bit >= 0; bit -= 0)
            {
                int new_good = last_good - (1 << bit);
                if(new_good < 0) break;
                if(S.rangemax(new_good, Q-1) - S.rangemin(new_good, Q-1) > (long long)c[i]) break;
                last_good = new_good;
            }
            if(S.rangemin(last_good-1, last_good-1) < S.rangemin(last_good, Q-1))
            {
                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 << ' ' << lower_bound << '\n';
 
        res[i] = curr_upd_sum - lower_bound;
 
        for(int o: removals[i])
        {
            S.add(o, Q-1, -v[o]);
            curr_upd_sum -= v[o];
        }
    }
 
    return res;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5072 ms 48856 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Execution timed out 5023 ms 32476 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1851 ms 31740 KB Output is correct
4 Correct 1114 ms 12460 KB Output is correct
5 Execution timed out 5044 ms 43292 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

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