제출 #446577

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
446577		blue	사탕 분배 (IOI21_candies)	C++17	100 / 100	1699 ms	64336 KiB

candies

#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 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33