Submission #670242

#	Time	Username	Problem	Language	Result	Execution time	Memory
670242		bLIC	Po (COCI21_po)	C++17	70 / 70	16 ms	2372 KiB

Main

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

// using namespace __gnu_pbds;
using namespace std;

// typedef tree<int,null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x).size()
#define ft first
#define sd second
#define pb push_back
#define endl '\n'

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<vl> vvl;

#define dbg if(0)

const ll MOD = 998244353;
const ll INFLL = 1e14;
const int INF = 1e9;
const int maxN = 2e5+6;
const int maxK = 10;

void printbit(int x, int len) {string s="\n";while(len--){s=((x%2)?'1':'0')+s;x/=2;} cout<<s;}


#define gbit(x, i) (((1<<i)&(x))!=0)

template<typename T>
T max(const T& a, const T& b, const T& c){return max(a, max(b, c));}
template<typename T>
T max(T a, T b, T c, T d){return max(max(a, b, c), d);}

struct Mytype{
    ll val[2][2], mx;
    Mytype(ll x){
        val[0][1] = val[1][0] = val[0][0] = 0;
        val[1][1] = x;
    }
    Mytype():Mytype(0){}
    friend Mytype operator+(const Mytype& a, const Mytype& b){
        Mytype temp;
        temp.val[0][0] = max(a.val[0][0]+b.val[1][0], a.val[0][1]+b.val[0][0]);
        temp.val[1][0] = max(a.val[1][0]+b.val[1][0], a.val[1][1]+b.val[0][0]);
        temp.val[0][1] = max(a.val[0][0]+b.val[1][1], a.val[0][1]+b.val[0][1]);
        temp.val[1][1] = max(a.val[1][0]+b.val[1][1], a.val[1][1]+b.val[0][1]);
        temp.mx=-INFLL;
        for (int i = 0;i<2;i++)
            for (int j = 0;j<2;j++) temp.mx = max(temp.mx, temp.val[i][j]);
        return temp;
    }
};


template <class T> struct SegTree{
    int n; T ID;
    std::vector<T> tree;
    T oper(T a, T b){return a+b;} // update this operation function according to need
    SegTree(int _n, T id){
        n = 1;ID = id;
        while(n<_n) n<<=1;
        tree.resize(2*n, ID);
    }
    void build(std::vector<T> list){
        for (int i = 0;i<(int) list.size();++i) tree[i+n] = list[i];
        for (int i = n-1;i>0;--i) tree[i] = oper(tree[i<<1], tree[i<<1|1]);
    }
    void update(int ind, T value){
        for (tree[ind+=n] = value;ind>1;ind>>=1) tree[ind>>1] = (ind&1)?oper(tree[ind^1], tree[ind]):oper(tree[ind], tree[ind^1]);
    }
    T query(int l, int r){// indexing is from 0 to n-1, gives answer to [l, r)
        T left = ID;
        T right = ID;
        for (l+=n, r+=n;l<r;l>>=1, r>>=1){
            if (l&1) left = oper(left, tree[l++]);
            if (r&1) right = oper(tree[--r], right);
        }
        return oper(left, right);
    }
};


void solve(){
    int n;cin>>n;
    vi a(n+2);
    for (int i = 1;i<=n;i++) cin>>a[i];
    vi arr;
    int ans = 0;
    for (int i = 1;i<n+2;i++) {
        if (a[i]-a[i-1]!=0) arr.pb(a[i]-a[i-1]);
    }
    stack<int> s;
    for (int x:arr){
        if (x>0) s.push(x);
        else {
            while(x){
                auto y = s.top();s.pop();
                if (-x<y){
                    y+=x;
                    x = 0;
                    s.push(y);
                }
                else {
                    x+=y;
                }
                ans++;
            }
        }
    }
    cout<<ans;

}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
// #define _DEBUG
#ifdef _DEBUG
	freopen("optmilk.in", "r", stdin);
	freopen("optmilk.out", "w", stdout);
	int tt = clock();
#endif
    int t=1, i = 1;
    // cin>>t;
    while(t--){
        // cout<<"Case #"<<i++<<": ";
        solve();
        // cout<<'\n';
    }
#ifdef _DEBUG
    cerr << "TIME = " << (float)(clock() - tt)/CLOCKS_PER_SEC << endl;
    tt = clock();
#endif
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:139:14: warning: unused variable 'i' [-Wunused-variable]
  139 |     int t=1, i = 1;
      |              ^

• Subtask 1: 70 / 70