제출 #534834

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
534834		Cookie197	Snowball (JOI21_ho_t2)	C++17	100 / 100	143 ms	24680 KiB

Main

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>

using namespace std;
#define ll long long
#define pii pair<ll,ll> 
#define mp make_pair
#define endl "\n"
#define out(x) cout<< #x << " = " << x << endl
#define outp(x) cout << #x << " first = " << x.first << " second = " << x.second << endl
#define inf 3e18

int n,q;
ll arr[200005], ans[200005];
pii snow[200005];
ll rem[200005];

ll wind[200005];
pii samplesnow;
vector<pii> sampleadd(200005);
vector<ll> samplepre(200005);
vector<pii> bit(200005);
pii operator+(const pii &a, const pii &b){
    return mp(a.first+b.first, a.second+b.second);
}
void add(int id,pii x){
    for (int i=id;i<=q;i+=(i&-i)) bit[i] = bit[i] + x;
}
pii sum(int id){
    if (id==0) return mp(0ll,0ll);
    if (id>=q) id=q;
    pii ans = mp(0ll,0ll);
    for (int i=id;i>=1;i-=(i&-i)) ans = ans + bit[i];
    return ans;
}


signed main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>q; n+=2;
    arr[1] = -3e18, arr[n] = 3e18;
    for (int i=2;i<n;i++) cin>>arr[i];
    for (int i=1;i<n;i++) {
        snow[i] = mp(0,0), rem[i] = arr[i+1]-arr[i];
    }
    
    for (int z=1;z<=q;z++){
        ll x; cin>>x; wind[z] = x;
        if (x>0){
            samplesnow.first -= x;
            if (samplesnow.first < 0){
                sampleadd[z].first += -samplesnow.first;
                samplesnow.first = 0;
            }
            samplesnow.second += x;
            if (samplesnow.second > inf){
                samplesnow.second = inf;
            }
        }else{
            x = abs(x);
            samplesnow.second -= x;
            if (samplesnow.second < 0){
                sampleadd[z].second += -samplesnow.second;
                samplesnow.second = 0;
            }
            samplesnow.first += x;
            if (samplesnow.first > inf){
                samplesnow.first = inf;
            }
        }
        samplepre[z] = samplepre[z-1] + sampleadd[z].first + sampleadd[z].second;
    }
    

    for (int z=1;z<=q;z++){
        //cout<<sampleadd[z].first<<" "<<sampleadd[z].second<<"  "<<samplepre[z]<<endl;
        add(z,sampleadd[z]);
    }
    for (int z=q+1;z<samplepre.size();z++) samplepre[z] = samplepre[q];

    for (int i=1;i<n;i++){
        ll amount = arr[i+1] - arr[i];
        int pos = lower_bound(samplepre.begin(),samplepre.end(),amount+1) - samplepre.begin();
        pii more = sum(pos);
        //out(pos);
        //outp(sampleadd[pos]);
        //out(amount);
        //outp(more);
        ll toomuch = samplepre[pos] - amount; toomuch = max(0ll, toomuch);
        if (sampleadd[pos].first != 0) more.first -= toomuch;
        else more.second -= toomuch;

        //outp(more);
        ans[i] += more.first, ans[i+1] += more.second;
    }

    for (int i=2;i<n;i++) cout<<ans[i]<<endl;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:81:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for (int z=q+1;z<samplepre.size();z++) samplepre[z] = samplepre[q];
      |                    ~^~~~~~~~~~~~~~~~~

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