Submission #1038921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038921		Andrey	Distributing Candies (IOI21_candies)	C++17	100 / 100	911 ms	68436 KiB

candies

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

long long n,q;
vector<pair<long long,long long>> haha[200001];
vector<pair<long long,long long>> big(1000001);
vector<pair<long long,long long>> sm(1000001);
vector<long long> wow(1000001);

void build(long long l, long long r, long long x) {
    if(l == r) {
        big[x] = {0,l};
        sm[x] = {0,-l};
        return;
    }
    long long mid = (l+r)/2;
    build(l,mid,x*2);
    build(mid+1,r,x*2+1);
    big[x] = max(big[x*2],big[x*2+1]);
    sm[x] = min(sm[x*2],sm[x*2+1]);
}

void upd(long long l, long long r, long long ql, long long qr, long long x, long long br) {
    if(l == ql && r == qr) {
        wow[x]+=br;
        big[x] = {big[x].first+br,big[x].second};
        sm[x] = {sm[x].first+br,sm[x].second};
        return;
    }
    long long mid = (l+r)/2;
    if(qr <= mid) {
        upd(l,mid,ql,qr,x*2,br);
    }
    else if(ql > mid) {
        upd(mid+1,r,ql,qr,x*2+1,br);
    }
    else {
        upd(l,mid,ql,mid,x*2,br);
        upd(mid+1,r,mid+1,qr,x*2+1,br);
    }
    big[x] = max(big[x*2],big[x*2+1]);
    sm[x] = min(sm[x*2],sm[x*2+1]);
    big[x] = {big[x].first+wow[x],big[x].second};
    sm[x] = {sm[x].first+wow[x],sm[x].second};
}

pair<long long,long long> calc(long long l, long long r, long long ql, long long qr, long long x, bool y) {
    if(ql > qr) {
        return {0,-1};
    }
    if(l == ql && r == qr) {
        if(y) {
            return big[x];
        }
        else {
            return sm[x];
        }
    }
    long long mid = (l+r)/2;
    pair<long long,long long> ans;
    if(qr <= mid) {
        ans = calc(l,mid,ql,qr,x*2,y);
    }
    else if(ql > mid) {
        ans = calc(mid+1,r,ql,qr,x*2+1,y);
    }
    else {
        pair<long long,long long> a = calc(l,mid,ql,mid,x*2,y);
        pair<long long,long long> b = calc(mid+1,r,mid+1,qr,x*2+1,y);
        if(y) {
            ans = max(a,b);
        }
        else {
            ans = min(a,b);
        }
    }
    ans = {ans.first+wow[x],ans.second};
    return ans;
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    n = c.size();
    q = l.size();
    for(long long i = 0; i < q; i++) {
        haha[l[i]].push_back({v[i],q+1-i});
        haha[r[i]+1].push_back({-v[i],q+1-i});
    }
    q++;
    build(1,q,1);
    vector<int> ans(n);
    for(long long i = 0; i < n; i++) {
        for(pair<long long,long long> v: haha[i]) {
            upd(1,q,v.second,q,1,v.first);
        }
        long long bl = 0,br = q;
        while(bl < br) {
            long long mid = (br+bl+1)/2;
            if(calc(1,q,1,mid,1,1).first-calc(1,q,1,mid,1,0).first < c[i]) {
                bl = mid;
            }
            else {
                br = mid-1;
            }
        }
        long long p = bl;
        if(p == q) {
            ans[i] = calc(1,q,1,q,1,1).first;
        }
        else {
            p++;
            pair<long long,long long> a = calc(1,q,1,p,1,1);
            pair<long long,long long> b = calc(1,q,1,p,1,0);
            b = {b.first,-b.second};
            if(b.second > a.second) {
                ans[i] = a.first;
            }
            else {
                ans[i] = c[i]+b.first;
            }
        }
    }
    return ans;
}

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