oj.uz

Submission #443161

# Submission time Handle Problem Language Result Execution time Memory
443161 2021-07-09T23:43:41 Z RGBB Distributing Candies (IOI21_candies) C++17
100 / 100
 4429 ms 38636 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>pp;
typedef long long ll;
const int MAXN=200000;
int n,q;
ll sum,maxs[1<<19],mins[1<<19],lazy[1<<19];
vector<pp>query[MAXN];
void delazy(int a,int b,int c){
    maxs[c]+=lazy[c];
    mins[c]+=lazy[c];
    if(a!=b){
        lazy[2*c+1]+=lazy[c];
        lazy[2*c+2]+=lazy[c];
    }
    lazy[c]=0;
}
void update(int a,int b,int c,int be,int en,int v){
    delazy(a,b,c);
    if(a>b||a>en||b<be)return;
    if(a>=be&&b<=en){
        maxs[c]+=v;
        mins[c]+=v;
        if(a!=b){
            lazy[2*c+1]+=v;
            lazy[2*c+2]+=v;
        }
        return;
    }
    update(a,(a+b)/2,2*c+1,be,en,v);
    update((a+b)/2+1,b,2*c+2,be,en,v);
    maxs[c]=max(maxs[2*c+1],maxs[2*c+2]);
    mins[c]=min(mins[2*c+1],mins[2*c+2]);
}
ll maxq(int a,int b,int c,int be,int en){
    delazy(a,b,c);
    if(a>b||a>en||b<be)return LLONG_MIN;
    if(a>=be&&b<=en)return maxs[c];
    return max(maxq(a,(a+b)/2,2*c+1,be,en),maxq((a+b)/2+1,b,2*c+2,be,en));
}
ll minq(int a,int b,int c,int be,int en){
    delazy(a,b,c);
    if(a>b||a>en||b<be)return LLONG_MAX;
    if(a>=be&&b<=en)return mins[c];
    return min(minq(a,(a+b)/2,2*c+1,be,en),minq((a+b)/2+1,b,2*c+2,be,en));
}
ll range(int p){
    return maxq(0,q-1,0,p,q-1)-minq(0,q-1,0,p,q-1);
}
ll edge(int s){
    if(maxq(0,q-1,0,0,q-1)>s)return maxq(0,q-1,0,0,q-1)-s;
    else if(minq(0,q-1,0,0,q-1)<0)return minq(0,q-1,0,0,q-1);
    else return 0;
}
ll norm(int p,int s){
    if(maxq(0,q-1,0,p-1,q-1)>maxq(0,q-1,0,p,q-1))return minq(0,q-1,0,p,q-1);
    else if(minq(0,q-1,0,p-1,q-1)<minq(0,q-1,0,p,q-1))return maxq(0,q-1,0,p,q-1)-s;
}
int calc(int s){
    int lef=0;
    int rig=q-1;
    int mid=(lef+rig)/2;
    while(rig-lef>1){
        if(range(mid)>s)lef=mid;
        else rig=mid;
        mid=(lef+rig)/2;
    }
    if(range(lef)<=s)mid=lef;
    else mid=rig;
    ll lb=0;
    if(mid==0)lb=edge(s);
    else lb=norm(mid,s);
    return sum-lb;
}
vector<int>distribute_candies(vector<int>c,vector<int>l,vector<int>r,vector<int>v){
    vector<int>ret;
    n=c.size();
    q=v.size();
    for(int i=0;i<q;i++){
        query[l[i]].push_back({i,v[i]});
        if(r[i]!=n-1)query[r[i]+1].push_back({i,-v[i]});
    }
    sum=0;
    memset(maxs,0,sizeof(maxs));
    memset(mins,0,sizeof(mins));
    memset(lazy,0,sizeof(lazy));
    for(int i=0;i<n;i++){
        for(pp j:query[i]){
            sum+=j.second;
            update(0,q-1,0,j.first,q-1,j.second);
        }
        ret.push_back(calc(c[i]));
    }
    return ret;
}

Compilation message

candies.cpp: In function 'll norm(int, int)':
candies.cpp:59:1: warning: control reaches end of non-void function [-Wreturn-type]
   59 | }
      | ^

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17228 KB Output is correct
2 Correct 8 ms 17228 KB Output is correct
3 Correct 10 ms 17344 KB Output is correct
4 Correct 10 ms 17356 KB Output is correct
5 Correct 23 ms 17444 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4429 ms 31948 KB Output is correct
2 Correct 4223 ms 32012 KB Output is correct
3 Correct 4182 ms 32000 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17228 KB Output is correct
2 Correct 375 ms 26508 KB Output is correct
3 Correct 1387 ms 21088 KB Output is correct
4 Correct 4329 ms 31792 KB Output is correct
5 Correct 3928 ms 38088 KB Output is correct
6 Correct 4035 ms 38636 KB Output is correct
7 Correct 3839 ms 37780 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17228 KB Output is correct
2 Correct 11 ms 17228 KB Output is correct
3 Correct 193 ms 23720 KB Output is correct
4 Correct 1203 ms 20192 KB Output is correct
5 Correct 3567 ms 26940 KB Output is correct
6 Correct 3588 ms 31040 KB Output is correct
7 Correct 3781 ms 31728 KB Output is correct
8 Correct 3516 ms 30556 KB Output is correct
9 Correct 3904 ms 31772 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17228 KB Output is correct
2 Correct 8 ms 17228 KB Output is correct
3 Correct 10 ms 17344 KB Output is correct
4 Correct 10 ms 17356 KB Output is correct
5 Correct 23 ms 17444 KB Output is correct
6 Correct 4429 ms 31948 KB Output is correct
7 Correct 4223 ms 32012 KB Output is correct
8 Correct 4182 ms 32000 KB Output is correct
9 Correct 9 ms 17228 KB Output is correct
10 Correct 375 ms 26508 KB Output is correct
11 Correct 1387 ms 21088 KB Output is correct
12 Correct 4329 ms 31792 KB Output is correct
13 Correct 3928 ms 38088 KB Output is correct
14 Correct 4035 ms 38636 KB Output is correct
15 Correct 3839 ms 37780 KB Output is correct
16 Correct 9 ms 17228 KB Output is correct
17 Correct 11 ms 17228 KB Output is correct
18 Correct 193 ms 23720 KB Output is correct
19 Correct 1203 ms 20192 KB Output is correct
20 Correct 3567 ms 26940 KB Output is correct
21 Correct 3588 ms 31040 KB Output is correct
22 Correct 3781 ms 31728 KB Output is correct
23 Correct 3516 ms 30556 KB Output is correct
24 Correct 3904 ms 31772 KB Output is correct
25 Correct 10 ms 17228 KB Output is correct
26 Correct 1129 ms 21360 KB Output is correct
27 Correct 403 ms 29132 KB Output is correct
28 Correct 3779 ms 36356 KB Output is correct
29 Correct 3919 ms 36736 KB Output is correct
30 Correct 3945 ms 36904 KB Output is correct
31 Correct 3980 ms 37080 KB Output is correct
32 Correct 4121 ms 37212 KB Output is correct