oj.uz

답안 #801612

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
801612 2023-08-02T06:55:01 Z Khizri 사탕 분배 (IOI21_candies) C++17
100 / 100
 912 ms 46456 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=2e5+5;
struct st{
    ll mn=0,mx=0;
};
ll n,q,sum[mxn],lazy[4*mxn],arr[mxn],tree2[mxn];
vector<int>start[mxn],finish[mxn];
st tree[mxn*4];
void update2(int idx,ll val){
    while(idx<=q){
        tree2[idx]+=val;
        idx+=(idx&(-idx));
    }
}
ll query2(int idx){
    ll ans=0;
    while(idx>0){
        ans+=tree2[idx];
        idx-=(idx&(-idx));
    }
    return ans;
}
void relax(int node,int l,int r){
    if(l!=r){
        lazy[2*node]+=lazy[node];
        lazy[2*node+1]+=lazy[node];
    }
    tree[node].mn+=lazy[node];
    tree[node].mx+=lazy[node];
    lazy[node]=0;
}
void update(int node,int l,int r,int ql,int qr,int val){
    if(lazy[node]){
        relax(node,l,r);
    }
    if(r<ql||l>qr) return;
    if(ql<=l&&r<=qr){
        lazy[node]=val;
        relax(node,l,r);
        return;
    }
    int m=(l+r)/2;
    update(2*node,l,m,ql,qr,val);
    update(2*node+1,m+1,r,ql,qr,val);
    tree[node].mn=min(tree[2*node].mn,tree[2*node+1].mn);
    tree[node].mx=max(tree[2*node].mx,tree[2*node+1].mx);
}
st query(int node,int l,int r,int ql,int qr){
    if(l>qr||r<ql){
        st ans;
        ans.mn=INF;
        ans.mx=-INF;
        return ans;
    }
    if(lazy[node]){
        relax(node,l,r);
    }
    if(ql<=l&&r<=qr){
        return tree[node];
    }
    int m=(l+r)/2;
    st x=query(2*node,l,m,ql,qr);
    st y=query(2*node+1,m+1,r,ql,qr);
    st ans;
    ans.mn=min(x.mn,y.mn);
    ans.mx=max(x.mx,y.mx);
    return ans;
}
vector<int> distribute_candies(vector<int> c, vector<int> x, vector<int> y, vector<int> vq) {
    n = c.size();
    q=x.size();
    int sz=q;  
    for(int i=0;i<q;i++){
        arr[i+1]=vq[i];
    }
    for(int i=0;i<q;i++){
        start[x[i]].pb(i);
        finish[y[i]+1].pb(i);
    }
    vector<int>ans;
    for(int id=0;id<n;id++){
        for(int v:start[id]){
            update(1,1,q,v+1,q,vq[v]);
            update2(v+1,vq[v]);
        }
        for(int v:finish[id]){
            update(1,1,q,v+1,q,-vq[v]);
            update2(v+1,-vq[v]);
        }
        int lim=c[id];
        int pos=0;
        int l=1,r=q;
        while(l<=r){
            int m=(l+r)/2;
            st res=query(1,1,q,m,q);
            if(res.mx-res.mn>lim){
                l=m+1;
            }
            else{
                r=m-1;
            }
        }
        pos=l-1;
        ll mxx=0,mnn=0,sum=0;
        if(pos>0){
            st res=query(1,1,q,pos,q);
            mxx=res.mx;
            mnn=res.mn;
            sum=query2(pos);
        }
        else{
            st res=query(1,1,q,1,q);
            mxx=max(res.mx,mxx);
            mnn=min(res.mn,mnn);
            sum=0;
        }
        if(mxx-sum>lim){
            ans.pb(lim-(mxx-query2(q)));
        }
        else{
            ans.pb(query2(q)-mnn);
        }
    }
    return ans;
}

Compilation message

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:85:9: warning: unused variable 'sz' [-Wunused-variable]
   85 |     int sz=q;
      |         ^~

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 7 ms 9940 KB Output is correct
4 Correct 6 ms 9856 KB Output is correct
5 Correct 9 ms 10032 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 908 ms 44572 KB Output is correct
2 Correct 897 ms 43792 KB Output is correct
3 Correct 912 ms 43668 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9716 KB Output is correct
2 Correct 227 ms 35728 KB Output is correct
3 Correct 219 ms 15876 KB Output is correct
4 Correct 890 ms 45668 KB Output is correct
5 Correct 846 ms 46028 KB Output is correct
6 Correct 826 ms 46456 KB Output is correct
7 Correct 821 ms 45704 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 9692 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 101 ms 34092 KB Output is correct
4 Correct 180 ms 13800 KB Output is correct
5 Correct 535 ms 38032 KB Output is correct
6 Correct 526 ms 38700 KB Output is correct
7 Correct 572 ms 39300 KB Output is correct
8 Correct 560 ms 37852 KB Output is correct
9 Correct 598 ms 39384 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 7 ms 9940 KB Output is correct
4 Correct 6 ms 9856 KB Output is correct
5 Correct 9 ms 10032 KB Output is correct
6 Correct 908 ms 44572 KB Output is correct
7 Correct 897 ms 43792 KB Output is correct
8 Correct 912 ms 43668 KB Output is correct
9 Correct 5 ms 9716 KB Output is correct
10 Correct 227 ms 35728 KB Output is correct
11 Correct 219 ms 15876 KB Output is correct
12 Correct 890 ms 45668 KB Output is correct
13 Correct 846 ms 46028 KB Output is correct
14 Correct 826 ms 46456 KB Output is correct
15 Correct 821 ms 45704 KB Output is correct
16 Correct 4 ms 9692 KB Output is correct
17 Correct 4 ms 9684 KB Output is correct
18 Correct 101 ms 34092 KB Output is correct
19 Correct 180 ms 13800 KB Output is correct
20 Correct 535 ms 38032 KB Output is correct
21 Correct 526 ms 38700 KB Output is correct
22 Correct 572 ms 39300 KB Output is correct
23 Correct 560 ms 37852 KB Output is correct
24 Correct 598 ms 39384 KB Output is correct
25 Correct 5 ms 9684 KB Output is correct
26 Correct 175 ms 13932 KB Output is correct
27 Correct 255 ms 35444 KB Output is correct
28 Correct 859 ms 44284 KB Output is correct
29 Correct 884 ms 44680 KB Output is correct
30 Correct 857 ms 44796 KB Output is correct
31 Correct 855 ms 45064 KB Output is correct
32 Correct 867 ms 45372 KB Output is correct