Submission #813567

#	Time	Username	Problem	Language	Result	Execution time	Memory
813567		Username4132	Distributing Candies (IOI21_candies)	C++17	100 / 100	1252 ms	69444 KiB

candies

#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 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33