結果
| 問題 | No.2808 Concentration |
| ユーザー |
 ぷら
|
| 提出日時 | 2024-07-12 23:15:01 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 481 ms / 2,000 ms |
| コード長 | 5,511 bytes |
| コンパイル時間 | 3,413 ms |
| コンパイル使用メモリ | 150,304 KB |
| 最終ジャッジ日時 | 2025-02-22 05:25:58 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 57 |
ソースコード
#include <string.h>#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <cfloat>#include <climits>#include <cmath>#include <complex>#include <ctime>#include <deque>#include <fstream>#include <functional>#include <iomanip>#include <iostream>#include <iterator>#include <list>#include <map>#include <memory>#include <queue>#include <random>#include <set>#include <stack>#include <string>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>using namespace std;using ll = long long;using pii = pair<int,int>;using pll = pair<ll,ll>;template <typename T> using vc = vector<T>;template <typename T> using vvc = vector<vector<T>>;template <typename T> using vvvc = vector<vector<vector<T>>>;template<class T> using pq = priority_queue<T,vector<T>,greater<T>>;template <class T, class S> inline bool chmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); }template <class T, class S> inline bool chmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); }int dx4[] = {1,0,-1,0};int dy4[] = {0,1,0,-1};#define overload5(a, b, c, d, e, name, ...) name#define overload4(a, b, c, d, name, ...) name#define REP0(n) for(ll jidlsjf = 0; jidlsjf < n; ++jidlsjf)#define REP1(i, n) for(ll i = 0; i < (n); ++i)#define REP2(i, a, b) for(ll i = (a); i < (b); ++i)#define REP3(i, a, b, c) for(ll i = (a); i < (b); i += (c))#define rep(...) overload4(__VA_ARGS__, REP3, REP2, REP1, REP0)(__VA_ARGS__)#define per0(n) for(int jidlsjf = 0; jidlsjf < (n); ++jidlsjf)#define per1(i, n) for(ll i = (n)-1; i >= 0; --i)#define per2(i, a, b) for(ll i = (a)-1; i >= b; --i)#define per3(i, a, b, c) for(ll i = (a)-1; i >= (b); i -= (c))#define per(...) overload4(__VA_ARGS__, per3, per2, per1, per0)(__VA_ARGS__)#define setbits(j, n) for(ll iiiii = (n), j = lowbit(iiiii); iiiii; iiiii ^= 1 << j, j = lowbit(iiiii))#define perm(v) for(bool permrepflag = true; (permrepflag ? exchange(permrepflag, false) : next_permutation(all(v)));)#define fi first#define se second#define pb push_back#define ppb pop_back#define ppf pop_front#define drop(s) cout << #s << endl, exit(0)#define si(c) (int)(c).size()#define lb(c, x) distance((c).begin(), lower_bound(all(c), (x)))#define lbg(c, x) distance((c).begin(), lower_bound(all(c), (x), greater{}))#define ub(c, x) distance((c).begin(), upper_bound(all(c), (x)))#define ubg(c, x) distance((c).begin(), upper_bound(all(c), (x), greater{}))#define rng(v, l, r) v.begin() + (l), v.begin() + (r)#define all(c) c.begin(), c.end()#define rall(c) c.rbegin(), c.rend()#define SORT(v) sort(all(v))#define REV(v) reverse(all(v))#define UNIQUE(x) SORT(x), x.erase(unique(all(x)), x.end())#define MIN(v) *min_element(all(v))#define MAX(v) *max_element(all(v))#define overload2(_1, _2, name, ...) name#define vec(type, name, ...) vector<type> name(__VA_ARGS__)#define vv(type, name, h, ...) vector<vector<type>> name(h, vector<type>(__VA_ARGS__))#define vvv(type, name, h, w, ...) vector<vector<vector<type>>> name(h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))ll inf = 1001001001001001001;template <typename T>struct LazySegmentTree {int n;vector<T> dat;vector<T>lazy;LazySegmentTree() {};LazySegmentTree(int N) {n = 1;while(n < N) {n *= 2;}dat.resize(n*2,0);lazy.resize(n*2,0);}void eval(int k,int l,int r) {if(lazy[k] == 0) return;if(k < n) {lazy[k*2] += lazy[k];lazy[k*2+1] += lazy[k];}dat[k] += lazy[k];lazy[k] = 0;}void update(int a, int b, T x, int k, int l, int r) {eval(k,l,r);if(a <= l && r <= b) {lazy[k] += x;eval(k,l,r);}else if(a < r && l < b) {update(a, b, x, k*2, l, (l+r)/2);update(a, b, x, k*2+1, (l+r)/2, r);dat[k] = max(dat[k*2],dat[k*2+1]);}}void update(int a, int b, T x) {//[a,b)update(a, b, x, 1, 0, n);}T query_sub(int a, int b, int k, int l, int r) {eval(k,l,r);if (r <= a || b <= l) {return -inf;}else if (a <= l && r <= b) {return dat[k];}else {T vl = query_sub(a, b, k*2, l, (l+r)/2);T vr = query_sub(a, b, k*2+1, (l+r)/2, r);return max(vl,vr);}}T query(int a, int b) {//[a,b)return query_sub(a, b, 1, 0, n);}};int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n,s,h;cin >> n >> s >> h;vc<int>x(n),y(n),z(n),cmp;rep(i,n) {cin >> x[i] >> y[i] >> z[i];cmp.pb(x[i]);cmp.pb(y[i]);}cmp.pb(2002002002);UNIQUE(cmp);LazySegmentTree<ll>Seg(si(cmp));vvc<pii>tmp(si(cmp));rep(i,n) {int it1 = lower_bound(all(cmp),x[i])-cmp.begin();int it2 = lower_bound(all(cmp),y[i])-cmp.begin();tmp[it2].pb({it1,z[i]});}ll ans = 0;vc<ll>dp(si(cmp));rep(i,si(cmp)-1) {for(auto j:tmp[i]) {Seg.update(0,j.fi+1,j.se);}int it = lower_bound(all(cmp),cmp[i]-s)-cmp.begin();ll mx = Seg.query(it,i+1);chmax(ans,mx);int nxt = lower_bound(all(cmp),cmp[i]+h)-cmp.begin();chmax(dp[nxt],mx);chmax(dp[i+1],dp[i]);Seg.update(i,i+1,dp[i]);}cout << ans << "\n";}