Submission #417066

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
417066	2021-06-03T11:20:01 Z	mat_v	Snowball (JOI21_ho_t2)	C++14	0 / 100	2 ms	460 KB

Main

#include <bits/stdc++.h>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))

using namespace std;
typedef long long ll;

int n,m;

ll maks[200005];
ll mini[200005];
ll ans[200005];
ll niz[200005];
ll pref[200005];

ll get(int x, int idx){
    if(idx == 0){
        if(mini[x] >= 0)return 0;
        return -mini[x];
    }
    if(maks[x] <= 0)return 0;
    return maks[x];
}

int main()
{
    ios_base::sync_with_stdio(false);

    cin >> n >> m;
    ff(i,1,n)cin >> niz[i];
    ff(i,1,m){
        ll x;
        cin >> x;
        pref[i] = pref[i - 1] + x;
    }
    mini[1] = maks[1] = pref[1];
    ff(i,2,m){
        maks[i] = max(pref[i], maks[i - 1]);
        mini[i] = min(pref[i], mini[i - 1]);
    }

    ff(i,1,n-1){
        ll dif = niz[i + 1] - niz[i];
        int l = 1;
        int r = m;
        if(get(r,0) + get(r,1) < dif){
            ans[i] += get(r,1);
            ans[i + 1] += get(r,0);
        }
        else{
            while(l < r){
                int mid = (l + r) / 2;
                if(get(mid,0) + get(mid,1) >= dif)r = mid;
                else l = mid + 1;
            }
        }
        if(pref[l] > 0){
            ans[i+1] += get(l,0);
            ans[i] += (dif - get(l,0));
        }
        else{
            ans[i] += get(l,1);
            ans[i + 1] += (dif - get(l,1));
        }
    }
    ans[1] += get(m,0);
    ans[n] += get(m,1);
    ff(i,1,n)cout << ans[i] << "\n";


    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
Main.cpp:29:5: note: in expansion of macro 'ff'
   29 |     ff(i,1,n)cin >> niz[i];
      |     ^~
Main.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
Main.cpp:30:5: note: in expansion of macro 'ff'
   30 |     ff(i,1,m){
      |     ^~
Main.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
Main.cpp:36:5: note: in expansion of macro 'ff'
   36 |     ff(i,2,m){
      |     ^~
Main.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
Main.cpp:41:5: note: in expansion of macro 'ff'
   41 |     ff(i,1,n-1){
      |     ^~
Main.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
Main.cpp:67:5: note: in expansion of macro 'ff'
   67 |     ff(i,1,n)cout << ans[i] << "\n";
      |     ^~

Subtask #1

0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	352 KB	Output is correct
4	Incorrect	2 ms	460 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #2

0 / 67.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	352 KB	Output is correct
4	Incorrect	2 ms	460 KB	Output isn't correct
5	Halted	0 ms	0 KB	-