oj.uz

Submission #435207

# Submission time Handle Problem Language Result Execution time Memory
435207 2021-06-23T05:27:25 Z CodePlatina Distributing Candies (IOI21_candies) C++17
100 / 100
 868 ms 51084 KB 
#include "candies.h"

#include <vector>
#include <algorithm>
#include <tuple>
#define pii pair<int, int>
#define ff first
#define ss second

using namespace std;

const long long INF = (long long)8e18 + 100;

struct Node
{
    long long mx, mn, up, dn, l;
    Node(void) : mx(0), mn(0), up(0), dn(0), l(0) {}
}seg[808080];

void prop(int ind)
{
    if(!seg[ind].l) return;
    seg[ind << 1].mx += seg[ind].l;
    seg[ind << 1].mn += seg[ind].l;
    seg[ind << 1].l += seg[ind].l;
    seg[ind << 1 | 1].mx += seg[ind].l;
    seg[ind << 1 | 1].mn += seg[ind].l;
    seg[ind << 1 | 1].l += seg[ind].l;
    seg[ind].l = 0;
}

void mrge(int ind)
{
    Node &nd = seg[ind], &x = seg[ind << 1], &y = seg[ind << 1 | 1];
    nd.mx = max(x.mx, y.mx);
    nd.mn = min(x.mn, y.mn);
    nd.up = max({x.up, y.up, y.mx - x.mn});
    nd.dn = max({x.dn, y.dn, x.mx - y.mn});
}

void upd(int ind, int s, int e, int l, int r, long long x)
{
    if(e <= l || r <= s) return;
    if(l <= s && e <= r)
    {
        seg[ind].mn += x;
        seg[ind].mx += x;
        seg[ind].l += x;
        return;
    }

    int mid = s + e >> 1;
    prop(ind);
    upd(ind << 1, s, mid, l, r, x);
    upd(ind << 1 | 1, mid, e, l, r, x);
    mrge(ind);
}

int ub(int ind, int s, int e, long long x, long long mx)
{
    if(s + 1 == e)
    {
        if(mx - seg[ind].mn > x) return s;
        else return s - 1;
    }

    int mid = s + e >> 1;
    prop(ind);
    if(seg[ind << 1 | 1].up > x || mx - seg[ind << 1 | 1].mn > x) return ub(ind << 1 | 1, mid, e, x, mx);
    else return ub(ind << 1, s, mid, x, max(mx, seg[ind << 1 | 1].mx));
}

int lb(int ind, int s, int e, long long x, long long mn)
{
    if(s + 1 == e)
    {
        if(seg[ind].mx - mn > x) return s;
        else return s - 1;
    }

    int mid = s + e >> 1;
    prop(ind);
    if(seg[ind << 1 | 1].dn > x || seg[ind << 1 | 1].mx - mn > x) return lb(ind << 1 | 1, mid, e, x, mn);
    else return lb(ind << 1, s, mid, x, min(mn, seg[ind << 1 | 1].mn));
}

long long xqry(int ind, int s, int e, int l, int r)
{
    if(e <= l || r <= s) return -INF;
    if(l <= s && e <= r) return seg[ind].mx;

    int mid = s + e >> 1;
    prop(ind);
    return max(xqry(ind << 1, s, mid, l, r), xqry(ind << 1 | 1, mid, e, l, r));
}

long long nqry(int ind, int s, int e, int l, int r)
{
    if(e <= l || r <= s) return INF;
    if(l <= s && e <= r) return seg[ind].mn;

    int mid = s + e >> 1;
    prop(ind);
    return min(nqry(ind << 1, s, mid, l, r), nqry(ind << 1 | 1, mid, e, l, r));
}

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

    vector<pii> ls[n + 1];
    for(int i = 0; i < T; ++i)
    {
        ls[l[i]].push_back({i + 1, v[i]});
        ls[r[i] + 1].push_back({i + 1, -v[i]});
    }

    long long sum = 0;
    long long pr = 0;
    vector<int> ans;
    for(int i = 0; i < n; ++i)
    {
        for(auto [p, x] : ls[i]) upd(1, 0, T + 2, p + 1, T + 2, x), sum += x;
        upd(1, 0, T + 2, 1, T + 2, -c[i] - 1 - pr);
        pr = -c[i] - 1;

        int a = ub(1, 0, T + 2, c[i], -INF);
        int b = lb(1, 0, T + 2, c[i], INF);

        if(a > b) ans.push_back(-xqry(1, 0, T + 2, a, T + 2) + sum - 1);
        else ans.push_back(-nqry(1, 0, T + 2, b, T + 2) - c[i] + sum - 1);
    }

    return ans;
}

