| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 670242 |
2022-12-08T11:24:42 Z |
bLIC |
Po (COCI21_po) |
C++17 |
|
16 ms |
2372 KB |
#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
Main.cpp: In function 'int main()':
Main.cpp:139:14: warning: unused variable 'i' [-Wunused-variable]
139 | int t=1, i = 1;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
4 ms |
980 KB |
Output is correct |
| 5 |
Correct |
7 ms |
1368 KB |
Output is correct |
| 6 |
Correct |
16 ms |
2372 KB |
Output is correct |
| 7 |
Correct |
15 ms |
2240 KB |
Output is correct |
