oj.uz

Submission #443166

# Submission time Handle Problem Language Result Execution time Memory
443166 2021-07-10T00:52:11 Z RGBB Distributing Candies (IOI21_candies) C++17
100 / 100
 2706 ms 32100 KB 
#include <iostream>
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
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 update(int a,int b,int c,int be,int en,int v){
    if(lazy[c]!=0){
        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;
    }
    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){
    if(lazy[c]!=0){
        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;
    }
    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){
    if(lazy[c]!=0){
        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;
    }
    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){
    ll mx=maxq(0,q-1,0,0,q-1);
    if(mx>s)return mx-s;
    ll mn=minq(0,q-1,0,0,q-1);
    if(mn<0)return mn;
    else return 0;
}
ll norm(int p,int s){
    ll mx=maxq(0,q-1,0,p,q-1);
    ll mn=minq(0,q-1,0,p,q-1);
    if(maxq(0,q-1,0,p-1,q-1)>mx)return mn;
    else if(minq(0,q-1,0,p-1,q-1)<mn)return mx-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:79:1: warning: control reaches end of non-void function [-Wreturn-type]
   79 | }
      | ^

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17228 KB Output is correct
2 Correct 9 ms 17228 KB Output is correct
3 Correct 10 ms 17356 KB Output is correct
4 Correct 11 ms 17344 KB Output is correct
5 Correct 18 ms 17572 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2671 ms 31796 KB Output is correct
2 Correct 2706 ms 31716 KB Output is correct
3 Correct 2588 ms 31940 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 350 ms 26552 KB Output is correct
3 Correct 631 ms 21156 KB Output is correct
4 Correct 2334 ms 31776 KB Output is correct
5 Correct 2459 ms 31824 KB Output is correct
6 Correct 2596 ms 31940 KB Output is correct
7 Correct 2492 ms 32100 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 9 ms 17228 KB Output is correct
3 Correct 147 ms 23604 KB Output is correct
4 Correct 594 ms 20032 KB Output is correct
5 Correct 1871 ms 26992 KB Output is correct
6 Correct 1842 ms 26880 KB Output is correct
7 Correct 1893 ms 27028 KB Output is correct
8 Correct 1823 ms 27204 KB Output is correct
9 Correct 1906 ms 26892 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 9 ms 17228 KB Output is correct
3 Correct 10 ms 17356 KB Output is correct
4 Correct 11 ms 17344 KB Output is correct
5 Correct 18 ms 17572 KB Output is correct
6 Correct 2671 ms 31796 KB Output is correct
7 Correct 2706 ms 31716 KB Output is correct
8 Correct 2588 ms 31940 KB Output is correct
9 Correct 9 ms 17228 KB Output is correct
10 Correct 350 ms 26552 KB Output is correct
11 Correct 631 ms 21156 KB Output is correct
12 Correct 2334 ms 31776 KB Output is correct
13 Correct 2459 ms 31824 KB Output is correct
14 Correct 2596 ms 31940 KB Output is correct
15 Correct 2492 ms 32100 KB Output is correct
16 Correct 9 ms 17228 KB Output is correct
17 Correct 9 ms 17228 KB Output is correct
18 Correct 147 ms 23604 KB Output is correct
19 Correct 594 ms 20032 KB Output is correct
20 Correct 1871 ms 26992 KB Output is correct
21 Correct 1842 ms 26880 KB Output is correct
22 Correct 1893 ms 27028 KB Output is correct
23 Correct 1823 ms 27204 KB Output is correct
24 Correct 1906 ms 26892 KB Output is correct
25 Correct 10 ms 17228 KB Output is correct
26 Correct 588 ms 20172 KB Output is correct
27 Correct 345 ms 26564 KB Output is correct
28 Correct 2441 ms 31848 KB Output is correct
29 Correct 2596 ms 31688 KB Output is correct
30 Correct 2643 ms 31800 KB Output is correct
31 Correct 2539 ms 31676 KB Output is correct
32 Correct 2635 ms 31748 KB Output is correct