Compilation message

candies.cpp: In function 'void upd(int, int, int, int, int, long long int)':
candies.cpp:52:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |     int mid = s + e >> 1;
      |               ~~^~~
candies.cpp: In function 'int ub(int, int, int, long long int, long long int)':
candies.cpp:67:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |     int mid = s + e >> 1;
      |               ~~^~~
candies.cpp: In function 'int lb(int, int, int, long long int, long long int)':
candies.cpp:81:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |     int mid = s + e >> 1;
      |               ~~^~~
candies.cpp: In function 'long long int xqry(int, int, int, int, int)':
candies.cpp:92:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |     int mid = s + e >> 1;
      |               ~~^~~
candies.cpp: In function 'long long int nqry(int, int, int, int, int)':
candies.cpp:102:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |     int mid = s + e >> 1;
      |               ~~^~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31820 KB Output is correct
2 Correct 21 ms 31884 KB Output is correct
3 Correct 17 ms 31948 KB Output is correct
4 Correct 23 ms 31948 KB Output is correct
5 Correct 37 ms 32024 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 750 ms 51012 KB Output is correct
2 Correct 868 ms 51056 KB Output is correct
3 Correct 777 ms 51024 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 31948 KB Output is correct
2 Correct 366 ms 41160 KB Output is correct
3 Correct 212 ms 40504 KB Output is correct
4 Correct 719 ms 51048 KB Output is correct
5 Correct 740 ms 51056 KB Output is correct
6 Correct 843 ms 51036 KB Output is correct
7 Correct 757 ms 50944 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31792 KB Output is correct
2 Correct 17 ms 31820 KB Output is correct
3 Correct 215 ms 39908 KB Output is correct
4 Correct 170 ms 39352 KB Output is correct
5 Correct 413 ms 47852 KB Output is correct
6 Correct 387 ms 47752 KB Output is correct
7 Correct 412 ms 47804 KB Output is correct
8 Correct 368 ms 47876 KB Output is correct
9 Correct 369 ms 47772 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31820 KB Output is correct
2 Correct 21 ms 31884 KB Output is correct
3 Correct 17 ms 31948 KB Output is correct
4 Correct 23 ms 31948 KB Output is correct
5 Correct 37 ms 32024 KB Output is correct
6 Correct 750 ms 51012 KB Output is correct
7 Correct 868 ms 51056 KB Output is correct
8 Correct 777 ms 51024 KB Output is correct
9 Correct 18 ms 31948 KB Output is correct
10 Correct 366 ms 41160 KB Output is correct
11 Correct 212 ms 40504 KB Output is correct
12 Correct 719 ms 51048 KB Output is correct
13 Correct 740 ms 51056 KB Output is correct
14 Correct 843 ms 51036 KB Output is correct
15 Correct 757 ms 50944 KB Output is correct
16 Correct 17 ms 31792 KB Output is correct
17 Correct 17 ms 31820 KB Output is correct
18 Correct 215 ms 39908 KB Output is correct
19 Correct 170 ms 39352 KB Output is correct
20 Correct 413 ms 47852 KB Output is correct
21 Correct 387 ms 47752 KB Output is correct
22 Correct 412 ms 47804 KB Output is correct
23 Correct 368 ms 47876 KB Output is correct
24 Correct 369 ms 47772 KB Output is correct
25 Correct 18 ms 31780 KB Output is correct
26 Correct 168 ms 39448 KB Output is correct
27 Correct 379 ms 41124 KB Output is correct
28 Correct 742 ms 51084 KB Output is correct
29 Correct 807 ms 51004 KB Output is correct
30 Correct 735 ms 50940 KB Output is correct
31 Correct 730 ms 51004 KB Output is correct
32 Correct 795 ms 51040 KB Output is correct