oj.uz

Submission #437081

# Submission time Handle Problem Language Result Execution time Memory
437081 2021-06-25T18:44:17 Z p3rfect Distributing Candies (IOI21_candies) C++17
0 / 100
 807 ms 42320 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(ll nom, ll l, ll r)
    {
        if (l == r){
            if (l > q + 2) t[nom].mn = MAXLL, t[nom].mx = MINLL;
            return;
        }

        ll mid = (l + r) / 2;
        build(nom * 2, l, mid);
        build(nom * 2 + 1, mid + 1, r);
        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 build_segtree()
    {
        while (sz < q + 3) sz *= 2;
        sz--;
        build(1, 0, 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);
    }

    pair < ll, pll > get(ll nom, ll l, ll r, ll c, ll mx, ll mn)
    {
        propagate(nom, l, r);

        if (l == r) return {l, {mn, mx}};

        ll mid = (l + r) / 2;
        if (max(t[nom * 2 + 1].mx, mx) - min(t[nom * 2 + 1].mn, mn) > c){
            return get(nom * 2 + 1, mid + 1, r, c, mx, mn);
        }
        else{
            return get(nom * 2, l, mid, c, max(mx, t[nom * 2 + 1].mx), min(mn, t[nom * 2 + 1].mn));
        }
    }

    ll get(ll c)
    {
        pair < ll, pll > g = get(1, 0, sz, c, MINLL, MAXLL);
        ll idx = g.fi, mn = g.se.fi, mx = g.se.se;
        idx += sz + 1;

        if (t[idx].mn < lst) 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;
//}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Incorrect 4 ms 4940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 451 ms 30784 KB Output is correct
3 Correct 74 ms 9524 KB Output is correct
4 Correct 718 ms 35524 KB Output is correct
5 Correct 691 ms 41924 KB Output is correct
6 Incorrect 807 ms 42320 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Incorrect 4 ms 4940 KB Output isn't correct
3 Halted 0 ms 0 KB -