Submission #383772

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
383772	2021-03-30T19:38:32 Z	N1NT3NDO	Po (COCI21_po)	C++14	10 / 70	1000 ms	3872 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_left(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_left(v*2,tl,m);
    else return position_left(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)
    {
        //for(int i=1;i<=n;i++) cout << get(1,1,n,i,i) << ' ';
        //cout << '\n';
        if (t[1].se==0) break;
        l = position_left(1,1,n);

        int l1 = l, r1 = n;
        while(l1<r1)
        {
            int m1 = (l1+r1+1) >> 1;
            if (get(1,1,n,l,m1)!=0)
                l1 = m1;
            else r1 = m1 - 1;
        }
        r = l1;
        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

10.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Incorrect	2 ms	364 KB	Output isn't correct
3	Incorrect	3 ms	364 KB	Output isn't correct
4	Incorrect	316 ms	2028 KB	Output isn't correct
5	Incorrect	528 ms	3692 KB	Output isn't correct
6	Execution timed out	1077 ms	3820 KB	Time limit exceeded
7	Execution timed out	1097 ms	3872 KB	Time limit exceeded