oj.uz

답안 #811297

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
811297 2023-08-07T03:52:04 Z penguinman 사탕 분배 (IOI21_candies) C++17
40 / 100
 5000 ms 57144 KB 
#include "candies.h"
 
#include <bits/stdc++.h>
 
using std::cin;
using std::cout;
using std::vector;
using std::string;
using ll = long long;
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()
 
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 l = a+N, r = b+N-1;
        per(i,log,0){
            eval(l>>i);
            eval(r>>i);
        }
        while(l < r){
            if(l & 1){
                lmax[l] = std::max(lmax[l], lsum[l]+val);
                lmin[l] = std::min(lmin[l], lsum[l]+val);
                lsum[l] += val;
                l++;
            }
            l >>= 1;
            if((r&1) == 0){
                lmax[r] = std::max(lmax[r], lsum[r]+val);
                lmin[r] = std::min(lmin[r], lsum[r]+val);
                lsum[r] += val;
                r--;
            }
            r >>= 1;
        }
        if(l == r){
            lmax[l] = std::max(lmax[l], lsum[l]+val);
            lmin[l] = std::min(lmin[l], lsum[l]+val);
            lsum[l] += val;
        }
    }
    /*void update(ll a, ll b, ll val, ll now = 1, ll l = 0, ll r = -1){
        if(r == -1) r = N;
        if(r <= a || b <= l) return;
        eval(now);
        if(a <= l && r <= b){
            if(val > 0) lmax[now] = val;
            else lmin[now] = val;
            lsum[now] += val;
            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,0){
            eval(now>>i);
        }
        return mp(max[now], min[now]);
    }
    void eval(ll now){
        if(lmax[now]){
            max[now] = std::max(max[now], sum[now]+lmax[now]);
            if(now < N){
                lmax[now*2] = std::max(lmax[now*2], lsum[now*2]+lmax[now]);
                lmax[now*2+1] = std::max(lmax[now*2+1], lsum[now*2+1]+lmax[now]);
            }
            lmax[now] = 0;
        }
        if(lmin[now]){
            min[now] = std::min(min[now], sum[now]+lmin[now]);
            if(now < N){
                lmin[now*2] = std::min(lmin[now*2], lsum[now*2]+lmin[now]);
                lmin[now*2+1] = std::min(lmin[now*2+1], lsum[now*2+1]+lmin[now]);
            }
            lmin[now] = 0;
        }
        if(lsum[now]){
            sum[now] += lsum[now];
            if(now < N){
                lsum[now*2] += lsum[now];
                lsum[now*2+1] += lsum[now];
            }
            lsum[now] = 0;
        }
        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
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 3 ms 436 KB Output is correct
4 Correct 5 ms 468 KB Output is correct
5 Correct 10 ms 724 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3715 ms 54820 KB Output is correct
2 Correct 3985 ms 52624 KB Output is correct
3 Correct 3730 ms 52876 KB Output is correct

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 428 KB Output is correct
2 Correct 1119 ms 16644 KB Output is correct
3 Correct 414 ms 37008 KB Output is correct
4 Correct 4657 ms 50772 KB Output is correct
5 Correct 4358 ms 57144 KB Output is correct
6 Correct 4850 ms 55524 KB Output is correct
7 Execution timed out 5021 ms 54772 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 569 ms 17236 KB Output is correct
4 Correct 408 ms 36652 KB Output is correct
5 Correct 2764 ms 52912 KB Output is correct
6 Correct 2050 ms 53416 KB Output is correct
7 Correct 2043 ms 53004 KB Output is correct
8 Correct 2140 ms 52736 KB Output is correct
9 Correct 1900 ms 52348 KB Output is correct

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 3 ms 436 KB Output is correct
4 Correct 5 ms 468 KB Output is correct
5 Correct 10 ms 724 KB Output is correct
6 Correct 3715 ms 54820 KB Output is correct
7 Correct 3985 ms 52624 KB Output is correct
8 Correct 3730 ms 52876 KB Output is correct
9 Correct 1 ms 428 KB Output is correct
10 Correct 1119 ms 16644 KB Output is correct
11 Correct 414 ms 37008 KB Output is correct
12 Correct 4657 ms 50772 KB Output is correct
13 Correct 4358 ms 57144 KB Output is correct
14 Correct 4850 ms 55524 KB Output is correct
15 Execution timed out 5021 ms 54772 KB Time limit exceeded
16 Halted 0 ms 0 KB -