oj.uz

Submission #939728

# Submission time Handle Problem Language Result Execution time Memory
939728 2024-03-06T17:13:17 Z IS_Rushdi Distributing Candies (IOI21_candies) C++17
0 / 100
 5000 ms 21384 KB 
#include "candies.h" 
#include<bits/stdc++.h>
using namespace std;
typedef int64_t i64;
#define VII vector<int>
struct seg{
    int sz = 1;
    vector<i64>mn,mx,op;
    seg(int n){
        while(sz < n) sz*=2;
        mn.assign(sz*2,0ll);
        mx.assign(sz*2,0ll);
        op.assign(sz*2,0ll);
    }
    void update(int l,int r,i64 v,int x=0,int lx=0,int rx=-1){
        if(rx == -1) rx = sz;
        
        if(rx <= l || lx >= r) return;
        if(rx <= r && lx >= l){
            op[x] += v;
            mx[x] += v;
            mn[x] += v;
            return;
        }
        
        int m = (lx+rx)/2;
        update(l,r,v,x*2+1,lx,m);
        update(l,r,v,x*2+2,m,rx);
        mn[x] = min(mn[x*2+1],mn[x*2+2]) + op[x];
        mx[x] = max(mx[x*2+1],mx[x*2+2]) + op[x];
    }
    i64 getmn(int l,int r,int x=0,int lx=0,int rx=-1){
        if(rx == -1) rx = sz;
        if(rx <= l || lx >= r) return 1e18;
        if(rx <= r && lx >= l) return mn[x];
        int m = (lx+rx)/2;
        return min(getmn(l,r,x*2+1,lx,m),getmn(l,r,x*2+2,m,rx))+ op[x];
    }
    i64 getmx(int l,int r,int x=0,int lx=0,int rx=-1){
        if(rx == -1) rx = sz;
        if(rx <= l || lx >= r) return -1e18;
        if(rx <= r && lx >= l) return mx[x];
        int m = (lx+rx)/2;
        return max(getmx(l,r,x*2+1,lx,m),getmx(l,r,x*2+2,m,rx)) + op[x];
    }
};

VII distribute_candies(VII c,VII l ,VII r,VII v) {
    int n = c.size();
    int q = l.size();
    vector<pair<int,int>>C;
    for(int i = 0; i < n; i++) C.push_back({c[i],i});
    sort(C.rbegin(), C.rend());
    seg st(q);

    for(int i = 0; i < q; i++){
        st.update(i,q,v[i]);
    }
    
    vector<int>ans(n);
    function<int(int x)>f=[&](int x){
        int l = 0,r=q-1;
        int ret = q;
        while(l <= r){
            int m = (l+r)/2;
            i64 MX = st.getmx(0,m+1);
            if(MX > x){
                r = m-1;
                ret = m;
            }else{
                l = m+1;
            }
        }
        return ret;
    };
    function<int(int x)>f2=[&](int x){
        int l = 0,r=q-1;
        int ret = q;
        while(l <= r){
            int m = (l+r)/2;
            i64 MN = st.getmn(0,m+1);
            if(MN < x){
                r = m-1;
                ret = m;
            }else{
                l = m+1;
            }
        }
        return ret;
    };
    for(int i = 0; i < n; i++){
        int num = C[i].first;
        while(true){
            int idx1=f(num),idx2=f2(0);
            if(min(idx1,idx2) == q) break;
            if(idx1 < idx2){
                i64 rm = st.getmx(0,idx1+1)-num;
                st.update(idx1,q,-rm);
            }else{
                i64 rm = st.getmn(0,idx2+1);
                st.update(idx2,q,-rm);
            }
        }
        ans[C[i].second] = st.getmn(q-1,q);
    }
    return ans;
}
 
// int main(){
//     int n,q; cin >> n >> q;
//     vector<int>l(q),r(q),v(q),c(n);
//     for(int i = 0; i < n; i++) cin >> c[i];
//     for(int i = 0; i < q; i++){
//         cin >> l[i] >> r[i] >> v[i];
//     }
//     vector<int>ans = distribute_candies(c,l,r,v);
//     for(int x : ans){
//         cout << x << ' ';
//     }
// }

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1593 ms 21384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Execution timed out 5046 ms 19200 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -