結果
問題 |
No.3214 small square
|
ユーザー |
|
提出日時 | 2025-07-25 22:58:41 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,963 ms / 3,000 ms |
コード長 | 6,473 bytes |
コンパイル時間 | 2,705 ms |
コンパイル使用メモリ | 223,824 KB |
実行使用メモリ | 36,252 KB |
最終ジャッジ日時 | 2025-07-25 22:59:38 |
合計ジャッジ時間 | 51,720 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h> using namespace std; using SS = long long; using FF = long long; long long inf = 1e18; class LazySegmentTree{ //ACL超参考にしてる というかパクリ. //verify十分だけど注意. private: vector<SS> dat; vector<FF> lazy; public: int siz = -1,n = -1,log = 0; SS op(SS a,SS b){return max(a,b);} SS mapping(FF f, SS x){return f+x;} FF composition(FF f, FF g){return f+g;} SS e(){return -inf;} FF id(){return 0;} //op区間演算 mapping lazy→data composition lazy→lazy //e 単位元 id map(id,a)=a LazySegmentTree(int N){init(N);} LazySegmentTree(const vector<SS> &A){//配列サイズに合わせる. siz = 1; n = A.size(); log = 0; while(siz < n) siz <<= 1,log++; dat.resize(siz*2,e()); lazy.resize(siz,id()); for(int i=0; i<n; i++) dat.at(i+siz) = A.at(i); for(int i=siz-1; i>0; i--) merge(i); } void init(int N){ //単位元になる. siz = 1; n = N; log = 0; while(siz < n) siz *= 2,log++; dat.assign(siz*2,e()); lazy.assign(siz,id()); } void init(const vector<SS> &A){ //配列サイズに合わせる. siz = 1; n = A.size(); log = 0; while(siz < n) siz <<= 1,log++; dat.resize(siz*2,e()); lazy.assign(siz,id()); for(int i=0; i<n; i++) dat.at(i+siz) = A.at(i); for(int i=siz-1; i>0; i--) merge(i); } private: void eval(int u,FF f){ //u番目にfを適用したあと保留. if(u == 0) return; dat.at(u) = mapping(f,dat.at(u)); if(u < siz) lazy.at(u) = composition(f,lazy.at(u)); } void spread(int u){ //uにあるFF保留を伝播. if(u == 0 || id() == lazy.at(u)) return; eval(2*u,lazy.at(u)); eval(2*u+1,lazy.at(u)); lazy.at(u) = id(); } void merge(int u){dat.at(u) = op(dat.at(u*2),dat.at(u*2+1));} //子2つからマージ. public: void set(int pos,SS x){ //1点変更. assert(0 <= pos && pos < n); pos += siz; for(int i=log; i>0; i--) spread(pos>>i); dat.at(pos) = x; while(pos > 1) pos >>= 1,merge(pos); } void update(int pos,FF f){ //1点更新 変数抜かして区間更新になってないか注意!. assert(0 <= pos && pos < n); pos += siz; for(int i=log; i>0; i--) spread(pos>>i); dat.at(pos) = mapping(f,dat.at(pos)); while(pos > 1) pos >>= 1,merge(pos); } void update(int l,int r,FF f){ //区間更新. assert(0 <= l && l <= r && r <= n); if(l == r) return; l += siz; r += siz; for(int i=log; i>0; i--){ if(((l>>i)<<i) != l) spread(l>>i); if(((r>>i)<<i) != r) spread((r-1)>>i); } int memoL = l,memoR = r; while(l < r){ if(l&1) eval(l++,f); if(r&1) eval(--r,f); l >>= 1; r >>= 1; } l = memoL,r = memoR; while((l&1) == 0) l >>= 1; while((r&1) == 0) r >>= 1; r--; //-1注意. while(l > 1) l >>= 1,merge(l); while(r > 1) r >>= 1,merge(r); } SS get(int pos){ //1点取得. assert(0 <= pos && pos < n); pos += siz; for(int i=log; i>0; i--) spread(pos>>i); return dat.at(pos); } SS rangeans(int l,int r){ //区間取得. assert(0 <= l && l <= r && r <= n); if(l == r) return e(); l += siz; r += siz; for(int i=log; i>0; i--){ if(((l>>i)<<i) != l) spread(l>>i); if(((r>>i)<<i) != r) spread((r-1)>>i); } SS retl = e(),retr = e(); while(l < r){ if(l&1) retl = op(retl,dat.at(l++)); if(r&1) retr = op(dat.at(--r),retr); l >>= 1; r >>= 1; } return op(retl,retr); } SS allrange(){return dat.at(1);} //全体取得. int maxright(const function<bool(SS)> f,int l = 0){ assert(0 <= l && l <= n && f(e())); if(l == n) return n; l += siz; for(int i=log; i>0; i--) spread(l>>i); SS now = e(); do{ while(l%2 == 0) l >>= 1; SS next = op(now,dat.at(l)); if(f(next) == false){ while(l < siz){ spread(l); l <<= 1; next = op(now,dat.at(l)); if(f(next)) now = next,l++; } return l-siz; } now = next; l++; }while((l&-l) != l); return n; } int minleft(const function<bool(SS)> f,int r = -1){ if(r == -1) r = n; assert(0 <= r && r <= n && f(e())); if(r == 0) return 0; r += siz; for(int i=log; i>0; i--) spread((r-1)>>i); SS now = e(); do{ r--; while(r&1) r >>= 1; if(r == 0) r = 1; SS next = op(dat.at(r),now); if(f(next) == false){ while(r < siz){ spread(r); r <<= 1; r++; next = op(now,dat.at(r)); if(f(next)) now = next,r--; } return r+1-siz; } now = next; }while((r&-r) != r); return 0; } }; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int N,A; cin >> N >> A; vector<tuple<long long,long long,long long>> XYV(N); for(auto &[x,y,v] : XYV) cin >> x >> y >> v; long long answer = 0; for(int dy=0; dy<=1; dy++){ vector<int> Ys; for(auto [x,y,v] : XYV) Ys.push_back(y-A+dy),Ys.push_back(y+1); sort(Ys.begin(),Ys.end()); Ys.erase(unique(Ys.begin(),Ys.end()),Ys.end()); for(int dx=0; dx<=1; dx++){ map<int,vector<tuple<int,int,long long>>> M; for(auto [x,y,v] : XYV){ int posl = lower_bound(Ys.begin(),Ys.end(),y-A+dy)-Ys.begin(); int posr = lower_bound(Ys.begin(),Ys.end(),y+1)-Ys.begin(); M[x-A+dx].push_back({posl,posr,v}); M[x+1].push_back({posl,posr,-v}); } LazySegmentTree Z(vector<SS>(Ys.size(),0LL)); for(auto [k,v] : M){ for(auto [l,r,add] : v) Z.update(l,r,add); answer = max(answer,Z.allrange()); } } } cout << answer << endl; }