Submission #475895

#	Time	Username	Problem	Language	Result	Execution time	Memory
475895		Jarif_Rahman	Snowball (JOI21_ho_t2)	C++17	100 / 100	148 ms	11600 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const ll inf = 1e13;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q; cin >> n >> q;
    vector<ll> v(n);
    for(ll &x: v) cin >> x;

    vector<ll> w(q);
    for(ll &x: w) cin >> x;
    vector<ll> sum(q+1);
    sum[0] = 0;
    for(int i = 0; i < q; i++) sum[i+1] = sum[i]+w[i];
    vector<pair<ll, ll>> pos, neg;
    pos.pb({0, 0});
    neg.pb({0, 0});
    ll a = 0, b = 0;
    for(int i = 1; i <= q; i++){
        if(sum[i] == 0) continue;
        if(sum[i] > 0 && sum[i] > b){
            b = sum[i];
            pos.pb({b, -a});
        }
        if(sum[i] < 0 && sum[i] < a){
            a = sum[i];
            neg.pb({-a, b});
        }
    }

    vector<ll> ans(n, 0);

    for(int i = 0; i < n; i++){
        if(i == 0){
            ans[i]+=neg.back().f;
        }
        else{
            int a = 0, b = neg.size(); b--;
            while(a < b){
                int md = (a+b+1)/2;
                if(neg[md].f+neg[md].sc > v[i]-v[i-1]) b = md-1;
                else a = md;
            }
            ll cur = neg[a].f;
            if(a+1 != neg.size()) cur = max(cur, v[i]-v[i-1]-neg[a+1].sc);
            ans[i]+=cur;
        }
        if(i == n-1){
            ans[i]+=pos.back().f;
        }
        else{
            int a = 0, b = pos.size(); b--;
            while(a < b){
                int md = (a+b+1)/2;
                if(pos[md].f+pos[md].sc > v[i+1]-v[i]) b = md-1;
                else a = md;
            }
            ll cur = pos[a].f;
            if(a+1 != pos.size()) cur = max(cur, v[i+1]-v[i]-pos[a+1].sc);
            ans[i]+=cur;
        }
    }

    for(ll x: ans) cout << x << "\n";
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:51:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |             if(a+1 != neg.size()) cur = max(cur, v[i]-v[i-1]-neg[a+1].sc);
      |                ~~~~^~~~~~~~~~~~~
Main.cpp:65:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             if(a+1 != pos.size()) cur = max(cur, v[i+1]-v[i]-pos[a+1].sc);
      |                ~~~~^~~~~~~~~~~~~

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