Submission #940728

# Submission time Handle Problem Language Result Execution time Memory
940728 2024-03-07T14:23:32 Z 7mody Distributing Candies (IOI21_candies) C++17
Compilation error
0 ms 0 KB
// #include "candies.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 

struct seg{
    int sz = 1; vector<ll>mn,mx,sum,op,add;
    seg(int n){
        while(sz < n) sz*=2;
        mn.assign(sz*2,0ll);
        mx.assign(sz*2,0ll);
        op.assign(sz*2,0ll);
        sum.assign(sz*2,0ll);
        add.assign(sz*2,0ll);
    }
    void push(int x,int lx,int rx){
        if(rx-lx == 1) return;
        int m = (lx+rx)/2;
        add[x*2+1] += add[x];
        add[x*2+2] += add[x];
        sum[x*2+1] += add[x] * (m-lx);
        sum[x*2+2] += add[x] * (rx-m);
        sum[x] = sum[x*2+1] + sum[x*2+2];
        add[x] = 0;
    }
    void update(int l,int r,ll v,int x=0,int lx=0,int rx=-1){
        if(rx == -1){r++;rx=sz;}
        push(x,lx,rx);
        if(rx <= l || lx >= r) return;
        if(rx <= r && lx >= l){
            op[x] += v;
            mn[x] += v;
            mx[x] += v;
            add[x] += v;
            sum[x] += (rx-lx)*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];
        sum[x] = sum[x*2+1] + sum[x*2+2];}
    ll getMIN(int l,int r,int x=0,int lx=0,int rx=-1){
        if(rx == -1){rx=sz;r++;}
        if(rx <= l || lx >= r) return 1e15;
        if(rx <= r && lx >= l) return mn[x];
        int m = (lx+rx)/2;
        return min(getMIN(l,r,x*2+1,lx,m),getMIN(l,r,x*2+2,m,rx)) + op[x];}
    ll getMAX(int l,int r,int x=0,int lx=0,int rx=-1){
        if(rx == -1){rx=sz;r++;}
        if(rx <= l || lx >= r) return -1e15;
        if(rx <= r && lx >= l) return mx[x];
        int m = (lx+rx)/2;
        return max(getMAX(l,r,x*2+1,lx,m),getMAX(l,r,x*2+2,m,rx)) + op[x];}
    ll getSUM(int l,int r,int x=0,int lx=0,int rx=-1){
        if(rx == -1){rx=sz;r++;}
        push(x,lx,rx);
        if(rx <= l || lx >= r) return 0ll;
        if(rx <= r && lx >= l) return sum[x];
        int m = (lx+rx)/2;
        return getSUM(l,r,x*2+1,lx,m)+getSUM(l,r,x*2+2,m,rx);}};

int n, m;

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v){
    n = c.size();
    m = r.size();
    vector<int> s(n);

    vector<vector<int>> L(n),R(n);

    for(int i=0; i < m;i++){
        L[l[i]].push_back(i);
        R[r[i]].push_back(i);
    }

    seg st(m + 2);
    // - 0 ,
    for(int i=0; i < n;i++){

        for(int x : L[i]) st.update(x + 2, m + 1, v[x]);

        int l = 0;
        int r = m;
        int id = -1;

        ll cmx, cmn;

        while(l <= r){
            int mid = (l+r)/2;
            ll a,b;
            a = st.getMAX(mid + 1, m + 1), b = st.getMIN(mid + 1, m + 1);
            if(a - b >= c[i]){
                l = mid+1;
                id = mid;
                cmx = a;
                cmn = b;
            } else r = mid-1;
        }

        // cout << cmx << ' ' << cmn << endl;
        if(id == -1){
            l = 0;
            r = m;
            int limit = st.getMIN(1, m + 1);
            while(l <= r){
                int mid = (l + r)/2;
                if(st.getMIN(mid + 1, m + 1) == limit){
                    l = mid + 1;
                    id = mid;
                } else r = mid - 1;
            } id++;
            s[i] = st.getSUM(m+1,m+1) - st.getSUM(id,id);
            // s[i] = st.getSUM(m+1,m+1) - cmn;
            for(int x : R[i]) st.update(x + 2, m + 1, -v[x]);
            continue;
        }
        int cond = 0;
        ll curr;
        id++;
        if(cmx == st.getMAX(id + 1, m + 1)) cond = 1, curr = cmx;
        else cond = 0, curr = cmn;
        if(cond){
            int l = id - 1;
            int r = m;
            while(l <= r){
                int mid = (l+r)/2;
                if(st.getMAX(mid + 1, m + 1) == curr){
                    id = mid;
                    l = mid + 1;
                } else r = mid - 1;
            }
            id++;
            // cout << st.getSUM(id + 1, m + 1) << ' ' << id << ' ';
            s[i] = c[i] - (st.getSUM(id, id) - st.getSUM(m+1,m+1));
        } else{
            int l = id - 1;
            int r = m;
            while(l <= r){
                int mid = (l+r)/2;
                if(st.getMIN(mid + 1, m + 1) == curr){
                    id = mid;
                    l = mid + 1;
                } else r = mid - 1;
            }
            id++;
            s[i] = st.getSUM(m+1,m+1) - st.getSUM(id, id);
        }
        for(int x : R[i]) st.update(x + 2, m + 1, -v[x]);
    }
    return s;
}

void solve(){
    cin >> n;
    vector<int> c(n);
    for(int i=0; i < n;i++) cin >> c[i];
    int q; cin >> q;
    vector<int> l(q),r(q),v(q);
    for(int i=0; i < q;i++) cin >> l[i];
    for(int i=0; i < q;i++) cin >> r[i];
    for(int i=0; i < q;i++) cin >> v[i];
    vector<int> ans = distribute_candies(c,l,r,v); cout << endl;
    for(int x : ans) cout << x << ' '; cout << endl;
}

int32_t main(){
    ios::sync_with_stdio(false);    
    cin.tie();
    cout.tie();
    int t=1;
    // cin >> t;
    while(t--){
        // cout << t <<  ":\n";
        solve();
    }
}

Compilation message

candies.cpp: In function 'void solve()':
candies.cpp:166:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  166 |     for(int x : ans) cout << x << ' '; cout << endl;
      |     ^~~
candies.cpp:166:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  166 |     for(int x : ans) cout << x << ' '; cout << endl;
      |                                        ^~~~
/usr/bin/ld: /tmp/ccD5sqIn.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccEiRUCo.o:candies.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status