#include <bits/stdc++.h>
using namespace std;
#define eb emplace_back
#define pb push_back
#define ppb pop_back
#define ub upper_bound
#define lb lower_bound
#define bs binary_search
#define cln(a,s) memset((a),0,sizeof((a)[0])*(s))
#define all(x) (x).begin() , (x).end()
#define fi first
#define se second
#define int long long
using pii = pair<int,int>;
using ll = long long;
const int maxn = 2e5 + 5;
const int inf = 1e9;
const int mod = 1e9+7;
int n,q,a[maxn],t[4*maxn],lz[4*maxn];
map<int,vector<int>> occ;
void build(int vi,int vl,int vr) {
if(vl == vr) {
t[vi] = a[vl];
return;
}
int mid = (vl+vr)/2;
build(2*vi,vl,mid);
build(2*vi+1,mid+1,vr);
t[vi] = min(t[2*vi],t[2*vi+1]);
}
void push(int vi,int vl,int vr) {
if(vl == vr) {
lz[vi] = 0;
return;
}
lz[2*vi] += lz[vi];
lz[2*vi+1] += lz[vi];
t[2*vi] += lz[vi];
t[2*vi+1] += lz[vi];
lz[vi] = 0;
}
void update(int vi,int vl,int vr,int l,int r,int val) {
if(l > r) return;
push(vi,vl,vr);
if(vl == l and vr == r) {
t[vi] += val;
lz[vi] += val;
return;
}
int mid = (vl+vr)/2;
update(2*vi,vl,mid,l,min(mid,r),val);
update(2*vi+1,mid+1,vr,max(mid+1,l),r,val);
t[vi] = min(t[2*vi],t[2*vi+1]);
}
int query(int vi,int vl,int vr,int l,int r) {
if(l > r) return inf;
push(vi,vl,vr);
if(vl == l and vr == r) return t[vi];
int mid = (vl+vr)/2;
return min(query(2*vi,vl,mid,l,min(mid,r)),
query(2*vi+1,mid+1,vr,max(mid+1,l),r));
}
int solve(int l,int r,int diff) {
if(l > r) return 0;
int mn = query(1,1,n,l,r);
//cout << l << " " << r << " " << mn << " " << diff << endl;
if(l == r) return mn != 0;
update(1,1,n,l,r,-mn);
int tmp = mn;
mn += diff;
diff += tmp;
int st = lb(all(occ[mn]),l) - occ[mn].begin();
int nd = ub(all(occ[mn]),r) - occ[mn].begin() - 1;
if(occ[mn][st] == l and occ[mn][nd] == r and tmp == 0) return 0;
int ans = 1;
ans += solve(l,occ[mn][st]-1,diff);
ans += solve(occ[mn][nd]+1,r,diff);
for(int i=st+1;i<=nd;i++) {
ans += solve(occ[mn][i-1]+1,occ[mn][i]-1,diff);
}
return ans;
}
int32_t main () {
//freopen("in","r",stdin); freopen("out","w",stdout);
ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
cin >> n;
for(int i=1;i<=n;i++) cin >> a[i] , occ[a[i]].pb(i);
build(1,1,n);
cout << solve(1,n,0) << endl;
/*while(q--) {
int opt,l,r,val;
cin >> opt >> l >> r;
if(opt == 1) {
cin >> val;
update(1,1,n,l,r,val);
}
else {
cout << query(1,1,n,l,r) << endl;
}
}*/
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 4 |
Incorrect |
34 ms |
3436 KB |
Output isn't correct |
| 5 |
Incorrect |
54 ms |
5868 KB |
Output isn't correct |
| 6 |
Correct |
159 ms |
17772 KB |
Output is correct |
| 7 |
Incorrect |
239 ms |
26860 KB |
Output isn't correct |
