oj.uz

Submission #1062217

# Submission time Handle Problem Language Result Execution time Memory
1062217 2024-08-16T21:52:48 Z vjudge1 Distributing Candies (IOI21_candies) C++17
0 / 100
 195 ms 42728 KB 
#include <bits/stdc++.h>
using namespace std;
#define ft first
#define sd second
#define ll long long
#define ti(x) stoi(x)
#define ts(x) to_string(x)
#define dbg(x) cout<<#x<<" : "<<x<<" "
ll n=200005;
vector<ll> t(4*n), v2(4*n, 0), v3(4*n, 0);
inline void update(ll v, ll tl, ll tr, ll pos, ll val){
if(tl==tr){
t[v]=val;
v2[v]=max(0LL, val);
v3[v]=max(0LL, val);
}else{
ll tm=(tl+tr)/2;
if(pos<=tm)update(v*2, tl, tm, pos, val);
else update(v*2+1, tm+1, tr, pos, val);
t[v]=t[v*2]+t[v*2+1];
v2[v]=max(v2[v*2], t[v*2]+v2[v*2+1]);
v3[v]=min(v3[v*2], t[v*2]+v3[v*2+1]);
}
}
inline ll query(ll v, ll tl, ll tr, ll val){
if(tl==tr){
if(t[v]>val)return val;
if(t[v]<0)return 0;
return val;
}
ll tm=(tl+tr)/2;
if(v2[v*2+1]-v3[v*2+1])return query(v*2+1, tm+1, tr, val);
ll o=query(v*2, tl, tm, val);
if(o+v2[v*2+1]>val)return val-(v2[v*2+1]-t[v*2+1]);
if(o+v3[v*2+1]<0)return t[v*2+1]-v3[v*2+1];
return o+t[v];
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v){
vector<vector<ll>> v5(c.size()+1);
for(int i=0; i<l.size(); i++){
v5[l[i]].push_back(i);
v5[r[i]+1].push_back(-i);
}
vector<int> o1(c.size());
for(int i=0; i<c.size(); i++){
for(auto y: v5[i]){
if(y<0)update(1, 0, c.size(), -y, 0);
else update(1, 0, c.size(), y, v[y]);
}
o1[i]=query(1, 0, c.size(), c[i]);
}
return o1;
}

Compilation message

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:40:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 | for(int i=0; i<l.size(); i++){
      |              ~^~~~~~~~~
candies.cpp:45:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 | for(int i=0; i<c.size(); i++){
      |              ~^~~~~~~~~

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

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