oj.uz

Submission #853165

# Submission time Handle Problem Language Result Execution time Memory
853165 2023-09-23T14:56:35 Z abcvuitunggio Distributing Candies (IOI21_candies) C++17
100 / 100
 987 ms 33792 KB 
#include "candies.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair <int, int> pll;
int n,q;
vector <int32_t> ve[200001],res;
int lazy[900001],pos;
pll st[900001];
pll combine(pll a, pll b){
    return {min(a.first,b.first),max(a.second,b.second)};
}
void down(int node, int l, int r){
    if (!lazy[node]||l==r)
        return;
    st[node<<1].first+=lazy[node];
    st[node<<1].second+=lazy[node];
    lazy[node<<1]+=lazy[node];
    st[node<<1|1].first+=lazy[node];
    st[node<<1|1].second+=lazy[node];
    lazy[node<<1|1]+=lazy[node];
    lazy[node]=0;
}
void update(int node, int l, int r, int u, int v, int val){
    if (l>v||r<u||l>r||u>v)
        return;
    if (l>=u&&r<=v){
        st[node].first+=val;
        st[node].second+=val;
        lazy[node]+=val;
        return;
    }
    down(node,l,r);
    int mid=(l+r)>>1;
    update(node<<1,l,mid,u,v,val);
    update(node<<1|1,mid+1,r,u,v,val);
    st[node]=combine(st[node<<1],st[node<<1|1]);
}
pll get(int node, int l, int r, int u, int v){
    if (l>v||r<u|l>r||u>v)
        return {1e18,-1e18};
    if (l>=u&&r<=v)
        return st[node];
    down(node,l,r);
    int mid=(l+r)>>1;
    return combine(get(node<<1,l,mid,u,v),get(node<<1|1,mid+1,r,u,v));
}
vector <int32_t> distribute_candies(vector <int32_t> c, vector <int32_t> l, vector <int32_t> r, vector <int32_t> v){
    n=c.size();
    q=l.size();
    update(1,0,q+1,0,q+1,1e18);
    update(1,0,q+1,1,q+1,-1e18);
    for (int i=0;i<q;i++){
        ve[l[i]].push_back(i+1);
        ve[r[i]+1].push_back(-i-1);
    }
    for (int i=0;i<n;i++){
        for (int j:ve[i]){
            pos+=(j>0?v[j-1]:-v[-j-1]);
            update(1,0,q+1,abs(j)+1,q+1,(j>0?v[j-1]:-v[-j-1]));
        }
        int l=0,r=q+1;
        int kq=-1;
        while (l<=r){
            int mid=(l+r)>>1;
            auto [mn,mx]=get(1,0,q+1,mid,q+1);
            if (mx-mn>=c[i]){
                kq=(mid&&v[mid-1]>0?c[i]-mx+pos:pos-mn);
                l=mid+1;
            }
            else
                r=mid-1;
        }
        res.push_back(kq);
    }
    return res;
}

Compilation message

candies.cpp: In function 'pll get(long long int, long long int, long long int, long long int, long long int)':
candies.cpp:40:15: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   40 |     if (l>v||r<u|l>r||u>v)
      |              ~^~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7516 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 3 ms 7768 KB Output is correct
4 Correct 3 ms 8024 KB Output is correct
5 Correct 6 ms 7824 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 931 ms 33476 KB Output is correct
2 Correct 942 ms 33560 KB Output is correct
3 Correct 987 ms 33600 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7516 KB Output is correct
2 Correct 175 ms 26960 KB Output is correct
3 Correct 242 ms 12256 KB Output is correct
4 Correct 891 ms 33440 KB Output is correct
5 Correct 978 ms 33456 KB Output is correct
6 Correct 899 ms 33428 KB Output is correct
7 Correct 905 ms 33792 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7768 KB Output is correct
3 Correct 92 ms 26412 KB Output is correct
4 Correct 247 ms 11108 KB Output is correct
5 Correct 723 ms 29620 KB Output is correct
6 Correct 690 ms 29584 KB Output is correct
7 Correct 673 ms 29472 KB Output is correct
8 Correct 716 ms 29636 KB Output is correct
9 Correct 724 ms 29620 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7516 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 3 ms 7768 KB Output is correct
4 Correct 3 ms 8024 KB Output is correct
5 Correct 6 ms 7824 KB Output is correct
6 Correct 931 ms 33476 KB Output is correct
7 Correct 942 ms 33560 KB Output is correct
8 Correct 987 ms 33600 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 175 ms 26960 KB Output is correct
11 Correct 242 ms 12256 KB Output is correct
12 Correct 891 ms 33440 KB Output is correct
13 Correct 978 ms 33456 KB Output is correct
14 Correct 899 ms 33428 KB Output is correct
15 Correct 905 ms 33792 KB Output is correct
16 Correct 2 ms 7512 KB Output is correct
17 Correct 2 ms 7768 KB Output is correct
18 Correct 92 ms 26412 KB Output is correct
19 Correct 247 ms 11108 KB Output is correct
20 Correct 723 ms 29620 KB Output is correct
21 Correct 690 ms 29584 KB Output is correct
22 Correct 673 ms 29472 KB Output is correct
23 Correct 716 ms 29636 KB Output is correct
24 Correct 724 ms 29620 KB Output is correct
25 Correct 2 ms 7516 KB Output is correct
26 Correct 251 ms 11108 KB Output is correct
27 Correct 171 ms 27116 KB Output is correct
28 Correct 907 ms 33524 KB Output is correct
29 Correct 914 ms 33576 KB Output is correct
30 Correct 902 ms 33412 KB Output is correct
31 Correct 915 ms 33628 KB Output is correct
32 Correct 858 ms 33644 KB Output is correct