結果
問題 |
No.3214 small square
|
ユーザー |
![]() |
提出日時 | 2025-07-25 21:58:24 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 412 ms / 3,000 ms |
コード長 | 1,814 bytes |
コンパイル時間 | 3,631 ms |
コンパイル使用メモリ | 264,440 KB |
実行使用メモリ | 33,732 KB |
最終ジャッジ日時 | 2025-07-25 21:59:07 |
合計ジャッジ時間 | 15,991 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000005 #define Inf64 1000000000000000001LL long long op(long long a,long long b){ return max(a,b); } long long e(){ return 0; } long long mapping(long long a,long long b){ return a + b; } long long composition(long long a,long long b){ return a + b; } long long id(){ return 0; } int main(){ long long N,A; cin>>N>>A; A *= 2; vector<long long> x(N),y(N),v(N); rep(i,N){ cin>>x[i]>>y[i]>>v[i]; x[i] *= 2; y[i] *= 2; } auto tx = x; rep(i,N){ tx.push_back(x[i]+A); tx.push_back(x[i]+A+1); tx.push_back(x[i]+A-1); } sort(tx.begin(), tx.end()); tx.erase(unique(tx.begin(), tx.end()), tx.end()); vector<long long> ty; rep(i,N){ ty.push_back(y[i]-A); ty.push_back(y[i]+1); } sort(ty.begin(), ty.end()); ty.erase(unique(ty.begin(), ty.end()), ty.end()); vector Add(tx.size(),vector<vector<long long>>()); rep(i,N){ int xx = lower_bound(tx.begin(), tx.end(), x[i]) - tx.begin(); int ll = lower_bound(ty.begin(), ty.end(), y[i]-A) - ty.begin(); int rr = lower_bound(ty.begin(), ty.end(), y[i]+1) - ty.begin(); Add[xx].push_back({ll,rr,v[i]}); } lazy_segtree<long long, op, e, long long, mapping, composition, id> seg(ty.size()); long long ans = 0; int ci = 0; rep(i,tx.size()){ rep(j,Add[i].size()){ int l = Add[i][j][0]; int r = Add[i][j][1]; long long v = Add[i][j][2]; seg.apply(l, r, v); } while(tx[i] - tx[ci] > A){ rep(j,Add[ci].size()){ int l = Add[ci][j][0]; int r = Add[ci][j][1]; long long v = Add[ci][j][2]; seg.apply(l, r, -v); } ci++; } ans = max(ans, seg.all_prod()); } cout<<ans<<endl; return 0; }