답안 #939739

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
939739 2024-03-06T17:22:41 Z IS_Rushdi 사탕 분배 (IOI21_candies) C++17
컴파일 오류
0 ms 0 KB
#include<bits/stdc++.h>
using namespace std;
typedef int64_t i64;
#define VII vector<int>
 
 
struct seg{
    vector<i64>mx,mn,cmx,cmn,op,st;
    int sz = 1;
    void build(int x,int lx,int rx){
        if(rx-lx == 1){
            cmx[x] = cmn[x] = 1;
            return;
        }
        int m = (lx+rx)/2;
        build(x*2+1,lx,m);
        build(x*2+2,m,rx);
        cmx[x] = cmx[x*2+1] + cmx[x*2+2];
        cmn[x] = cmn[x*2+1] + cmn[x*2+2];
    }
    seg(int n){
        while(sz < n) sz*=2;
        op.assign(sz*2,0ll);
        mx.assign(sz*2,0ll);
        mn.assign(sz*2,0ll);
        cmx.assign(sz*2,0ll);
        cmn.assign(sz*2,0ll);
        st.assign(sz*2,2e9);
        build(0,0,sz);
    }
    void push(int x,int lx,int rx){
        if(rx-lx == 1) return;
        op[x*2+1] += op[x];
        op[x*2+2] += op[x];
        int m = (lx+rx)/2;
        NQF(x*2+1,lx,m);
        NQF(x*2+2,m,rx);
        op[x] = 0;
    }
    void NQF(int x,int lx,int rx){
        if(rx-lx == 1){
            cmx[x] = cmn[x] = 1;
            mn[x] = mx[x] = op[x];
            return;
        }
        
        mx[x] = max(mx[x*2+1],mx[x*2+2]) + op[x];
        mn[x] = min(mn[x*2+1],mn[x*2+2]) + op[x];
        
        if(mx[x*2+1] > mx[x*2+2]) cmx[x] = cmx[x*2+1];
        else if(mx[x*2+2] > mx[x*2+1]) cmx[x] = cmx[x*2+2];
        else cmx[x] = cmx[x*2+1] + cmx[x*2+2];
        
        if(mn[x*2+1] < mn[x*2+2]) cmn[x] = cmn[x*2+1];
        else if(mn[x*2+2] < mn[x*2+1]) cmn[x] = cmn[x*2+2];
        else cmn[x] = cmn[x*2+1] + cmn[x*2+2];
    }
    void update(int l,int r,int v,int x=0,int lx=0,int rx=-1){
        if(rx == -1) rx = sz;
        if(rx <= l || lx >= r) return;
        NQF(x,lx,rx);
        push(x,lx,rx);
        if(rx <= r && lx >= l){
            mn[x] += v;
            mx[x] += v;
            op[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);
        NQF(x,lx,rx);
        push(x,lx,rx);
    }
    void checkMAX(int x=0,int lx=0,int rx=-1){
        if(rx == -1) rx = sz;
        NQF(x,lx,rx);
        push(x,lx,rx);
        int v = st[x];
        if(mx[x] > v){
            if(cmx[x] == (rx-lx)){
                op[x] -= mx[x]-v;
            }else{
                int m = (lx+rx)/2;
                checkMAX(x*2+1,lx,m);
                checkMAX(x*2+2,m,rx);
            }
        }
 
        NQF(x,lx,rx);
        push(x,lx,rx);
    }
    void checkMIN(int x=0,int lx=0,int rx=-1){
        if(rx == -1) rx = sz;
        NQF(x,lx,rx);
        push(x,lx,rx);
        if(mn[x] < 0){
            if(cmx[x] == rx-lx){
                op[x] -= mn[x];
                push(x,lx,rx);
            }else{
                int m = (lx+rx)/2;
                checkMIN(x*2+1,lx,m);
                checkMIN(x*2+2,m,rx);
            }
        }
        NQF(x,lx,rx);
        push(x,lx,rx);
    }
    int get(int i,int x=0,int lx=0,int rx=-1){
        if(rx == -1) rx = sz;
        if(rx-lx == 1) return op[x];
        NQF(x,lx,rx);
        push(x,lx,rx);
        int m = (lx+rx)/2;
        if(i < m) return op[x] + get(i,x*2+1,lx,m);
        else return op[x] + get(i,x*2+2,m,rx);
    }
    void wow(vector<int>&arr,int x=0,int lx=0,int rx=-1){
        if(rx == -1) rx = sz;
        if(rx-lx == 1){
            st[x] = arr[lx];
            return;
        }
        int m = (lx+rx)/2;
        wow(arr,x*2+1,lx,m);
        wow(arr,x*2+2,m,rx);
        st[x] = min(st[x*2+1],st[x*2+2]);
    }
};
VII distribute_candies(VII c,VII l ,VII r,VII v) {
    int n = c.size();
    int q = l.size();
    seg st(n+1);
    st.wow(c);
    for(int i = 0; i < q; i++){
        st.update(l[i],r[i]+1,v[i]);
        if(v[i] > 0){
            st.checkMAX();
        }else{
            st.checkMIN();
        }
    }
    
    vector<int>ans;
    for(int i = 0; i < n; i++) ans.push_back(st.get(i));
    return ans;
}
 
int main(){
    int n;
    assert(1 == scanf("%d", &n));
    std::vector<int> c(n);
    for(int i = 0; i < n; ++i) {
        assert(scanf("%d", &c[i]) == 1);
    }

    int q;
    assert(1 == scanf("%d", &q));
    std::vector<int> l(q), r(q), v(q);
    for(int i = 0; i < q; ++i) {
        assert(scanf("%d %d %d", &l[i], &r[i], &v[i]) == 3);
    }

    std::vector<int> ans = distribute_candies(c, l, r, v);

    for(int i = 0; i < n; ++i) {
        if (i > 0) {
            printf(" ");
        }
        printf("%d", ans[i]);
    }
    printf("\n");
    fclose(stdout);
    return 0;
}

Compilation message

/usr/bin/ld: /tmp/cccHn5wA.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc6LZybA.o:candies.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status