oj.uz

답안 #811176

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
811176 2023-08-07T01:51:30 Z penguinman 사탕 분배 (IOI21_candies) C++17
0 / 100
 5000 ms 27736 KB 
#include "candies.h"

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::vector;
using std::string;
using ll = int;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
using std::endl;

#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define all(a) a.begin(),a.end()

constexpr ll inf = (1<<30);

struct lazy_segment_tree{
    ll N;
    ll log;
    vi sum, max, min;
    vi lsum, lmax, lmin;
    lazy_segment_tree(ll n){
        N = 1;
        log = 0;
        while(N <= n){
            N *= 2;
            log++;
        }
        sum.resize(2*N);
        max.resize(2*N);
        min.resize(2*N);
        lsum.resize(2*N);
        lmax.resize(2*N);
        lmin.resize(2*N);
    }
    void update(ll a, ll b, ll val, ll now = 1, ll l = 0, ll r = -1){
        if(r == -1) r = N;
        eval(now);
        if(a <= l && r <= b){
            if(val > 0) lmax[now] = val;
            else lmin[now] = val;
            lsum[now] += val;
            return;
        }
        if(r <= a || b <= l) return;
        update(a,b,val,now*2,l,(l+r)/2);
        update(a,b,val,now*2+1,(l+r)/2,r);
    }
    pii calc(ll now){
        now += N;
        per(i,log+1,0){
            eval((now>>i));
        }
        return mp(max[now], min[now]);
    }
    void eval(ll now){
        max[now] = std::min(inf,std::max(max[now], sum[now]+lmax[now]));
        min[now] = std::max(-inf,std::min(min[now], sum[now]+lmin[now]));
        sum[now] += lsum[now];
        sum[now] = std::min(inf, sum[now]);
        sum[now] = std::max(sum[now], -inf);
        if(now < N){
            lmax[now*2] = std::min(inf,std::max(lmax[now*2], lsum[now*2]+lmax[now]));
            lmin[now*2] = std::max(-inf,std::min(lmin[now*2], lsum[now*2]+lmin[now]));
            lsum[now*2] += lsum[now];
            lsum[now*2] = std::min(lsum[now*2], inf);
            lsum[now*2] = std::max(lsum[now*2+1], -inf);
            lmax[now*2+1] = std::min(inf,std::max(lmax[now*2+1], lsum[now*2+1]+lmax[now]));
            lmin[now*2+1] = std::max(-inf,std::min(lmin[now*2+1], lsum[now*2+1]+lmin[now]));
            lsum[now*2+1] += lsum[now];
            lsum[now*2+1] = std::min(lsum[now*2], inf);
            lsum[now*2+1] = std::max(lsum[now*2+1], -inf);
        }
        lmax[now] = lmin[now] = lsum[now] = 0;
    }
};

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int N = c.size();
    ll Q = l.size();
    vi left(N,-1), right(N,Q);
    while(true){
        lazy_segment_tree seg(N);
        vi mid(N);
        bool flg = true;
        vii query(Q+1);
        rep(i,0,N){
            if(left[i]+1 < right[i]){
                mid[i] = (left[i]+right[i])/2;
                query[mid[i]].pb(i);
                flg = false;
            }
        }
        if(flg) break;
        per(i,Q,0){
            if(i < Q){
                seg.update(l[i], r[i]+1, v[i]);
            }
            for(auto el: query[i]){
                auto ret = seg.calc(el);
                if(c[el] <= ret.first-ret.second) left[el] = mid[el];
                else right[el] = mid[el];
            }
        }
    }
    vector<int> ans(N);
    {
        vii max(Q+1), min(Q+1);
        rep(i,0,N){
            if(left[i] == -1) max[0].pb(i);
            else{
                if(v[left[i]] > 0){
                    min[left[i]].pb(i);
                }
                else{
                    max[left[i]].pb(i);
                }
            }
        }
        lazy_segment_tree seg(N);
        per(i,Q,0){
            if(i < Q){
                seg.update(l[i], r[i]+1, v[i]);
            }
            for(auto el: max[i]){
                ans[el] = seg.calc(el).first;
            }
            for(auto el: min[i]){
                ans[el] = c[el]+seg.calc(el).second;
            }
        }
    }
    return ans;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5044 ms 27736 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

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