oj.uz

답안 #939537

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
939537 2024-03-06T13:21:14 Z haxorman 사탕 분배 (IOI21_candies) C++17
8 / 100
 1412 ms 44880 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define ll long long

const int mxN = 2e5 + 7;
const int SZ = exp2(ceil(log2(mxN)));
const ll INF = 1e18;

int n, q;
ll lazy[4*mxN];
pair<ll,int> seg[4*mxN][2];
vector<pair<int,int>> que[mxN][2];

void push(int ind, int l, int r, int cnt = 1) {
    seg[ind][0].f += lazy[ind];
    seg[ind][1].f += lazy[ind];

    if (l != r) {
        lazy[2*ind] += lazy[ind];
        lazy[2*ind+1] += lazy[ind];

        if (cnt) {
            int mid = (l+r)/2;
            push(2*ind,l,mid,cnt-1);
            push(2*ind+1,mid+1,r,cnt-1);
        }
    }
    lazy[ind] = 0;
}

void update(int lo, int hi, ll inc, int ind=1, int l=0, int r=SZ-1) {
    push(ind,l,r);
    if (lo > r || l > hi) {
        return;
    }

    if (lo <= l && r <= hi) {
        lazy[ind] += inc;
        push(ind,l,r);
        return;
    }
    
    int mid = (l+r)/2;
    update(lo,hi,inc,2*ind,l,mid);
    update(lo,hi,inc,2*ind+1,mid+1,r);
    
    if (seg[2*ind][0].f < seg[2*ind+1][0].f) seg[ind][0] = seg[2*ind][0];
    else seg[ind][0] = seg[2*ind+1][0];

    if (seg[2*ind][1].f > seg[2*ind+1][1].f) seg[ind][1] = seg[2*ind][1];
    else seg[ind][1] = seg[2*ind+1][1];
}

// {min, max}
pair<pair<ll,int>,pair<ll,int>>
walk(int c, pair<ll,int> mn, pair<ll,int> mx, int ind=1, int l=0, int r=SZ-1) {
    push(ind,l,r);

    if (l == r) {
        return {min(mn,seg[ind][0]),max(mx,seg[ind][1])};
    }

    int mid = (l+r)/2;
    if (max(mx.f,seg[2*ind+1][1].f) - min(mn.f,seg[2*ind+1][0].f) >= c) {
        return walk(c,mn,mx,2*ind+1,mid+1,r);
    }
    else {
        return walk(c,min(mn,seg[2*ind+1][0]),max(mx,seg[2*ind+1][1]),
                    2*ind,l,mid);
    }
}

ll query(int pos, int ind=1, int l=0, int r=SZ-1) {
    push(ind,l,r);
    if (l == r) {
        return seg[ind][0].f;
    }

    int mid = (l+r)/2;
    if (pos <= mid) {
        return query(pos,2*ind,l,mid);
    }
    else {
        return query(pos,2*ind+1,mid+1,r);
    }
}

vector<int> distribute_candies(vector<int> c, vector<int> l,
                                    vector<int> r, vector<int> v) {
    n = c.size(), q = v.size()+1;

    seg[1+SZ][0] = seg[1+SZ][1] = {0, 1};
    for (int i = 2; i <= q; ++i) {
        que[l[i-2]][0].push_back({v[i-2], i});
        que[r[i-2]][1].push_back({v[i-2], i});

        seg[i+SZ][0] = seg[i+SZ][1] = {0, i};
    }
    
    for (int ind = SZ-1; ind >= 0; --ind) {
        if (seg[2*ind][0].f < seg[2*ind+1][0].f) seg[ind][0] = seg[2*ind][0];
        else seg[ind][0] = seg[2*ind+1][0];

        if (seg[2*ind][1].f > seg[2*ind+1][1].f) seg[ind][1] = seg[2*ind][1];
        else seg[ind][1] = seg[2*ind+1][1];
    }
    
    vector<int> ans(n);
    for (int i = 0; i < n; ++i) {
        for (auto [val, t] : que[i][0]) {
            update(t, q, val);
        }
        update(1,q,-c[i]);
        
        /*
        for (int j = 0; j <= q; ++j) {
            cout << query(j,j).f.f << ' ';
        }
        cout << "\n";
        */
        
        auto cur = walk(c[i],{INF,0},{-INF,0});
        if (cur.s.s > cur.f.s) {
            ans[i] = c[i] + query(q) - query(cur.s.s);
        }
        else {
            ans[i] = query(q) - query(cur.f.s);
        }
        /*
        int lb = 0, rb = q;
        ll res = 0;
        while (lb <= rb) {
            int mb = (lb+rb)/2;
            auto cur = query(mb,q);

            if (cur.s.f - cur.f.f >= (ll) c[i]) {
                lb = mb + 1;

                if (cur.s.s > cur.f.s) {
                    res = c[i] + query(q,q).f.f - query(cur.s.s,cur.s.s).f.f;
                }
                else {
                    res = query(q,q).f.f - query(cur.f.s,cur.f.s).f.f;
                }
            }
            else {
                rb = mb - 1;
            }
        }
        ans[i] = res;
        */
        
        update(1,q,c[i]);
        for (auto [val, t] : que[i][1]) {
            update(t, q, -val);
        }
    }
    return ans;
}

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 21084 KB Output is correct
2 Incorrect 5 ms 21168 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1396 ms 44860 KB Output is correct
2 Correct 1412 ms 44860 KB Output is correct
3 Correct 1383 ms 44880 KB Output is correct

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 21080 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 21084 KB Output is correct
2 Incorrect 7 ms 21136 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 21084 KB Output is correct
2 Incorrect 5 ms 21168 KB Output isn't correct
3 Halted 0 ms 0 KB -