Submission #1190564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190564		duyngadocton	Distributing Candies (IOI21_candies)	C++20	0 / 100	46 ms	9796 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define fi first
#define se second
#define ii pair<int,int>
#define iii pair<ii,int>
#define pb push_back

const int MAX = (int) 2e5;

int n;
int a[MAX + 5];
int q;

struct queries {
    int l, r, v;
    queries(int _l = 0, int _r = 0, int _v = 0) : l(_l), r(_r), v(_v) {}
} query[MAX + 5];
vector<int> ans;

namespace sub4 {
    ll s[MAX + 5];
    ll smax[MAX + 5], smin[MAX + 5];
    ll dis[MAX + 5];

    bool check() {
        for(int i = 1; i <= q; ++i) if(query[i].l != 1 || query[i].r != n) return 0;
        return 1;
    }

    void solve() {
        for(int i = 1; i <= q; ++i) s[i] = s[i - 1] + query[i].v;
        smax[q] = smin[q] = s[q];
        for(int i = q - 1; i >= 1; --i) smax[i] = max(smax[i + 1], s[i]);
        for(int i = q - 1; i >= 1; --i) smin[i] = min(smin[i + 1], s[i]);
        for(int i = 1; i <= q; ++i) dis[i] = max(smax[i] - s[i - 1], 0LL) - min(smin[i] - s[i - 1], 0LL);
        for(int i = 1; i <= n; ++i) {
            int lo = 0, hi = q + 1;
            while(hi - lo > 1) {
                int mid = lo + hi >> 1;
                if(dis[mid] <= a[i]) hi = mid;
                else lo = mid;
            }
            int c;
            if(hi == 1) {
                c = -1;
            }
            else c = (query[hi - 1].v < 0) ? -1 : 1;
            if(c == -1) ans.pb(s[q] - s[hi - 1]);
            else ans.pb(a[i] + s[q] - s[hi - 1]);
        }

    }
}

vector<int> distribute_candies(vector<int> c, vector<int> l,vector<int> r, vector<int> v) {
    n = c.size();
    for(int i = 0; i < n; ++i) a[i + 1] = c[i];
    q = l.size();
    for(int i = 0; i < q; ++i) query[i + 1] = queries(l[i] + 1, r[i] + 1, v[i]);
    if(sub4::check()) sub4::solve();
    return ans;
}

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