제출 #1170422

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170422		PagodePaiva	사탕 분배 (IOI21_candies)	C++20	29 / 100	291 ms	28624 KiB

candies

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

using namespace std;

const long long N = 200010;
long long c[N];
long long n;

struct Segtree{
    long long tree[4*N];
    array <long long, 3> lazy[4*N];
    long long join(long long a, long long b){
        return max(a, b);
    }
    void build(long long node, long long l, long long r){
        lazy[node] = {0, 0, 0};
        if(l == r){
            tree[node] = 0;
            return;
        }
        long long mid = (l+r)/2;
        build(2*node, l, mid);
        build(2*node+1, mid+1, r);
        tree[node] = join(tree[2*node], tree[2*node+1]);
    }
    void unlazy(long long node, long long l, long long r){
        if(lazy[node][1] == 1){
            tree[node] = 0;
        }
        else if(lazy[node][2] == 1){
            tree[node] = c[r];
        }
        tree[node] += lazy[node][0];
        if(l != r){
            if(lazy[node][1] == 1 or lazy[node][2] == 1){
                lazy[2*node] = lazy[2*node+1] = lazy[node];
            }
            else{
                lazy[2*node][0] += lazy[node][0];
                lazy[2*node+1][0] += lazy[node][0];
            }
        }
        lazy[node] = {0, 0, 0};
    }
    void updateadd(long long node, long long l, long long r, long long tl, long long tr, long long val){
        unlazy(node, tl, tr);
        if(l > tr or tl > r) return;
        if(l <= tl and tr <= r){
            lazy[node][0] += val;
            unlazy(node, tl, tr);
            return;
        }
        long long mid = (tl+tr)/2;
        updateadd(2*node, l, r, tl, mid, val);
        updateadd(2*node+1, l, r, mid+1, tr, val);
        tree[node] = join(tree[2*node], tree[2*node+1]);
        return;
    }
    void updateset(long long node, long long l, long long r, long long tl, long long tr, long long val){
        unlazy(node, tl, tr);
        if(l > tr or tl > r) return;
        if(l <= tl and tr <= r){
            lazy[node] = {0, 0, 0};
            lazy[node][val] = 1;
            unlazy(node, tl, tr);
            return;
        }
        long long mid = (tl+tr)/2;
        updateset(2*node, l, r, tl, mid, val);
        updateset(2*node+1, l, r, mid+1, tr, val);
        tree[node] = join(tree[2*node], tree[2*node+1]);
        return;
    }
    long long query(long long node, long long l, long long r, long long tl, long long tr){
        unlazy(node, tl, tr);
        if(l > tr or tl > r) return 0;
        if(l <= tl and tr <= r) return tree[node];
        long long mid = (tl+tr)/2;
        return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
    }
    long long busca(long long node,long long l, long long r, long long val){
        unlazy(node, l, r);
        if(val > 0){
            if(l == r){
                if(c[l]-tree[node] < val) return n+1;
                return l;
            }
            long long mid = (l+r)/2;
            unlazy(2*node, l, mid);
            if(c[mid]-tree[2*node] >= val) return busca(2*node, l, mid, val);
            return busca(2*node+1, mid+1, r, val);
        }
        else{
            if(l == r){
                if(tree[node] < -val) return n+1;
                return l;
            }
            long long mid = (l+r)/2;
            unlazy(2*node, l, mid);
            if(tree[2*node] >= -val) return busca(2*node, l, mid, val);
            return busca(2*node+1, mid+1, r, val);
        }
    }
} seg;

std::vector<int> distribute_candies(std::vector<int> cc, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    n = cc.size();
    vector <pair <long long, long long>> maximos;
    for(long long i = 0;i < n;i++){
        maximos.push_back({cc[i], i});
    }
    sort(maximos.begin(), maximos.end());
    for(long long j = 0;j < n;j++){
        c[j+1] = maximos[j].first;
    }
    seg.build(1, 1, n);
    for(auto x : v){
        if(x > 0){
            long long pos = seg.busca(1, 1, n, x);
           //cout << pos << '\n';
            seg.updateset(1, 1, pos-1, 1, n, 2);
            seg.updateadd(1, pos, n, 1, n, x);
        }
        else{
            long long pos = seg.busca(1, 1, n, x);
            //cout << pos << '\n';
            seg.updateset(1, 1, pos-1, 1, n, 1);
            seg.updateadd(1,pos, n, 1, n, x);
        }
    }
    vector <int> ans(n);
    for(long long i = 0;i < n;i++){
        ans[maximos[i].second] = seg.query(1, i+1, i+1, 1, n); 
    }
    return ans;
}

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