Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define FILL(X, V) memset((X), (V), sizeof(X))
- #define SIZE(V) int((V).size())
- #define FOR2(cont,start,max) for(int (cont) = (start), _MAX = (max); (cont) < _MAX; (cont)++)
- #define FOR(cont,max) FOR2((cont), 0, (max))
- #define LOG(x) (31 - __builtin_clz(x))
- #define W(x) cerr << "\033[31m" << #x << " = " << x << "\033[0m" << endl;
- #define Ws(x) cerr << "\033[31m" << #x << "\033[0m" << endl;
- #define ii pair<int, int>
- #define ff first
- #define ss second
- #define oo 1e9
- #define ep 1e-9
- #define pb push_back
- typedef long long ll;
- typedef unsigned long long ul;
- class SegTree_Max{
- vector<int> st, st2, id;
- vector<int> lazy;
- int n;
- void prop(int p, int L, int R){
- if(lazy[p]){
- st[p] += lazy[p];
- lazy[2*p] += lazy[p];
- lazy[2*p+1] += lazy[p];
- lazy[p] = 0;
- }
- }
- void upd(int p, int L, int R, int i, int j, int v){
- prop(p, L, R);
- if(j < L || i > R){
- return;
- }
- if(i <= L && R <= j){
- lazy[p] = v;
- prop(p, L, R);
- return;
- }
- int mid = (L+R)/2;
- upd(2*p, L, mid, i, j, v);
- upd(2*p+1, mid+1, R, i, j, v);
- st[p] = max(st[2*p],st[2*p+1]);
- }
- int qry(int p, int L, int R, int i, int j){
- // W(p);
- // W(L);
- // W(R);
- // W(i);
- // W(j);
- prop(p, L, R);
- if(j < L || i > R){
- // Ws(completely_out);
- // W(0);
- return -oo;
- }
- if(i <= L && R <= j){
- // Ws(completely_in);
- // W(st[p]);
- return st[p];
- }
- // Ws(partially_in);
- int mid = (L+R)/2;
- return max(qry(2*p, L, mid, i, j), qry(2*p+1, mid+1, R, i, j));
- }
- public:
- SegTree_Max(int sz){
- n = sz;
- st.assign(6*(n + 1), 0);
- lazy.assign(6*(n + 1), 0);
- }
- int qry(int i, int j){
- return qry(1, 1, n, i, j);
- }
- void upd(int i, int j, int v){
- upd(1, 1, n, i, j, v);
- }
- };
- class SegTree_Sum{
- vector<int> st, st2, id;
- vector<int> lazy;
- int n;
- void prop(int p, int L, int R){
- if(lazy[p]){
- st[p] += lazy[p];
- lazy[2*p] += lazy[p];
- lazy[2*p+1] += lazy[p];
- lazy[p] = 0;
- }
- }
- void upd(int p, int L, int R, int i, int j, int v){
- prop(p, L, R);
- if(j < L || i > R) return;
- if(i <= L && R <= j){
- lazy[p] = v;
- prop(p, L, R);
- return;
- }
- int mid = (L+R)/2;
- upd(2*p, L, mid, i, j, v);
- upd(2*p+1, mid+1, R, i, j, v);
- int qryLo = st[2*p];
- int qryHi = st[2*p+1];
- st[p] = qryLo + qryHi;
- }
- int qry(int p, int L, int R, int i, int j){
- prop(p, L, R);
- if(j < L || i > R) return 0;
- if(i <= L && R <= j) return st[p];
- int mid = (L+R)/2;
- int qryLo = qry(2*p, L, mid, i, j);
- int qryHi = qry(2*p+1, mid+1, R, i, j);
- return qryLo + qryHi;
- }
- public:
- SegTree_Sum(int sz){
- n = sz;
- st.assign(6*(n + 1), 0);
- lazy.assign(6*(n + 1), 0);
- }
- int qry(int i, int j){
- return qry(1, 1, n, i, j);
- }
- void upd(int i, int j, int v){
- upd(1, 1, n, i, j, v);
- }
- };
- int main() {
- ios::sync_with_stdio(false);
- int n,d,x,tot = 0;
- cin >> n >> d;
- // W(n);
- // W(d);
- SegTree_Sum st_sum(n);//st_sum é a soma dos x no intervalo com os depositos calculados
- SegTree_Max st_max(n);//st_max é o maior valor de st_sum[1,i] no intervalo
- vector<int> v(n+1);
- FOR2(i,1,n+1){
- cin >> x;
- v[i] = x;
- // W(i);
- // W(x);
- st_sum.upd(i,i,x);
- st_max.upd(i,i,st_sum.qry(1,i));
- // W(st_sum.qry(1,i));
- // W(st_max.qry(1,i));
- if(st_sum.qry(1,i+1) > d){
- cout << -1 << endl;
- return 0;
- }
- }
- FOR2(i,1,n+1){
- int val = st_sum.qry(1,i);
- if(v[i] == 0 && val < 0){
- int mx = st_max.qry(i+1,n);
- // W(val);
- // W(mx);
- mx = d - mx;//maior depósito possivel que não faça nenhum que vem depois estourar o limite
- // W(mx);
- if(val + mx < 0){
- cout << -1 << endl;
- return 0;
- }
- st_sum.upd(i,i,mx);
- st_max.upd(i,i,-1*st_max.qry(i,i));
- st_max.upd(i,i,st_sum.qry(1,i));
- tot++;
- }
- }
- cout << tot << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement