oj.uz

답안 #811202

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
811202 2023-08-07T02:22:54 Z penguinman 사탕 분배 (IOI21_candies) C++17
40 / 100
 5000 ms 50648 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+1,0){
            eval(l>>i);
            eval(r>>i);
        }
        while(l < r){
            if(l & 1){
                eval(l);
                if(val > 0) lmax[l] = val;
                else lmin[l] = val;
                lsum[l] += val;
                l++;
            }
            l >>= 1;
            if((r&1) == 0){
                eval(r);
                if(val > 0) lmax[r] = val;
                else lmin[r] = val;
                lsum[r] += val;
                r--;
            }
            r >>= 1;
        }
        if(l == r){
            eval(l);
            if(val > 0) lmax[l] = val;
            else lmin[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+1,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 340 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Correct 12 ms 680 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4441 ms 49856 KB Output is correct
2 Correct 4539 ms 50572 KB Output is correct
3 Correct 4569 ms 50648 KB Output is correct

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1636 ms 14592 KB Output is correct
3 Correct 435 ms 34936 KB Output is correct
4 Execution timed out 5080 ms 44424 KB Time limit exceeded
5 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 1086 ms 14604 KB Output is correct
4 Correct 441 ms 35468 KB Output is correct
5 Correct 2453 ms 49360 KB Output is correct
6 Correct 2172 ms 49204 KB Output is correct
7 Correct 2033 ms 48832 KB Output is correct
8 Correct 2249 ms 49436 KB Output is correct
9 Correct 1979 ms 48124 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 340 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Correct 12 ms 680 KB Output is correct
6 Correct 4441 ms 49856 KB Output is correct
7 Correct 4539 ms 50572 KB Output is correct
8 Correct 4569 ms 50648 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1636 ms 14592 KB Output is correct
11 Correct 435 ms 34936 KB Output is correct
12 Execution timed out 5080 ms 44424 KB Time limit exceeded
13 Halted 0 ms 0 KB -