제출 #1190732

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190732		duyngadocton	사탕 분배 (IOI21_candies)	C++20	0 / 100	50 ms	8260 KiB

candies

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


using namespace std;

#define pb push_back
#define fi first
#define se second
#define ll long long

const int MAX = (int) 1e5;

int n, q;
int a[MAX + 5];
vector<int> ans;

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];

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

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

    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]);
            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 = 1; i <= q; ++i) query[i] = queries(l[i - 1] + 1, r[i - 1] + 1, v[i - 1]);
    if(sub4::check()) sub4::solve(), 0;
    return ans;
}

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