제출 #1190584

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190584		duyngadocton	사탕 분배 (IOI21_candies)	C++20	0 / 100	49 ms	10564 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];
    pair<ll, int> 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].fi = smin[q].fi = s[q];
        smax[q].se = -q;
        smin[q].se = q;
        for(int i = q - 1; i >= 1; --i) smax[i] = max(smax[i + 1], {s[i], -i});
        for(int i = q - 1; i >= 1; --i) smin[i] = min(smin[i + 1], {s[i], i});
        for(int i = 1; i <= q; ++i) dis[i] = smax[i].fi - smin[i].fi;
        dis[0] = LLONG_MAX;
        for(int i = 1; i <= n; ++i) {
            int lo = -1, hi = q;
            while(hi - lo > 1) {
                int mid = lo + hi >> 1;
                if (dis[mid] <= a[i]) hi = mid;
                else lo = mid;
            }

            int c;

            int A = -smax[hi].se, B = smin[hi].se;

            int E = min(A, B);

            c = (query[E].v < 0) ? -1 : 1;
            if(c == -1) ans.pb(s[q] - s[E]);
            else ans.pb(a[i] + s[q] - s[E]);
        }

    }
}

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];
    l.insert(l.begin(), 0);
    r.insert(r.begin(), n-1);
    v.insert(v.begin(), -1e9);

    l.insert(l.begin(), 0);
    r.insert(r.begin(), n-1);
    v.insert(v.begin(), 1e9);

    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