Submission #691526

#	Time	Username	Problem	Language	Result	Execution time	Memory
691526		guagua0407	Snowball (JOI21_ho_t2)	C++17	0 / 100	2 ms	596 KiB

Main

/*
燒雞
 燒雞
  燒雞    好想進選訓
 燒雞
燒雞
*/
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define f first
#define s second
#define all(x) x.begin(),x.end() 
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

struct node{
    ll sum;
    ll l;
    ll r;
    ll pl;
    ll pr;
    ll rans;
    ll lans;
};

bool comp(node a,node b){
    return a.sum<b.sum;
}

int main() {_
    //setIO("wayne");
    ll n,q;
    cin>>n>>q;
    ll num[n];
    ll gapl[n],gapr[n];
    for(ll i=0;i<n;i++){
        cin>>num[i];
    }
    for(ll i=0;i<n-1;i++){
        gapl[i]=num[i+1]-num[i];
        gapr[i+1]=num[i+1]-num[i];
    }
    node cur;
    cur.sum=cur.l=cur.r=cur.pr=cur.pl=cur.rans=cur.lans=0;
    vector<node> left,right;
    left.push_back(cur);
    right.push_back(cur);
    ll pos=0;
    for(ll i=0;i<q;i++){
        ll x;
        cin>>x;
        pos+=x;
        if(x>=0){
            cur.r=max(cur.r,pos);
            cur.sum=cur.l+cur.r;
            left.push_back(cur);
            cur.pr=max(cur.pr,cur.r);
        }
        else{
            cur.l=max(cur.l,-1*pos);
            cur.sum=cur.l+cur.r;
            right.push_back(cur);
            cur.pl=max(cur.pl,cur.l);
        }
    }
    sort(all(left),comp);
    sort(all(right),comp);
    vector<ll> lsum(left.size(),0);
    vector<ll> rsum(right.size(),0);
    vector<ll> lsum2(left.size(),0);
    vector<ll> rsum2(right.size(),0);
    vector<ll> lsum3(left.size(),0);
    vector<ll> rsum3(right.size(),0);
    for(ll i=1;i<left.size();i++){
        lsum[i]=left[i].sum;
        left[i].rans=left[i-1].rans+max(0ll,left[i].r-left[i].pr);
        lsum2[i]=lsum3[i]=left[i].l+left[i].pr;
        lsum2[i]+=lsum2[i-1];
        left[i].l+=left[i-1].l;
        left[i].r+=left[i-1].r;
        left[i].pl+=left[i-1].pl;
        left[i].pr+=left[i-1].pr;
    }
    for(ll i=1;i<right.size();i++){
        rsum[i]=right[i].sum;
        right[i].lans=right[i-1].lans+max(0ll,right[i].l-right[i].pl);
        rsum2[i]=rsum3[i]=right[i].r+right[i].pl;
        rsum2[i]+=rsum2[i-1];
        right[i].l+=right[i-1].l;
        right[i].r+=right[i-1].r;
        right[i].pl+=right[i-1].pl;
        right[i].pr+=right[i-1].pr;
    }
    vector<ll> ans(n,0);
    for(ll i=0;i<n-1;i++){
        ll gap=gapl[i];
        ll pos=upper_bound(all(lsum),gap)-lsum.begin()-1;
        ll pos2=upper_bound(lsum3.begin()+pos+1,lsum3.end(),gap)-lsum3.begin()-1;
        ans[i]+=left[pos].rans;
        ll sz=lsum.size();
        ans[i]+=gap*(pos2-pos)-lsum2[pos2]+lsum2[pos];
        //cout<<ans[i]<<' ';
    }
    //cout<<'\n';
    //cout<<"  ";
    for(ll i=1;i<n;i++){
        ll gap=gapr[i];
        ll pos=upper_bound(all(rsum),gap)-rsum.begin()-1;
        ll pos2=upper_bound(rsum3.begin()+pos+1,rsum3.end(),gap)-rsum3.begin()-1;
        ans[i]+=right[pos].lans;
        ll sz=rsum.size();
        ans[i]+=gap*(pos2-pos)-rsum2[pos2]+rsum2[pos];
        //cout<<right[pos].lans+gap*(pos2-pos)-rsum2[pos2]+rsum2[pos]<<' ';
    }
    ans[0]+=cur.l;
    ans[n-1]+=cur.r;
    //cout<<'\n';
    for(ll i=0;i<n;i++){
        cout<<ans[i]<<'\n';
    }
    return 0;
}
//maybe its multiset not set

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:81:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(ll i=1;i<left.size();i++){
      |                ~^~~~~~~~~~~~
Main.cpp:91:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(ll i=1;i<right.size();i++){
      |                ~^~~~~~~~~~~~~
Main.cpp:107:12: warning: unused variable 'sz' [-Wunused-variable]
  107 |         ll sz=lsum.size();
      |            ^~
Main.cpp:118:12: warning: unused variable 'sz' [-Wunused-variable]
  118 |         ll sz=rsum.size();
      |            ^~
Main.cpp: In function 'void setIO(std::string)':
Main.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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