Submission #1167564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167564		ThylOne	Snowball (JOI21_ho_t2)	C++20	100 / 100	177 ms	16224 KiB

Main

//####################
//SnowBall
//####################
#include <algorithm>
#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;int q;cin>>q;
    
    vector<int> X(n);
    for(int &pos:X)cin>>pos;
    sort(X.begin(), X.end());
    
    vector<int> max_t(q), min_t(q), norme_t(q);
    int actVx = 0;
    vector<int> W(q);
    for(int i = 0 ;i < q ; i++){
        int v;cin>>v;W[i] = v;
        actVx += v; 
        max_t[i] = max((i==0 ? 0 : max_t[i-1]), actVx);
        min_t[i] = min((i==0 ? 0 : min_t[i-1]), actVx);
        norme_t[i] = max_t[i] + abs(min_t[i]);
    }

    pair<int,int> inters[n];
    for(int i = 0 ; i < n ; i++)
        inters[i] = make_pair(X[i], X[i]);

    vector<pair<int,int>> couple;
    for(int i = 0 ; i < n-1;i++)couple.push_back(make_pair(i,i+1));

    sort(couple.begin(), couple.end(), [&](pair<int,int> a, pair<int,int> b){
        return abs(X[a.first]-X[a.second]) < abs(X[b.first] - X[b.second]);
    });
    int time = -1;
    for(int iCouple = 0 ; iCouple < n - 1 ; iCouple++){
        auto act = couple[iCouple];
        int lenght = abs(X[act.first]  - X[act.second]);

        while(time<q-1 && norme_t[time + 1] < lenght)time++;
        if(time!=-1){//On applique tout ceux qui est hors collision
            inters[act.first].second += max_t[time];
            inters[act.second].first += min_t[time];
        }
        //On applique le choc de la collision
        if(time<q-1){
            inters[act.first].second = max(inters[act.first].second, min(inters[act.first].second+W[time+1], inters[act.second].first ));
            inters[act.second].first = min(inters[act.second].first, max(inters[act.second].first+W[time+1], inters[act.first].second ));
        }        
    }
    //On oublie pas les boules du bord
    inters[0].first += min_t[q - 1];
    inters[n - 1].second += max_t[q - 1];
    //Pour dbg
    for(int i = 0;i<n;i++){
        cout << inters[i].second - inters[i].first << endl;
    }
    return 0;
};

• Subtask 1: 33 / 33
• Subtask 2: 67 / 67