oj.uz

Submission #493813

# Submission time Handle Problem Language Result Execution time Memory
493813 2021-12-13T03:37:54 Z czhang2718 Distributing Candies (IOI21_candies) C++17
100 / 100
 2343 ms 43000 KB 
#include "candies.h"

// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
#define f first
#define s second
const int Q=200000;

int n, q;
ll mn[4*Q], mx[4*Q];
ll lazy[4*Q];
vector<int> start[Q], en[Q];

void push(int x, int lx, int rx){
    if(rx-lx==1) return;
    lazy[2*x+1]+=lazy[x];
    lazy[2*x+2]+=lazy[x];
    mn[2*x+1]+=lazy[x];
    mx[2*x+1]+=lazy[x];
    mn[2*x+2]+=lazy[x];
    mx[2*x+2]+=lazy[x];
    lazy[x]=0;
}

void upd(int l, int r, int v, int x, int lx, int rx){
    push(x, lx, rx);
    if(lx>=l && rx<=r){
        lazy[x]+=v;
        mn[x]+=v;
        mx[x]+=v;   
        return;
    }
    if(lx>=r || rx<=l) return;
    int m=(lx+rx)/2;
    upd(l, r, v, 2*x+1, lx,m ); upd(l, r, v, 2*x+2, m, rx);
    mn[x]=min(mn[2*x+1], mn[2*x+2]);
    mx[x]=max(mx[2*x+1], mx[2*x+2]);
} 

void upd(int l, int r, int v){
    upd(l, r, v, 0, 0, q);
}

pll get_range(int l, int r, int x, int lx, int rx){
    push(x, lx, rx);
    if(lx>=l && rx<=r) return {mn[x], mx[x]};
    if(lx>=r || rx<=l) return {1e18, -1e18};
    int m=(lx+rx)/2;
    pll a=get_range(l, r, 2*x+1, lx, m);
    pll b=get_range(l, r, 2*x+2, m, rx);
    return {min(a.f, b.f), max(a.s, b.s)};
}  

pll get_range(int l, int r){
    if(l>=0) return get_range(l, r, 0, 0, q);
    pll p=get_range(0, r, 0, 0, q);
    return {min(0LL, p.f), max(0LL, p.s)};
}

ll st(int i){
    if(i==-1) return 0;
    return get_range(i, i+1).f;
}

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    n = c.size();
    q=l.size();
    std::vector<int> s(n);
    for(int i=0; i<q; i++){
        start[l[i]].push_back(i);
        en[r[i]].push_back(i);
    }

    for(int i=0; i<n; i++){
        for(int t:start[i]){
            upd(t, q, v[t]);
        }
        pll p=get_range(-1, q);
        if(p.s-p.f<=c[i]){
            s[i]=(st(q-1))-p.f;
        }
        else{
            int t=-1;
            for(int k=q; k; k/=2){
                pll p;
                while(t+k<q && (p=get_range(t+k, q)).s-p.f>c[i]) t+=k;
            }
            p=get_range(t, q);
            if(st(t)==p.s){
                s[i]=st(q-1)-p.f;
            }
            else{
                s[i]=(st(q-1)-(p.s-c[i]));
            }
        }
        
        for(int t:en[i]){
            upd(t, q, -v[t]);
        }
    }
    return s;
}
// range add
// range min max

// why did I believe
// I had to dream

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 6 ms 9804 KB Output is correct
4 Correct 7 ms 9804 KB Output is correct
5 Correct 12 ms 9964 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2254 ms 36304 KB Output is correct
2 Correct 2160 ms 36268 KB Output is correct
3 Correct 2001 ms 36256 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 338 ms 32652 KB Output is correct
3 Correct 574 ms 15644 KB Output is correct
4 Correct 1895 ms 42252 KB Output is correct
5 Correct 2080 ms 42568 KB Output is correct
6 Correct 2188 ms 43000 KB Output is correct
7 Correct 2343 ms 42304 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 201 ms 28356 KB Output is correct
4 Correct 540 ms 13540 KB Output is correct
5 Correct 1281 ms 34384 KB Output is correct
6 Correct 1439 ms 35052 KB Output is correct
7 Correct 1424 ms 35700 KB Output is correct
8 Correct 1206 ms 34272 KB Output is correct
9 Correct 1569 ms 35828 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 6 ms 9804 KB Output is correct
4 Correct 7 ms 9804 KB Output is correct
5 Correct 12 ms 9964 KB Output is correct
6 Correct 2254 ms 36304 KB Output is correct
7 Correct 2160 ms 36268 KB Output is correct
8 Correct 2001 ms 36256 KB Output is correct
9 Correct 5 ms 9676 KB Output is correct
10 Correct 338 ms 32652 KB Output is correct
11 Correct 574 ms 15644 KB Output is correct
12 Correct 1895 ms 42252 KB Output is correct
13 Correct 2080 ms 42568 KB Output is correct
14 Correct 2188 ms 43000 KB Output is correct
15 Correct 2343 ms 42304 KB Output is correct
16 Correct 5 ms 9676 KB Output is correct
17 Correct 5 ms 9676 KB Output is correct
18 Correct 201 ms 28356 KB Output is correct
19 Correct 540 ms 13540 KB Output is correct
20 Correct 1281 ms 34384 KB Output is correct
21 Correct 1439 ms 35052 KB Output is correct
22 Correct 1424 ms 35700 KB Output is correct
23 Correct 1206 ms 34272 KB Output is correct
24 Correct 1569 ms 35828 KB Output is correct
25 Correct 5 ms 9676 KB Output is correct
26 Correct 444 ms 13636 KB Output is correct
27 Correct 290 ms 32104 KB Output is correct
28 Correct 1639 ms 40896 KB Output is correct
29 Correct 1909 ms 41320 KB Output is correct
30 Correct 2075 ms 41388 KB Output is correct
31 Correct 2171 ms 41584 KB Output is correct
32 Correct 1841 ms 41816 KB Output is correct