oj.uz

Submission #813567

# Submission time Handle Problem Language Result Execution time Memory
813567 2023-08-07T20:29:40 Z Username4132 Distributing Candies (IOI21_candies) C++17
100 / 100
 1252 ms 69444 KB 
#include "candies.h"
#include <iostream>
#include <vector>
#include<cassert>
using namespace std;
using pii = pair<int, int>;
using ll = long long;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define dforsn(i, s, n) for(int i=n-1; i>=s; --i)
#define PB push_back
#define F first
#define S second

const int MAXN = 200010, INF = 1000000010;
int n, q;

struct node{
    bool neu;
    ll mx, mp, ms, sum;
    int l, r, pr, sl;
    node(ll _mx, ll _mp, ll _ms, ll _sum, int _l, int _r, int _pr, int _sl) : neu(false), mx(_mx), mp(_mp), ms(_ms), sum(_sum), l(_l), r(_r), pr(_pr), sl(_sl) {}
    node(ll value, int pos){
        sum = value;
        neu = false;
        if(value > 0){
            mx = mp = ms = value;
            l = sl = pos;
            r = pr = pos + 1;
        }
        else{
            mx = mp = ms = 0;
            sl = pos + 1;
            l = r = pr = pos;
        }
    }
    node(){
        neu = true;
        mx=mp=ms=sum=l=r=pr=sl=0;
    }
};

node combine(node nl, node nr){
    if(nl.neu) return nr;
    if(nr.neu) return nl;

    ll mx, mp, ms, sum;
    int l, r, pr, sl;
    sum = nl.sum + nr.sum;

    if(nl.mp > nl.sum + nr.mp){
        mp = nl.mp, pr = nl.pr;
    }
    else{
        mp = nl.sum + nr.mp, pr = nr.pr;
    }

    if(nr.ms > nr.sum + nl.ms){
        ms = nr.ms, sl = nr.sl;
    }
    else{
        ms = nr.sum + nl.ms, sl = nl.sl;
    }

    ll mids = nl.ms + nr.mp;
    if(mids >= nl.mx && mids >= nr.mx){
        mx = mids, l = nl.sl, r = nr.pr;
    }
    else if(nl.mx >= mids && nl.mx >= nr.mx){
        mx = nl.mx, l = nl.l, r = nl.r;
    }
    else{
        mx = nr.mx, l = nr.l, r = nr.r;
    }

    return node(mx, mp, ms, sum, l, r, pr, sl);
}

void update(int pos, ll value, node* tr){
    tr[pos+q+1] = node(value+tr[pos+q+1].sum, pos);
    pos+=q+1;
    while(pos>1) pos>>=1, tr[pos] = combine(tr[pos<<1], tr[pos<<1|1]);
}

node query(int l, int r, node* tr){
    node resl, resr;
    for(l+=q+1, r+=q+1; l<r; l>>=1, r>>=1){
        if(l&1) resl = combine(resl, tr[l++]);
        if(r&1) resr = combine(tr[--r], resr);
    }
    return combine(resl, resr);
}

node t1[2*MAXN], t2[2*MAXN];
vector<pii> ops[MAXN];

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    n = (int)c.size();
    q = (int)v.size();
    ops[0].PB({-INF, 0});
    ops[n].PB({-INF, 0});

    forn(i, q){
        ops[l[i]].PB({v[i], i+1});
        ops[r[i]+1].PB({-v[i], i+1});
    }

    forn(i, q+1){
        t1[q+1+i] = node(0, i);
        t2[q+1+i] = node(0, i);
    }
    dforsn(i, 1, q+1){
        t1[i]=combine(t1[i<<1], t1[i<<1|1]);
        t2[i]=combine(t2[i<<1], t2[i<<1|1]);
    }

    vector<int> s(n);
    
    forn(i, n){
        for(pii el:ops[i]){
            update(el.S, el.F, t1);
            update(el.S, -el.F, t2);
        }
        
        int lo=0, hi=q+1;
        while(hi-lo>1){
            int mid = (hi+lo)>>1;
            node n1 = query(mid, q+1, t1);
            node n2 = query(mid, q+1, t2);

            if(n1.mx >= c[i] || n2.mx >= c[i]) lo=mid;
            else hi=mid;
        }

        node n1 = query(lo, q+1, t1);
        node n2 = query(lo, q+1, t2);

        if(n1.mx >= c[i]){
            int st = n1.r;
            s[i] = c[i] + query(st, q+1, t1).sum;
        }
        else{
            int st = n2.r;
            s[i] = query(st, q+1, t1).sum;
        }
    }
    
    return s;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 48820 KB Output is correct
2 Correct 27 ms 48820 KB Output is correct
3 Correct 24 ms 48852 KB Output is correct
4 Correct 23 ms 48956 KB Output is correct
5 Correct 26 ms 49012 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1084 ms 63688 KB Output is correct
2 Correct 1142 ms 66988 KB Output is correct
3 Correct 1225 ms 66924 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 48852 KB Output is correct
2 Correct 490 ms 61028 KB Output is correct
3 Correct 360 ms 54588 KB Output is correct
4 Correct 1252 ms 68748 KB Output is correct
5 Correct 1237 ms 69084 KB Output is correct
6 Correct 1012 ms 69444 KB Output is correct
7 Correct 924 ms 68924 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 48724 KB Output is correct
2 Correct 21 ms 48796 KB Output is correct
3 Correct 157 ms 59352 KB Output is correct
4 Correct 293 ms 52596 KB Output is correct
5 Correct 764 ms 62628 KB Output is correct
6 Correct 722 ms 63208 KB Output is correct
7 Correct 577 ms 63824 KB Output is correct
8 Correct 793 ms 62436 KB Output is correct
9 Correct 812 ms 63920 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 48820 KB Output is correct
2 Correct 27 ms 48820 KB Output is correct
3 Correct 24 ms 48852 KB Output is correct
4 Correct 23 ms 48956 KB Output is correct
5 Correct 26 ms 49012 KB Output is correct
6 Correct 1084 ms 63688 KB Output is correct
7 Correct 1142 ms 66988 KB Output is correct
8 Correct 1225 ms 66924 KB Output is correct
9 Correct 22 ms 48852 KB Output is correct
10 Correct 490 ms 61028 KB Output is correct
11 Correct 360 ms 54588 KB Output is correct
12 Correct 1252 ms 68748 KB Output is correct
13 Correct 1237 ms 69084 KB Output is correct
14 Correct 1012 ms 69444 KB Output is correct
15 Correct 924 ms 68924 KB Output is correct
16 Correct 22 ms 48724 KB Output is correct
17 Correct 21 ms 48796 KB Output is correct
18 Correct 157 ms 59352 KB Output is correct
19 Correct 293 ms 52596 KB Output is correct
20 Correct 764 ms 62628 KB Output is correct
21 Correct 722 ms 63208 KB Output is correct
22 Correct 577 ms 63824 KB Output is correct
23 Correct 793 ms 62436 KB Output is correct
24 Correct 812 ms 63920 KB Output is correct
25 Correct 21 ms 48724 KB Output is correct
26 Correct 317 ms 52668 KB Output is correct
27 Correct 469 ms 60512 KB Output is correct
28 Correct 1212 ms 67552 KB Output is correct
29 Correct 1160 ms 67916 KB Output is correct
30 Correct 1158 ms 68136 KB Output is correct
31 Correct 1042 ms 68180 KB Output is correct
32 Correct 1025 ms 68440 KB Output is correct