oj.uz

Submission #853166

# Submission time Handle Problem Language Result Execution time Memory
853166 2023-09-23T14:56:35 Z abcvuitunggio Distributing Candies (IOI21_candies) C++17
100 / 100
 948 ms 33904 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 2 ms 8024 KB Output is correct
4 Correct 3 ms 7772 KB Output is correct
5 Correct 5 ms 7772 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 914 ms 33604 KB Output is correct
2 Correct 948 ms 33524 KB Output is correct
3 Correct 946 ms 33432 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 179 ms 27104 KB Output is correct
3 Correct 240 ms 12216 KB Output is correct
4 Correct 887 ms 33480 KB Output is correct
5 Correct 916 ms 33476 KB Output is correct
6 Correct 882 ms 33640 KB Output is correct
7 Correct 868 ms 33576 KB Output is correct

Subtask #4
29.0 / 29.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 96 ms 26376 KB Output is correct
4 Correct 278 ms 10956 KB Output is correct
5 Correct 703 ms 29500 KB Output is correct
6 Correct 687 ms 29648 KB Output is correct
7 Correct 677 ms 29628 KB Output is correct
8 Correct 717 ms 29632 KB Output is correct
9 Correct 723 ms 29572 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 2 ms 8024 KB Output is correct
4 Correct 3 ms 7772 KB Output is correct
5 Correct 5 ms 7772 KB Output is correct
6 Correct 914 ms 33604 KB Output is correct
7 Correct 948 ms 33524 KB Output is correct
8 Correct 946 ms 33432 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 179 ms 27104 KB Output is correct
11 Correct 240 ms 12216 KB Output is correct
12 Correct 887 ms 33480 KB Output is correct
13 Correct 916 ms 33476 KB Output is correct
14 Correct 882 ms 33640 KB Output is correct
15 Correct 868 ms 33576 KB Output is correct
16 Correct 2 ms 7516 KB Output is correct
17 Correct 2 ms 7516 KB Output is correct
18 Correct 96 ms 26376 KB Output is correct
19 Correct 278 ms 10956 KB Output is correct
20 Correct 703 ms 29500 KB Output is correct
21 Correct 687 ms 29648 KB Output is correct
22 Correct 677 ms 29628 KB Output is correct
23 Correct 717 ms 29632 KB Output is correct
24 Correct 723 ms 29572 KB Output is correct
25 Correct 2 ms 7516 KB Output is correct
26 Correct 241 ms 10996 KB Output is correct
27 Correct 161 ms 27112 KB Output is correct
28 Correct 879 ms 33628 KB Output is correct
29 Correct 936 ms 33552 KB Output is correct
30 Correct 924 ms 33516 KB Output is correct
31 Correct 911 ms 33576 KB Output is correct
32 Correct 905 ms 33904 KB Output is correct