Submission #383741

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
383741	2021-03-30T18:46:46 Z	N1NT3NDO	Po (COCI21_po)	C++14	50 / 70	1000 ms	4992 KB

Main

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()

using namespace std;

const int N = 1e5 + 500;
const ll inf = 2 * 1e9;
int a[N],n;
ll t[4*N],mod[4*N];

void build(int v,int tl,int tr)
{
    if (tl==tr)
    {
        t[v] = a[tl];
        mod[v] = -1;
        return;
    }
    int m = (tl+tr) >> 1;
    build(v*2,tl,m);
    build(v*2+1,m+1,tr);
    t[v] = min(t[v*2],t[v*2+1]);
}

void push(int v,int tl,int tr)
{
   if (mod[v]!=-1 && tl!=tr)
   {
       mod[v*2] = mod[v];
       mod[v*2+1] = mod[v];
       mod[v] = -1;
       t[v*2] -= mod[v*2];
       t[v*2+1] -= mod[v*2+1];
   }
}

ll get(int v,int tl,int tr,int l,int r)
{
    push(v,tl,tr);
    if (tl>tr || tr<l || tl>r) return inf;
    if (tl>=l && tr<=r) return t[v];
    int m = (tl+tr) >> 1;
    ll res = min(get(v*2,tl,m,l,r),get(v*2+1,m+1,tr,l,r));
    t[v] = min(t[v*2],t[v*2+1]);
    return res;
}

void upd(int v,int tl,int tr,int l,int r,int value)
{
    if (tl>tr || tl>r || tr<l) return;
    if (tl>=l && tr<=r)
    {
        t[v] -= value;
        mod[v] = value;
        return;
    }
    push(v,tl,tr);
    int m = (tl+tr) >> 1;
    upd(v*2,tl,m,l,r,value);
    upd(v*2+1,m+1,tr,l,r,value);
    t[v] = min(t[v*2],t[v*2+1]);
}

int main()
{
    //ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("fcount.in","r",stdin); freopen("fcount.out","w",stdout);
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];

    build(1, 1, n);
    int l = 1, r = 1;
    int ans = 0;
    while (l <= n)
    {
        //for(int i=1;i<=n;i++) cout << get(1,1,n,i,i) << ' ';
        //cout << '\n';
        while (l <= n && get(1, 1, n, l, l) == 0)
            l++;


        if (l > n)
            break;

        r = l;
        while (r < n && get(1, 1, n, l, r+1) != 0)
            r++;

        //r = min(r, n);

        //r--;
        //cout << l << ' ' << r << '\n';

        upd(1, 1, n, l, r, get(1, 1, n, l, r));

        ans++;

        //l++;
    }

    cout << ans;
}

Subtask #1

50.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	2 ms	512 KB	Output is correct
3	Correct	2 ms	364 KB	Output is correct
4	Correct	123 ms	2668 KB	Output is correct
5	Correct	196 ms	4992 KB	Output is correct
6	Execution timed out	1087 ms	4816 KB	Time limit exceeded
7	Execution timed out	1080 ms	4460 KB	Time limit exceeded