Submission #383758

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
383758	2021-03-30T19:11:06 Z	N1NT3NDO	Po (COCI21_po)	C++14	50 / 70	1000 ms	3820 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 int inf = 2 * 1e9;
int a[N],n,mod[4*N];
pair<int,int> t[4*N];

pair<int,int> comb(pair<int,int> a, pair<int,int> b)
{
   return {min(a.fi,b.fi),max(a.se,b.se)};
}

void build(int v,int tl,int tr)
{
    if (tl==tr)
    {
        t[v].fi = a[tl];
        t[v].se = 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] = comb(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].fi -= mod[v*2];
       t[v*2].se -= mod[v*2];
       t[v*2+1].fi -= mod[v*2+1];
       t[v*2+1].se -= mod[v*2+1];
   }
}

int position(int v,int tl,int tr)
{
    push(v,tl,tr);
    if (tl==tr) return tl;
    int m = (tl+tr) >> 1;
    if (t[v*2].se>0) return position(v*2,tl,m);
    else return position(v*2+1,m+1,tr);
}

int 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].fi;
    int m = (tl+tr) >> 1;
    int res = min(get(v*2,tl,m,l,r),get(v*2+1,m+1,tr,l,r));
    t[v] = comb(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].fi -= value;
        t[v].se -= 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] = comb(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)
    {
        //while (l <= n && get(1, 1, n, l, l) == 0)
          //  l++;
        if (t[1].se==0) break;
        l = position(1,1,n);


        //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	1 ms	364 KB	Output is correct
3	Correct	2 ms	364 KB	Output is correct
4	Correct	101 ms	2064 KB	Output is correct
5	Correct	173 ms	3692 KB	Output is correct
6	Execution timed out	1098 ms	3820 KB	Time limit exceeded
7	Execution timed out	1088 ms	3692 KB	Time limit exceeded