Submission #936692

#	Time	Username	Problem	Language	Result	Execution time	Memory
936692		anton	Snowball (JOI21_ho_t2)	C++17	100 / 100	1061 ms	14520 KiB

Main

#include<bits/stdc++.h>
#include <vector>

using namespace std;
#define int long long
#define pii pair<int, int>


vector<int> p;
vector<pii> r;
vector<pii> l;
vector<int> res;
vector<int> x;
vector<int> w;

pii last_before(int time, vector<pii>& v){
    int r= 0;
    for(int step = (1LL<<20LL); step>=1; step/=2){
        int next= r+step;
        if(next<v.size() && v[next].first<=time){
            r = next;
        }
    }
    return v[r];
}

int find_intersection_moment(int dist){
    int time=  0;
    for(int step = (1LL<<20LL); step>=1; step/=2){
        int next= time+step;
        pii rh = last_before(next, r);
        pii lh =last_before(next, l);
        if(dist-rh.second+lh.second>0){
            time=next;
        }
    }

    //cout<<"majoration "<<dist<<" "<<time<<endl;

    if(time>1e6){
        return -1;
    }
    return time+1;
}

void add_major(int i, int j){
    int t=  find_intersection_moment(x[j]-x[i]);
    if(t==-1){
        res[i]+=r.back().second;
        res[j]-=l.back().second;
        //cout<<i<<" "<<j<<endl;
        
        return;
    }
    int pos1 = last_before(t-1, r).second;
    res[i] += pos1;
    int pos2= last_before(t-1, l).second;
    res[j] -= pos2;
    //cout<<pos1<<" "<<pos2<<endl;
    //cout<<w[t-1]<<endl;
    if(w[t-1]>0){
        res[i] += ((x[j]-x[i])+pos2-pos1);
        //cout<<((x[j]-x[i])+pos2-pos1)<<" i "<<endl;
    }
    else{
        res[j] += ((x[j]-x[i])+pos2-pos1);
        //cout<<((x[j]-x[i])+pos2-pos1)<<" j "<<endl;
    }
}

signed main(){
    int n, q;
    cin>>n>>q;
    x.push_back(-1e18);
    for(int i = 0; i<n; i++){
        int v;
        cin>>v;
        x.push_back(v);
    }
    x.push_back(1e18);
    p.push_back(0);
    w.resize(q);
    for(int i = 0; i<q; i++){
        cin>>w[i];
        p.push_back(p.back()+w[i]);
    }
    int rmost= -1;
    for(int i = 0; i<=q; i++){
        if(p[i]>rmost){
            rmost = p[i];
            r.push_back({i, p[i]});
        }
    }
    int lmost= 1;
    for(int i = 0; i<=q; i++){
        if(p[i]<lmost){
            lmost = p[i];
            l.push_back({i, p[i]});
        }
    }
    

    res.resize(n+2);
    for(int i = 0; i<=n; i++){
        add_major(i, i+1);
        //cout<<"added 1"<<endl;
    }

    for(int i = 1; i<=n; i++){
        cout<<res[i]<<endl;
    }

}

Compilation message (stderr)

Main.cpp: In function 'std::pair<long long int, long long int> last_before(long long int, std::vector<std::pair<long long int, long long int> >&)':
Main.cpp:20:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         if(next<v.size() && v[next].first<=time){
      |            ~~~~^~~~~~~~~

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