题解 | #定义变量#

#include #include

#define x first #define y second #define int long long #define PII pair<int,int> #define debug printf("++zhangyx++\n");

using namespace std;

const int INF = 0x3f3f3f3f; const int N = 1e7;

unordered_map<int,int>mp;

const int mod = 1e7;

int r[N]; struct node { int d,s,t;
}a[N]; int ans; int c[N]; int b[N]; int n,m;

bool check(int x) //二分的可行性函数 其实也不是很难想
{

for(int i=1;i<=n;i++) c[i] = b[i];

for(int i=1;i<=x;i++)
{

c[a[i].s]-=a[i].d;  
c[a[i].t+1]+=a[i].d; 

} for(int i=1;i<=n;i++) { c[i]+=c[i-1]; if(c[i]<0) return false; }

return true; }

void solve() { cin >> n >> m;

for(int i=1;i<=n;i++) cin >> r[i]; for(int i=1;i<=n;i++) b[i] = r[i]-r[i-1];

for(int i=1;i<=m;i++) cin >> a[i].d>> a[i].s>> a[i].t;

int l = 1,r =m; //答案的区间 就是在哪一天会有负值的情况
int mid;//而可行性函数就是判断 是否在这几天内会有 小于0或大于0的情况 //因为答案貌似满足在某一点之前都可行 在这后就不可行了 //因此 就 二分 while(l<=r) { mid = (l+r)>>1; if(check(mid)) ans=mid,l = mid+1; else r = mid -1; }

if(ans==m) cout << 0 <<endl;

else { cout << -1 <<endl; cout << ans + 1<<endl;
//·····之处 }

}

signed main() { std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

int T = 1;

// cin >> T;

while (T--) { solve(); }

return 0;

}