제출 #437093

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

candies

#include <iostream>
#include <cstdio>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <ctime>
#include <vector>
#include <set>
#include <iterator>
#include <map>
#include <functional>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <queue>
#include <deque>
#include <time.h>
#include <bitset>

#define ll long long
#define ld long double
#define y1 abc
#define endl '\n'
#define fi first
#define se second
#define m_p make_pair
#define pb push_back
#define pf push_front
#define MAXLL 9000000000000000000LL
#define MAXINT 2000000000
#define MINLL -9000000000000000000LL
#define MININT -2000000000
#define stoi aaaaavasd
#define pll pair < ll, ll >
#define pii pair < int, int >

using namespace std;
using namespace __gnu_pbds;

typedef tree< int, null_type, less< int >, rb_tree_tag, tree_order_statistics_node_update > ordered_set;

const ld pi = acos(-1);
const ll md = 1e9 + 7;
clock_t start_time = clock();

ll n, q, i, j;

vector < int > ans;

vector < pll > tg[200501];

struct segtree
{
    struct node
    {
        ll mn = 0, mx = 0, p = 0;
    };

    node t[800501];
    ll sz = 1, lst = 0;

    void build_segtree()
    {
        while (sz < q + 3) sz *= 2;
        sz--;
    }

    void propagate(ll nom, ll l, ll r)
    {
        if (t[nom].p == 0 || l == r) return;

        t[nom * 2].mn += t[nom].p;
        t[nom * 2].mx += t[nom].p;
        t[nom * 2].p += t[nom].p;
        t[nom * 2 + 1].mn += t[nom].p;
        t[nom * 2 + 1].mx += t[nom].p;
        t[nom * 2 + 1].p += t[nom].p;
        t[nom].p = 0;
    }

    void update(ll nom, ll l, ll r, ll cl, ll cr, ll x)
    {
        propagate(nom, l, r);

        if (l > cr || r < cl) return;

        if (l >= cl && r <= cr){
            t[nom].p += x;
            t[nom].mn += x;
            t[nom].mx += x;
            return;
        }

        ll mid = (l + r) / 2;
        update(nom * 2, l, mid, cl, cr, x);
        update(nom * 2 + 1, mid + 1, r, cl, cr, x);
        t[nom].mn = min(t[nom * 2].mn, t[nom * 2 + 1].mn);
        t[nom].mx = max(t[nom * 2].mx, t[nom * 2 + 1].mx);
    }

    void update(ll l, ll r, ll x)
    {
        lst += x;
        update(1, 0, sz, l, r, x);
    }

    ll get_mx(ll nom, ll l, ll r, ll cl, ll cr)
    {
        propagate(nom, l, r);

        if (l > cr || r < cl) return MINLL;

        if (l >= cl && r <= cr) return t[nom].mx;

        ll mid = (l + r) / 2;
        return max(get_mx(nom * 2, l, mid, cl, cr), get_mx(nom * 2 + 1, mid + 1, r, cl, cr));
    }

    ll get_mn(ll nom, ll l, ll r, ll cl, ll cr)
    {
        propagate(nom, l, r);

        if (l > cr || r < cl) return MAXLL;

        if (l >= cl && r <= cr) return t[nom].mn;

        ll mid = (l + r) / 2;
        return min(get_mn(nom * 2, l, mid, cl, cr), get_mn(nom * 2 + 1, mid + 1, r, cl, cr));
    }

    ll get(ll c)
    {
        ll idx, mn, mx, l = 0, r = q + 2, mid;

        while (l <= r){
            mid = (l + r) / 2;
            ll cmx = get_mx(1, 0, sz, mid, q + 2), cmn = get_mn(1, 0, sz, mid, q + 2);

            if (cmx - cmn > c){
                l = mid + 1;
                idx = mid;
            }
            else{
                r = mid - 1;
            }
        }

        mn = get_mn(1, 0, sz, idx + 1, q + 2);
        mx = get_mx(1, 0, sz, idx + 1, q + 2);

        if (get_mx(1, 0, sz, idx, idx) < mx) return c - (mx - lst);
        else return lst - mn;
    }
};

segtree t;

vector < int > distribute_candies(vector < int > c, vector < int > l, vector < int > r, vector < int > v)
{
    n = c.size();
    q = l.size();
    n--;
    q--;

    for (i = 0; i <= q; i++){
        tg[l[i]].pb({i, v[i]});
        tg[r[i] + 1].pb({i, -v[i]});
    }

    t.build_segtree();
    t.update(0, q + 2, MAXINT);
    t.update(1, q + 2, MININT);

    ans.resize(n + 1);
    for (i = 0; i <= n; i++){
        for (pll x : tg[i]){
            t.update(x.fi + 2, q + 2, x.se);
        }

        ans[i] = t.get(c[i]);
    }

    return ans;
}

//void solve()
//{
//    vector < int > c, l, r, v;
//    ll n, q;
//    cin >> n;
//    c.resize(n);
//    for (i = 0; i < n; i++) cin >> c[i];
//    cin >> q;
//    l.resize(q);
//    r.resize(q);
//    v.resize(q);
//    for (i = 0; i < q; i++) cin >> l[i] >> r[i] >> v[i];
//    v = distribute_candies(c, l, r, v);
//    for (int x : v) cout << x << " ";
//    cout << endl;
//}
//
//int main()
//{
//    #ifdef LOCAL
//        freopen("input.txt", "r", stdin);
//        freopen("output.txt", "w", stdout);
//    #endif
//
//    ios::sync_with_stdio(0);
//    cin.tie(0);
//
//    ll q = 1;
////    cin >> q;
//
//    while (q--){
//        solve();
//    }
//
//    #ifdef LOCAL
//        cout << endl;
//        cout << "Time = " << (ld)(clock() - start_time) / CLOCKS_PER_SEC << endl;
//    #endif
//
//    return 0;
//}

컴파일 시 표준 에러 (stderr) 메시지

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:150:20: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  150 |         mn = get_mn(1, 0, sz, idx + 1, q + 2);
      |              ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
candies.cpp:135:12: note: 'idx' was declared here
  135 |         ll idx, mn, mx, l = 0, r = q + 2, mid;
      |            ^~~

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33