제출 #1062217

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1062217		vjudge1	사탕 분배 (IOI21_candies)	C++17	0 / 100	195 ms	42728 KiB

candies

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33