Submission #600361

#	Time	Username	Problem	Language	Result	Execution time	Memory
600361		keta_tsimakuridze	Distributing Candies (IOI21_candies)	C++17	0 / 100	711 ms	25544 KiB

candies

#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 5, inf = 2e9;
ll lazy[4 * N], x, C;
struct node {
    int mx,  mn,  mn2,  mx2;
} tree[4*N];
void push(int u,int l,int r) {
    tree[u].mn += lazy[u];
    tree[u].mx += lazy[u];
    tree[u].mn2 += lazy[u];
    tree[u].mx2 += lazy[u];
    if(l != r) {
        lazy[2 * u] += lazy[u];
        lazy[2 * u + 1] += lazy[u];
    }
    lazy[u] = 0;
}
void UPD(int u,int mn, int mx) {
    tree[u].mn = max(tree[u].mn, mn);
    tree[u].mn2 = max(tree[u].mn2, mn);
    tree[u].mx = max(tree[u].mx, mn);
    tree[u].mx2 = max(tree[u].mx2, mn);

    tree[u].mn = min(tree[u].mn, mx);
    tree[u].mn2 = min(tree[u].mn2, mx);
    tree[u].mx = min(tree[u].mx, mx);
    tree[u].mx2 = min(tree[u].mx2, mx);
    if(tree[u].mn2 == tree[u].mn) tree[u].mn2 = inf;
    if(tree[u].mx2 == tree[u].mx) tree[u].mx2 = -inf;
}
node merge(node a, node b) {
    node c;
    if(a.mx == b.mx) c.mx = a.mx, c.mx2 = max(b.mx2, a.mx2);
    else {
        if(a.mx < b.mx) swap(a, b);
        c.mx = a.mx; c.mx2 = max(b.mx, a.mx2);
    }
    if(a.mn == b.mn) c.mn = a.mn, c.mn2 = min(b.mn2, a.mn2);
    else {
        if(a.mn > b.mn) swap(a, b);
        c.mn = a.mn; c.mn2 = min(b.mn, a.mn2);
    }
    return c;
}
void upd(int u, int st,int en,int l,int r,int up_mx,int up_mn) {
    push(u, l, r);
    up_mn = max(up_mn, tree[u].mn);
    up_mx = min(up_mx, tree[u].mx);
    UPD(u, up_mn, up_mx);
    if(0 <= tree[u].mn && C >= tree[u].mx) return;
    if(l > en || r < st) return;
    if(st <= l && r <= en && tree[u].mn2 > 0 && tree[u].mx2 < C) {
        UPD(u, 0, C);
        return;
    }
    int mid = (l + r) / 2;
    upd(2 * u, st, en, l, mid, up_mx, up_mn); upd(2 * u + 1, st, en, mid + 1, r, up_mx, up_mn);
    tree[u] = merge(tree[2 * u], tree[2 * u + 1]);
}
void upd(int u,int st,int en,int l,int r,int v, int up_mx, int up_mn) {
    upd(u, l, r, l, r, up_mx, up_mn);
    up_mn = max(up_mn, tree[u].mn);
    up_mx = min(up_mx, tree[u].mx);
    if(l > en || r < st) return;
    if(st <= l && r <= en) {
        lazy[u] = v;
        push(u, l, r);
        upd(u, l, r, l, r, up_mx + v, up_mn + v);
        x = tree[u].mn;
        return;
    }
    int mid = (l + r) / 2;
    upd(2 * u, st, en, l, mid, v, up_mx, up_mn);
    upd(2 * u + 1, st, en, mid + 1, r, v, up_mx, up_mn);
    tree[u] = merge(tree[2 * u], tree[2 * u + 1]);
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int n = c.size();
    for(int i = 1; i <= 4 * n; i++) tree[i].mn = tree[i].mx = 0, tree[i].mn2 = inf, tree[i].mx2 = -inf;
    C = c[0];
    vector<ll> a(n);
    for(int i = 0; i < v.size(); i++) {
        upd(1, l[i], r[i], 0, n - 1, v[i], inf, -inf);
    }
    vector<int> ans(n);
    for(int i = 0; i < c.size(); i++) {
        upd(1, i, i, 0, n - 1, 0, c[i], 0);
        ans[i] = x;
    }
    return ans;

}

Compilation message (stderr)

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:86:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for(int i = 0; i < v.size(); i++) {
      |                    ~~^~~~~~~~~~
candies.cpp:90:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(int i = 0; i < c.size(); i++) {
      |                    ~~^~~~~~~~~~

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