Submission #1081860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081860		FIFI_cpp	Snowball (JOI21_ho_t2)	C++17	100 / 100	153 ms	20196 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <fstream>
#include <iterator>
#include <set>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <cctype>
#include <string>
#include <cassert>
#include <set>
#include <bitset>
#include <unordered_set>
#include <numeric>
//using ll = int64_t;
#define pb push_back
#define all(a) a.begin(),a.end()
#define ppi pair<int,pair<int,int>>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int int64_t
// xcode cant include bits/stdc++.h
using namespace std;
/*   /\_/\
*   (= ._.)
*   / >  \>
*/
// encouraging cat
const int INF = 1000000;
const int mod = 1000000007;
const int MAXN = 2e5+5;
int n,q;
int pre1[MAXN + 1],pre2[MAXN + 1];
bool check(int k,int tmp)
{
    return ((pre1[k]+pre2[k])<=tmp);
}
int32_t main()
{
    cin >> n >> q;
    vector<int> x(MAXN + 1),a(MAXN + 1),w(MAXN + 1),sum(MAXN + 1);
    vector<pair<int,int>> b(n + 1);
    for(int i = 1;i <= n;i++)
    {
        cin >> x[i];
    }
    for(int i = 1;i <= q;i++)
    {
        cin >> w[i];
    }
    sum[0] = 0;
    pre1[0] = pre2[0] = 0;
    for(int j = 1;j <= q;j++)
    {
        sum[j] = sum[j-1] + w[j];
        pre1[j] = max(pre1[j - 1],sum[j]);
        pre2[j] = max(pre2[j - 1],-sum[j]);
    }
    a[1] = pre2[q];
    a[n] = pre1[q];
    for(int i = 1;i < n;i++)
    {
        int tmp = x[i + 1] - x[i];
        int l = 1,r = q,res=0;
        while(l <= r)
        {
            int mid = (l + r) / 2;
            if(check(mid,tmp))
            {
                res = mid;
                l = mid+1;
            }
            else 
                r = mid-1;
        }
        if(res > 0)
        {
            b[i].first = pre1[res];
            b[i].second = pre2[res];
        }
        if(res < q)
        {
            int pre_l = b[i].first,pre_r = b[i].second;
            int cur = tmp - pre_l - pre_r;
            if(sum[res + 1] > 0)
            {
                b[i].first += cur;
            }
            else 
                b[i].second+=cur;
        }
    }
    for(int i = 1;i <= n;i++)
    {
        if(i < n)
        {
            a[i] += b[i].first;
            a[i+1] += b[i].second;
        }
        cout << a[i] << '\n';
    }
    return 0;
}

Compilation message (stderr)

Main.cpp:31:9: warning: "/*" within comment [-Wcomment]
   31 | /*   /\_/\
      |

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