oj.uz

Submission #533708

# Submission time Handle Problem Language Result Execution time Memory
533708 2022-03-07T02:23:41 Z star_platinum Snowball (JOI21_ho_t2) C++14
100 / 100
 105 ms 26284 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define mikumywaifu ios_base::sync_with_stdio(0)
#define mudrockmywaifu cin.tie(0)
#define pb push_back
#define ss second
#define ff first
#define mem(i,j) memset(i,j,sizeof(i))
#define pii pair<int,int>
#define pll pair<long,long>
#define lowbit(x) x&-x
const int INF =0x3F3F3F3F;
const ll LINF=4611686018426387903;
ll gcd(ll a,ll b){
    if(b==0) return a;
    a%=b;
    return gcd(b,a);
}
void debug(){
    cout<<"DEBUG :";
    cout<<"\n";
}
/*-----------------------------------------*/
struct l{
    ll id,v;  
};
bool cmp(l a,l b){
    return a.v<b.v;
}
signed main(){
    mikumywaifu;
    mudrockmywaifu;
    int n,q;
    cin>>n>>q;
    vector<ll> a(n+1),b(q+1);
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<q;i++) cin>>b[i];
    ll tmp=0;
    vector<vector<ll>>dp(q+1,vector<ll>(2,0));
    for(int i=1;i<=q;i++){
        tmp+=b[i-1];
        dp[i][0]=min(dp[i-1][0],tmp);
        dp[i][1]=max(dp[i-1][1],tmp);
    }
    vector<l>arr;
    for(int i=0;i<n-1;i++){
        arr.pb({i,a[i+1]-a[i]});
    }
    vector<ll> ans(n+1);
    sort(arr.begin(),arr.end(),cmp);
    int pos=0;
    if(n>1){
        for(int i=1;i<=q;i++){
            while(pos<arr.size()&&dp[i][1]-dp[i][0]>=arr[pos].v){
                  ans[arr[pos].id]+=dp[i-1][1];
                  ans[arr[pos].id+1]-=dp[i-1][0];
                  if(b[i-1]>0) ans[arr[pos].id]+=arr[pos].v-(dp[i-1][1]-dp[i-1][0]);
                  else ans[arr[pos].id+1]+=arr[pos].v-(dp[i-1][1]-dp[i-1][0]);
                  pos++;
                  if(pos>=n-1) break;
            }
        }
        for(int i=pos;i<n-1;i++){
            ans[arr[i].id]+=dp[q][1];
            ans[arr[i].id+1]-=dp[q][0];
        }
    }
    ans[n-1]+=dp[q][1];
    ans[0]-=dp[q][0];
    for(int i=0;i<n;i++){
        cout<<ans[i]<<"\n";
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:58:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<l>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             while(pos<arr.size()&&dp[i][1]-dp[i][0]>=arr[pos].v){
      |                   ~~~^~~~~~~~~~~

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 1 ms 448 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 452 KB Output is correct
10 Correct 1 ms 504 KB Output is correct
11 Correct 1 ms 452 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 2 ms 588 KB Output is correct
17 Correct 1 ms 584 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 460 KB Output is correct

Subtask #2
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 1 ms 448 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 452 KB Output is correct
10 Correct 1 ms 504 KB Output is correct
11 Correct 1 ms 452 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 2 ms 588 KB Output is correct
17 Correct 1 ms 584 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 36 ms 14916 KB Output is correct
21 Correct 38 ms 14660 KB Output is correct
22 Correct 36 ms 14496 KB Output is correct
23 Correct 36 ms 14416 KB Output is correct
24 Correct 46 ms 15164 KB Output is correct
25 Correct 96 ms 24356 KB Output is correct
26 Correct 97 ms 24268 KB Output is correct
27 Correct 96 ms 23980 KB Output is correct
28 Correct 96 ms 24108 KB Output is correct
29 Correct 94 ms 23684 KB Output is correct
30 Correct 84 ms 23084 KB Output is correct
31 Correct 76 ms 22480 KB Output is correct
32 Correct 74 ms 22572 KB Output is correct
33 Correct 12 ms 2800 KB Output is correct
34 Correct 96 ms 24660 KB Output is correct
35 Correct 100 ms 24128 KB Output is correct
36 Correct 97 ms 24360 KB Output is correct
37 Correct 105 ms 24272 KB Output is correct
38 Correct 99 ms 24012 KB Output is correct
39 Correct 91 ms 24152 KB Output is correct
40 Correct 86 ms 24256 KB Output is correct
41 Correct 42 ms 15552 KB Output is correct
42 Correct 90 ms 22600 KB Output is correct
43 Correct 94 ms 25928 KB Output is correct
44 Correct 41 ms 15436 KB Output is correct
45 Correct 95 ms 24152 KB Output is correct
46 Correct 101 ms 26060 KB Output is correct
47 Correct 100 ms 26188 KB Output is correct
48 Correct 101 ms 26284 KB Output is correct