oj.uz

답안 #437093

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
437093 2021-06-25T19:02:39 Z p3rfect 사탕 분배 (IOI21_candies) C++17
100 / 100
 2999 ms 38712 KB 
#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;
//}

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: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.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 7 ms 5196 KB Output is correct
4 Correct 6 ms 5196 KB Output is correct
5 Correct 14 ms 5196 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2743 ms 32704 KB Output is correct
2 Correct 2999 ms 32720 KB Output is correct
3 Correct 2933 ms 32696 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 488 ms 28004 KB Output is correct
3 Correct 975 ms 9544 KB Output is correct
4 Correct 2917 ms 32720 KB Output is correct
5 Correct 2824 ms 32720 KB Output is correct
6 Correct 2633 ms 32720 KB Output is correct
7 Correct 2508 ms 38712 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 238 ms 25536 KB Output is correct
4 Correct 716 ms 8468 KB Output is correct
5 Correct 2247 ms 28580 KB Output is correct
6 Correct 2166 ms 32724 KB Output is correct
7 Correct 1885 ms 33316 KB Output is correct
8 Correct 2178 ms 32028 KB Output is correct
9 Correct 2402 ms 33428 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 7 ms 5196 KB Output is correct
4 Correct 6 ms 5196 KB Output is correct
5 Correct 14 ms 5196 KB Output is correct
6 Correct 2743 ms 32704 KB Output is correct
7 Correct 2999 ms 32720 KB Output is correct
8 Correct 2933 ms 32696 KB Output is correct
9 Correct 4 ms 4940 KB Output is correct
10 Correct 488 ms 28004 KB Output is correct
11 Correct 975 ms 9544 KB Output is correct
12 Correct 2917 ms 32720 KB Output is correct
13 Correct 2824 ms 32720 KB Output is correct
14 Correct 2633 ms 32720 KB Output is correct
15 Correct 2508 ms 38712 KB Output is correct
16 Correct 4 ms 4940 KB Output is correct
17 Correct 4 ms 4940 KB Output is correct
18 Correct 238 ms 25536 KB Output is correct
19 Correct 716 ms 8468 KB Output is correct
20 Correct 2247 ms 28580 KB Output is correct
21 Correct 2166 ms 32724 KB Output is correct
22 Correct 1885 ms 33316 KB Output is correct
23 Correct 2178 ms 32028 KB Output is correct
24 Correct 2402 ms 33428 KB Output is correct
25 Correct 3 ms 4940 KB Output is correct
26 Correct 770 ms 9592 KB Output is correct
27 Correct 511 ms 30648 KB Output is correct
28 Correct 2912 ms 37288 KB Output is correct
29 Correct 2733 ms 37660 KB Output is correct
30 Correct 2675 ms 37840 KB Output is correct
31 Correct 2631 ms 38036 KB Output is correct
32 Correct 2505 ms 38244 KB Output is correct