Submission #383985

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
383985	2021-03-31T06:51:48 Z	N1NT3NDO	Po (COCI21_po)	C++14	0 / 70	1000 ms	23660 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],B[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] = 0;
        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]!=0 && tl!=tr)
    {
        mod[v*2] = mod[v];
        mod[v*2+1] = mod[v];
        mod[v] = 0;
        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 > l && get(1, 1, n, l, r) == 0)
        //    r--;
        //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

0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	384 KB	Output isn't correct
2	Incorrect	3 ms	364 KB	Output isn't correct
3	Incorrect	213 ms	1900 KB	Output isn't correct
4	Execution timed out	1095 ms	8556 KB	Time limit exceeded
5	Execution timed out	1083 ms	10084 KB	Time limit exceeded
6	Execution timed out	1094 ms	17260 KB	Time limit exceeded
7	Execution timed out	1097 ms	23660 KB	Time limit exceeded