3 条题解
-
1
#include<iostream> #include<algorithm> #include<cmath> #include<vector> #include<set> #include<string> #include<iomanip> #include<cstring> #include<ctime> #include<unordered_map> #include<stack> #include<queue> //***************************************************************************************************************** // .-~~~~~~~~~-._ _.-~~~~~~~~~-. // __.' ~. .~ `.__ // .'// \./ \\`. // .'// | \\`. // .'// .-~"""""""~~~~-._ | _,-~~~~"""""""~-. \\`. // .'//.-" `-. | .-' "-.\\`. // .'//______.============-.. \ | / ..-============.______\\`. //.'______________________________\|/______________________________`. //***************************************************************************************************************** using namespace std; const int o = 1e7 + 10; typedef pair<long, long>ll; long long a[o], s[o], l1[o], r1[o], c1[o], t = 0; void num(int l, int r, int c) { a[l] -= c; a[r + 1] += c; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); long long n, m; cin >> n >> m; long long l = 1, r = n; long long cmp = 0; for (int i = 1; i <= n; i++) { cin >> l1[i] >> r1[i] >> c1[i]; } while (l <= r) { for (int i = 1; i <= n; i++) { s[i] = m; a[i] = s[i] - s[i - 1]; } bool fg = 0; long long mid = l + r>> 1; for (int i = 1; i <= mid; i++) { num(l1[i], r1[i], c1[i]); } for (int i = 1; i <= n;i++) { s[i] = a[i] + s[i - 1]; if (s[i]<= 0) { fg = 1; } } if (fg) { r = mid-1; cmp = mid; } else { l = mid+1; } } if (cmp!=0) { cout << cmp; } else { cout << "impossible"; } }
信息
- ID
- 965
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 708
- 已通过
- 66
- 上传者