oj.uz

Submission #853161

# Submission time Handle Problem Language Result Execution time Memory
853161 2023-09-23T14:51:27 Z abcvuitunggio Distributing Candies (IOI21_candies) C++17
8 / 100
 908 ms 33648 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==0?pos:(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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Incorrect 2 ms 7512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 882 ms 33648 KB Output is correct
2 Correct 874 ms 33432 KB Output is correct
3 Correct 908 ms 33424 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 7512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 3 ms 7512 KB Output is correct
3 Incorrect 80 ms 26476 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Incorrect 2 ms 7512 KB Output isn't correct
3 Halted 0 ms 0 KB -