oj.uz

답안 #814390

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
814390 2023-08-08T07:12:49 Z alvingogo 사탕 분배 (IOI21_candies) C++17
27 / 100
 372 ms 35160 KB 
#include "candies.h"
#include <bits/stdc++.h>
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

int c;
struct ST{
    struct no{
        int l,r,k;
        no(int a,int b,int c){
            l=a;
            r=b;
            k=c;
        }
        int get(int x){
            if(x<=l){
                return k;
            }
            return k+(min(x,r))-l;
        }
    };
    vector<no> st;
    void init(int x){
        st.resize(4*x,{0,c,0});
    }
    void pull(int v){
        no& a=st[2*v+1];
        no& b=st[2*v+2];
        no& c=st[v];
        int d=b.get(a.k),e=b.get(a.k+a.r-a.l);
        c.k=d;
        if(e==d){
            c.l=a.l;
        }
        else{
            c.l=a.l+max(0,(b.l-a.k));
        }
        c.r=c.l+(e-d);
    }
    void update(int v,int L,int R,int p,int x){
        if(L==R){
            if(x==0){
                st[v].l=0;
                st[v].r=c;
                st[v].k=0;
            }
            else if(x<0){
                st[v].l-=x;
            }
            else{
                st[v].r-=x;
                st[v].k+=x;
            }
            return;
        }
        int m=(L+R)/2;
        if(p<=m){
            update(2*v+1,L,m,p,x);
        }
        else{
            update(2*v+2,m+1,R,p,x);
        }
        pull(v);
    }
    int query(int x){
        return st[0].get(x);
    }
}st;
vector<int> distribute_candies(vector<int> w, vector<int> l,
                                    vector<int> r, vector<int> v) {
    int n=w.size();
    c=w[0];
    vector<int> ans(n);
    int q=l.size();
    st.init(q);
    vector<vector<pair<int,int> > > upd(n),del(n);
    for(int i=0;i<q;i++){
        if(abs(v[i])>c){
            if(v[i]<0){
                v[i]=-c;
            }
            else{
                v[i]=c;
            }
        }
        upd[l[i]].push_back({i,v[i]});
        del[r[i]].push_back({i,v[i]});
    }
    for(int i=0;i<n;i++){
        for(auto h:upd[i]){
            st.update(0,0,q-1,h.fs,h.sc);
        }
        ans[i]=st.query(0);
        for(auto h:del[i]){
            st.update(0,0,q-1,h.fs,0);
        }
    }
    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 Incorrect 289 ms 34084 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 187 ms 19948 KB Output is correct
3 Correct 61 ms 12844 KB Output is correct
4 Correct 330 ms 34712 KB Output is correct
5 Correct 366 ms 34904 KB Output is correct
6 Correct 351 ms 35040 KB Output is correct
7 Correct 372 ms 35160 KB Output is correct

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 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 -