oj.uz

Submission #1048479

# Submission time Handle Problem Language Result Execution time Memory
1048479 2024-08-08T07:51:28 Z boyliguanhan Distributing Candies (IOI21_candies) C++17
100 / 100
 174 ms 36176 KB 
#include "candies.h"

#include<bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
int C,Kof[200100];
VI ans;
struct segtree{
    struct DATA{
        long long prfmn,prfmx,sum;
        DATA(long long k){
            prfmn=min(0ll,k),
            prfmx=max(0ll,k),sum=k;
        }
        DATA(){
            prfmn=prfmx=sum=0;
        }
        DATA(DATA a,DATA b){ sum=a.sum+b.sum;
            prfmn=min(a.prfmn,b.prfmn+a.sum);
            prfmx=max(a.prfmx,b.prfmx+a.sum);
        }
    } T[1<<19];
    void Add(int i,int l,int r,int p,int v){
        if(l==r) return void(T[i]=DATA(T[i].sum+v));
        if(l+r>>1>=p) Add(i*2,l,l+r>>1,p,v);
        else Add(i*2+1,l+r+2>>1,r,p,v);
        T[i]=DATA(T[i*2],T[i*2+1]);
    }
    int getans(DATA k,int b){
        return (b?k.prfmx>C:k.prfmn>=-C)?C+k.sum-k.prfmx:k.sum-k.prfmn;
    }
    int Qry(int i,int l,int r,DATA prv){
        if(l==r) return getans(DATA(T[i],prv),T[i].sum>=0);
        DATA c=DATA(T[i*2+1],prv);
        if(c.prfmx-c.prfmn<=C)
            return Qry(i*2,l,l+r>>1,c);
        return Qry(i*2+1,l+r+2>>1,r,prv);
    }
} seg;
vector<pair<int,int>> stuf[200100];
VI distribute_candies(VI c,VI l,VI r,VI v) {
    int n=c.size(),q=l.size();
    for(int i=0;i<q;i++)
        stuf[l[i]].push_back({i+1,v[i]}),
        stuf[r[i]+1].push_back({i+1,-v[i]});
    for(int i=0;i<n;i++){
        for(auto[a,b]:stuf[i])
            seg.Add(1,0,q,a,b);
        C=c[i];
        ans.push_back(seg.Qry(1,0,q,seg.T[0]));
    }
    return ans;
}

Compilation message

candies.cpp: In member function 'void segtree::Add(int, int, int, int, int)':
candies.cpp:25:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |         if(l+r>>1>=p) Add(i*2,l,l+r>>1,p,v);
      |            ~^~
candies.cpp:25:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |         if(l+r>>1>=p) Add(i*2,l,l+r>>1,p,v);
      |                                 ~^~
candies.cpp:26:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |         else Add(i*2+1,l+r+2>>1,r,p,v);
      |                        ~~~^~
candies.cpp: In member function 'int segtree::Qry(int, int, int, segtree::DATA)':
candies.cpp:36:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |             return Qry(i*2,l,l+r>>1,c);
      |                              ~^~
candies.cpp:37:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |         return Qry(i*2+1,l+r+2>>1,r,prv);
      |                          ~~~^~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 17240 KB Output is correct
2 Correct 2 ms 17244 KB Output is correct
3 Correct 3 ms 17500 KB Output is correct
4 Correct 3 ms 17500 KB Output is correct
5 Correct 3 ms 17500 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 35012 KB Output is correct
2 Correct 163 ms 34504 KB Output is correct
3 Correct 167 ms 34500 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17240 KB Output is correct
2 Correct 92 ms 28200 KB Output is correct
3 Correct 37 ms 23224 KB Output is correct
4 Correct 169 ms 35668 KB Output is correct
5 Correct 166 ms 35784 KB Output is correct
6 Correct 173 ms 36176 KB Output is correct
7 Correct 168 ms 35840 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17244 KB Output is correct
2 Correct 2 ms 17244 KB Output is correct
3 Correct 46 ms 26896 KB Output is correct
4 Correct 35 ms 21620 KB Output is correct
5 Correct 86 ms 30700 KB Output is correct
6 Correct 92 ms 30896 KB Output is correct
7 Correct 96 ms 31156 KB Output is correct
8 Correct 87 ms 30388 KB Output is correct
9 Correct 84 ms 31488 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 17240 KB Output is correct
2 Correct 2 ms 17244 KB Output is correct
3 Correct 3 ms 17500 KB Output is correct
4 Correct 3 ms 17500 KB Output is correct
5 Correct 3 ms 17500 KB Output is correct
6 Correct 159 ms 35012 KB Output is correct
7 Correct 163 ms 34504 KB Output is correct
8 Correct 167 ms 34500 KB Output is correct
9 Correct 3 ms 17240 KB Output is correct
10 Correct 92 ms 28200 KB Output is correct
11 Correct 37 ms 23224 KB Output is correct
12 Correct 169 ms 35668 KB Output is correct
13 Correct 166 ms 35784 KB Output is correct
14 Correct 173 ms 36176 KB Output is correct
15 Correct 168 ms 35840 KB Output is correct
16 Correct 3 ms 17244 KB Output is correct
17 Correct 2 ms 17244 KB Output is correct
18 Correct 46 ms 26896 KB Output is correct
19 Correct 35 ms 21620 KB Output is correct
20 Correct 86 ms 30700 KB Output is correct
21 Correct 92 ms 30896 KB Output is correct
22 Correct 96 ms 31156 KB Output is correct
23 Correct 87 ms 30388 KB Output is correct
24 Correct 84 ms 31488 KB Output is correct
25 Correct 2 ms 17244 KB Output is correct
26 Correct 44 ms 21472 KB Output is correct
27 Correct 94 ms 27984 KB Output is correct
28 Correct 170 ms 35012 KB Output is correct
29 Correct 158 ms 35012 KB Output is correct
30 Correct 158 ms 35148 KB Output is correct
31 Correct 172 ms 35220 KB Output is correct
32 Correct 174 ms 35460 KB Output is correct