# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1167750 | tgirolami09 | Snowball (JOI21_ho_t2) | C++20 | 88 ms | 9844 KiB |
#include <iostream>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;
struct segment{
int id; //Determine the snowballs before and after
int length; //For calculations
bool operator<(const segment& other)const{
return length<other.length;
}
};
void printSeg(segment s){
printf("%lld : length %lld\n",s.id,s.length);
}
void printVec(vector<segment> v){
for (segment s : v){
printSeg(s);
}
}
void printSol(vector<int> v){
for (int i : v){
printf("%lld\n",i);
}
}
signed main(){
int nbSnowballs,nbDays;
scanf("%lld %lld",&nbSnowballs,&nbDays);
vector<int> snowballPositions;
int pos;
for (int i = 0;i<nbSnowballs;++i){
scanf("%lld",&pos);
snowballPositions.push_back(pos);
}
vector<segment> segments;
for (int i = 1;i<nbSnowballs;++i){
segments.push_back({i-1,snowballPositions[i]-snowballPositions[i-1]});
}
sort(segments.begin(),segments.end());
int minPos = 0;
int maxPos = 0;
int wind;
int currentWind = 0;
int firstPossible = 0;
vector<int> answer(nbSnowballs,0);
for (int i = 0;i<nbDays;++i){
scanf("%lld",&wind);
currentWind+=wind;
if (currentWind>maxPos){
//printf("New maximum to the right %lld\n",currentWind);
for (int idx = firstPossible;idx<nbSnowballs-1;++idx){
//Look at the smallest segment that can still alocate
if (segments[idx].length>currentWind-minPos){
//Is the segment larger than the currentMax to the right and (substract because negative) the currentax to the left
break;
}
else{
//Segment is too small to alocate more
//Amount left that can be allocated
int canAllocate = segments[idx].length-(maxPos-minPos);
//allocating
//To the left (negative)
answer[segments[idx].id]+= (maxPos+canAllocate);
//To the right (positive)
answer[segments[idx].id+1]+= (-minPos);
++firstPossible;
}
}
maxPos = currentWind;
}
else if (currentWind<minPos){
//printf("New maximum to the left %lld\n",currentWind);
for (int idx = firstPossible;idx<nbSnowballs-1;++idx){
//Look at the smallest segment that can still alocate
if (segments[idx].length>maxPos-currentWind){
//The segment is larger than the currentMax to the right and (substract because negative) the currentax to the left
break;
}
else{
//Segment is too small to alocate more
//Amount left that can be allocated
int canAllocate = segments[idx].length-(maxPos-minPos);
//allocating
//To the left (negative)
answer[segments[idx].id]+= (maxPos);
//To the right (positie)
answer[segments[idx].id+1]+= (-minPos+canAllocate);
++firstPossible;
}
}
minPos = currentWind;
}
}
//Finish for semgents larger at the end
for (int idx = firstPossible;idx<nbSnowballs-1;++idx){
//allocating
//To the left (negative)
answer[segments[idx].id]+= (maxPos);
//To the right (positie)
answer[segments[idx].id+1]+= (-minPos);
++firstPossible;
}
answer[0]+=(-minPos);
answer[nbSnowballs-1]+=(maxPos);
printSol(answer);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |