Submission #1239035

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239035		dosts	Distributing Candies (IOI21_candies)	C++20	0 / 100	5095 ms	84872 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 2e5+1, inf = 2e9;
vi C,V;
vector<signed> ans;


struct Node {
    int mnsuf =0 ,mxsuf = 0,sm = 0;
};

Node merge(Node a,Node b) {
    Node ret;
    ret.sm = a.sm+b.sm;
    ret.mxsuf = max(0ll,max(b.sm+a.mxsuf,b.mxsuf));
    ret.mnsuf = min(0ll,min(b.sm+a.mnsuf,b.mnsuf));
    return ret;
}
struct ST {
    vector<Node> t;

    ST(int nn) {
        t.assign(4*nn+1,Node{0,0,0});
    }


    void activate(int node,int l,int r,int p) {
        if (l == r) {
            t[node] = {min(0ll,V[l-1]),max(0ll,V[l-1]),V[l-1]};
            return;
        }
        int m = (l+r) >> 1;
        if (p <= m) activate(2*node,l,m,p);
        else activate(2*node+1,m+1,r,p);
        t[node] = merge(t[2*node],t[2*node+1]);
    }

    void deactivate(int node,int l,int r,int p) {
        if (l == r) {
            t[node] = {0,0,0};
            return;
        }
        int m = (l+r) >> 1;
        if (p <= m) deactivate(2*node,l,m,p);
        else deactivate(2*node+1,m+1,r,p);
        t[node] = merge(t[2*node],t[2*node+1]);
    }

    int sumq(int node,int l,int r,int L,int R) {
        if (l > R || r < L) return 0;
        if (l >= L && r <= R) return t[node].sm;
        int m = (l+r) >> 1;
        return sumq(2*node,l,m,L,R)+sumq(2*node+1,m+1,r,L,R);
    }

    int walk(int node,int l,int r,int x) {
        if (abs(t[node].mnsuf)+t[node].mxsuf < x) return -1;
        if (l == r) return l;
        int m = (l+r) >> 1;
        int w = walk(2*node+1,m+1,r,x);
        if (w != -1) return w;
        return walk(2*node,l,m,x);
    }
} st(LIM);

int q;
void activate(int p) {
    st.activate(1,1,q,p);
}

void deactivate(int p) {
    st.deactivate(1,1,q,p);
}

int eval(int p,int c) {
    int lst = st.walk(1,1,q,c);
    if (lst == -1) return c+st.sumq(1,1,q,1,q);
    if (V[lst-1] > 0) return c+st.sumq(1,1,q,lst+1,q);
    return st.sumq(1,1,q,lst+1,q);
}

struct DNQ {
    vector<vi> t;

    DNQ(int nn) {
        t.resize(4*nn+1);
    }

    void update(int node,int l,int r,int L,int R,int v) {
        if (l > R || r < L) return;
        if (l >= L && r <= R) {
            t[node].push_back(v);
            return;
        }
        int m = (l+r) >> 1;
        update(2*node,l,m,L,R,v),update(2*node+1,m+1,r,L,R,v);
    }

    void walk(int node,int l,int r) {
        for (auto it : t[node]) activate(it);
        if (l == r) {
            ans[l-1] = eval(l,C[l-1]);
            return;
        }
        int m = (l+r) >> 1;
        walk(2*node,l,m);
        walk(2*node+1,m+1,r);
        for (auto it : t[node]) deactivate(it);
    }
};
std::vector<int32_t> distribute_candies(std::vector<int32_t> c, std::vector<int32_t> l,
                                    std::vector<int32_t> r, std::vector<int32_t> v) {
    //activate deactivate find suffix that has abs(min)+max >= c
    int n = c.size();
    q = l.size();
    C = vi(all(c));
    V = vi(all(v));
    ans.resize(n);
    DNQ dnq(n);
    for (int i = 0;i<q;i++) {
        dnq.update(1,1,n,l[i]+1,r[i]+1,i+1);
    }
    dnq.walk(1,1,n);
    return ans;
}

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