不要使用
#define min(a,b) ((a)<(b)?(a):(b))
这份代码能过:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 1;
struct Node{int l, r, val, tag;}tree[maxn << 2];
int n, m, R[maxn];
inline void pushup(int u){tree[u].val = min(tree[u<<1].val, tree[u<<1|1].val);}
inline void pushdown(int u){
if(tree[u].l == tree[u].r) return;
tree[u<<1].tag += tree[u].tag;
tree[u<<1|1].tag += tree[u].tag;
tree[u<<1].val += tree[u].tag;
tree[u<<1|1].val += tree[u].tag;
tree[u].tag = 0;
}
inline void build(int u, int l, int r){
tree[u].l = l; tree[u].r = r;
tree[u].tag = 0;
if(l == r){tree[u].val = R[l]; return;}
int mid = (l + r) >> 1;
build(u<<1, l, mid); build(u<<1|1, mid + 1, r);
pushup(u);
}
inline void upd(int u, int l, int r, int x){
if(tree[u].l > r || tree[u].r < l) return;
if(l <= tree[u].l && tree[u].r <= r){
tree[u].val += x;
if(tree[u].l != tree[u].r) tree[u].tag += x;
return;
}
pushdown(u);
upd(u<<1, l, r, x); upd(u<<1|1, l, r, x);
pushup(u);
}
inline int query(int u, int l, int r){
if(tree[u].l > r || tree[u].r < l) return (1<<30);
if(l <= tree[u].l && tree[u].r <= r) return tree[u].val;
pushdown(u);
return min(query(u<<1, l, r), query(u<<1|1, l, r));
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &R[i]);
build(1, 1, n);
for(int i = 1, D, S, T; i <= m; i++){
scanf("%d%d%d", &D, &S, &T);
upd(1, S, T, -D);
query(1, S, T);
if(query(1, S, T) < 0){
printf("-1\n%d", i);
return 0;
}
}
printf("0");
return 0;
}
而这份不能:
#include <cstdio>
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int maxn = 1e6 + 1;
struct Node{int l, r, val, tag;}tree[maxn << 2];
int n, m, R[maxn];
void pushup(int u){tree[u].val = min(tree[u<<1].val, tree[u<<1|1].val);}
void pushdown(int u){
if(tree[u].l == tree[u].r) return;
tree[u<<1].tag += tree[u].tag;
tree[u<<1|1].tag += tree[u].tag;
tree[u<<1].val += tree[u].tag;
tree[u<<1|1].val += tree[u].tag;
tree[u].tag = 0;
}
void build(int u, int l, int r){
tree[u].l = l; tree[u].r = r;
tree[u].tag = 0;
if(l == r){tree[u].val = R[l]; return;}
int mid = (l + r) >> 1;
build(u<<1, l, mid); build(u<<1|1, mid + 1, r);
pushup(u);
}
void upd(int u, int l, int r, int x){
if(tree[u].l > r || tree[u].r < l) return;
if(l <= tree[u].l && tree[u].r <= r){
tree[u].val += x;
if(tree[u].l != tree[u].r) tree[u].tag += x;
return;
}
pushdown(u);
upd(u<<1, l, r, x); upd(u<<1|1, l, r, x);
pushup(u);
}
int query(int u, int l, int r){
if(tree[u].l > r || tree[u].r < l) return (1<<30);
if(l <= tree[u].l && tree[u].r <= r) return tree[u].val;
pushdown(u);
return min(query(u<<1, l, r), query(u<<1|1, l, r));
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &R[i]);
build(1, 1, n);
for(int i = 1, D, S, T; i <= m; i++){
scanf("%d%d%d", &D, &S, &T);
upd(1, S, T, -D);
query(1, S, T);
if(query(1, S, T) < 0){
printf("-1\n%d", i);
return 0;
}
}
printf("0");
return 0;
}