結果
| 問題 | No.1074 増殖 |
| ユーザー |
 milanis48663220
|
| 提出日時 | 2020-06-05 23:19:24 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 7,965 bytes |
| コンパイル時間 | 782 ms |
| コンパイル使用メモリ | 77,984 KB |
| 最終ジャッジ日時 | 2024-11-14 22:37:17 |
| 合計ジャッジ時間 | 1,552 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp:16:24: error: 'numeric_limits' was not declared in this scope
16 | static const T idm=numeric_limits<T>::min();
| ^~~~~~~~~~~~~~
main.cpp:16:40: error: expected primary-expression before '>' token
16 | static const T idm=numeric_limits<T>::min();
| ^
main.cpp:16:46: error: no matching function for call to 'min()'
16 | static const T idm=numeric_limits<T>::min();
| ~~~~~^~
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/string:50,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/locale_classes.h:40,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/ios_base.h:41,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ios:42,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ostream:38,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/iostream:39,
from main.cpp:1:
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
230 | min(const _Tp& __a, const _Tp& __b)
| ^~~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algobase.h:230:5: note: template argument deduction/substitution failed:
main.cpp:16:46: note: candidate expects 2 arguments, 0 provided
16 | static const T idm=numeric_limits<T>::min();
| ~~~~~^~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
278 | min(const _Tp& __a, const _Tp& __b, _Compare __
ソースコード
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
const ll INF = 1e7;
template<typename T>
class SegmentTreeBeats{
int n,hi;
static const T idm=numeric_limits<T>::min();
static const T idM=numeric_limits<T>::max(),idl=idM;
struct Node{
T Max,Max_second,Min,Min_second,sum,laz_val,laz_add;
int Max_count,Min_count,len;
Node():Max(idm),Max_second(idm),Min(idM),Min_second(idM)
,laz_val(idl),laz_add(0),len(1){}
};
vector<Node> Nodes;
inline void calc(int k){
Node &p=Nodes[k];
Node l=Nodes[k<<1|0];
Node r=Nodes[k<<1|1];
p.sum=l.sum+r.sum;
if (l.Max<r.Max){
p.Max=r.Max;
p.Max_count=r.Max_count;
p.Max_second=max(l.Max,r.Max_second);
} else if (r.Max<l.Max){
p.Max=l.Max;
p.Max_count=l.Max_count;
p.Max_second=max(l.Max_second,r.Max);
} else {
p.Max=l.Max;
p.Max_count=l.Max_count+r.Max_count;
p.Max_second=max(l.Max_second,r.Max_second);
}
if (l.Min<r.Min){
p.Min=l.Min;
p.Min_count=l.Min_count;
p.Min_second=min(l.Min_second,r.Min);
} else if (r.Min<l.Min){
p.Min=r.Min;
p.Min_count=r.Min_count;
p.Min_second=min(l.Min,r.Min_second);
} else {
p.Min=l.Min;
p.Min_count=l.Min_count+r.Min_count;
p.Min_second=min(l.Min_second,r.Min_second);
}
}
inline void update_node_min(int k,T x){
Node &node=Nodes[k];
node.sum+=(x-node.Max)*node.Max_count;
if (node.Max==node.Min) node.Max=node.Min=x;
else if (node.Max==node.Min_second) node.Max=node.Min_second=x;
else node.Max=x;
if (node.laz_val!=idl&&node.laz_val<x) node.laz_val=x;
}
inline void update_node_max(int k,T x){
Node &node=Nodes[k];
node.sum+=(x-node.Min)*node.Min_count;
if (node.Min==node.Max) node.Min=node.Max=x;
else if (node.Min==node.Max_second) node.Min=node.Max_second=x;
else node.Min=x;
if (node.laz_val!=idl&&x<node.laz_val) node.laz_val=x;
}
inline void update_node_add(int k,T x){
Node &node=Nodes[k];
node.Max+=x;
if (node.Max_second!=idm) node.Max_second+=x;
node.Min+=x;
if (node.Min_second!=idM) node.Min_second+=x;
node.sum+=x*node.len;
(node.laz_val!=idl?node.laz_val:node.laz_add)+=x;
}
inline void update_node_val(int k,T x){
Node &node=Nodes[k];
node.Max=x; node.Max_second=idm;
node.Min=x; node.Min_second=idM;
node.Max_count=node.Min_count=node.len;
node.sum=x*node.len;
node.laz_val=x; node.laz_add=0;
}
inline void update_sub_min(int k,T x){
if (Nodes[k].Max<=x) return;
if (Nodes[k].Max_second<x){
update_node_min(k,x); return;
}
propagate(k);
update_sub_min(k<<1|0,x);
update_sub_min(k<<1|1,x);
calc(k);
}
inline void update_sub_max(int k,T x){
if (x<=Nodes[k].Min) return;
if (x<Nodes[k].Min_second){
update_node_max(k,x); return;
}
propagate(k);
update_sub_max(k<<1|0,x);
update_sub_max(k<<1|1,x);
calc(k);
}
inline void propagate(int k){
if (k>=n) return;
Node &p=Nodes[k];
if (p.laz_val!=idl){
update_node_val(k<<1|0,p.laz_val);
update_node_val(k<<1|1,p.laz_val);
p.laz_val=idl; return;
}
if (p.laz_add!=0){
update_node_add(k<<1|0,p.laz_add);
update_node_add(k<<1|1,p.laz_add);
p.laz_add=0;
}
if (p.Max<Nodes[k<<1|0].Max) update_node_min(k<<1|0,p.Max);
if (p.Max<Nodes[k<<1|1].Max) update_node_min(k<<1|1,p.Max);
if (Nodes[k<<1|0].Min<p.Min) update_node_max(k<<1|0,p.Min);
if (Nodes[k<<1|1].Min<p.Min) update_node_max(k<<1|1,p.Min);
}
inline void thrust(int k){
if (k==n<<1) return;
int kc=__builtin_ctz(k);
for (int i=hi;i-->kc;) propagate(k>>i);
}
inline void thrust(int l,int r){
if (r==n<<1){thrust(l); return;}
int h=hi,x=l^r;
for (;!(x>>--h)&&h;) propagate(l>>h);
int lc=__builtin_ctz(l),rc=__builtin_ctz(r);
for (int i=h+1;i-->lc;) propagate(l>>i);
for (int i=h+1;i-->rc;) propagate(r>>i);
}
inline void recalc(int k){
k>>=__builtin_ctz(k);
while(k>>=1) calc(k);
}
public:
SegmentTreeBeats(int n_){init(n_);}
void init(int n_){
n=hi=1;
while(n<n_) n<<=1,++hi;
Nodes.resize(n<<1);
}
void build(const vector<T> &v){
for (int i=0;i<v.size();++i){
Nodes[i+n].Max=Nodes[i+n].Min=Nodes[i+n].sum=v[i];
Nodes[i+n].Max_count=Nodes[i+n].Min_count=Nodes[i+n].len=1;
}
for (int i=n-1;i;--i){
calc(i);
Nodes[i].len=Nodes[i<<1|0].len+Nodes[i<<1|1].len;
}
}
void update_min(int a,int b,T x){
if (a>=b) return;
thrust(a+=n),thrust(b+=n);
for (int l=a,r=b;l<r;l>>=1,r>>=1){
if (l&1) update_sub_min(l++,x);
if (r&1) update_sub_min(--r,x);
}
recalc(a),recalc(b);
}
void update_max(int a,int b,T x){
if (a>=b) return;
thrust(a+=n),thrust(b+=n);
for (int l=a,r=b;l<r;l>>=1,r>>=1){
if (l&1) update_sub_max(l++,x);
if (r&1) update_sub_max(--r,x);
}
recalc(a),recalc(b);
}
void update_add(int a,int b,T x){
if (a>=b) return;
thrust(a+=n),thrust(b+=n);
for (int l=a,r=b;l<r;l>>=1,r>>=1){
if (l&1) update_node_add(l++,x);
if (r&1) update_node_add(--r,x);
}
recalc(a),recalc(b);
}
void update_val(int a,int b,T x){
if (a>=b) return;
thrust(a+=n),thrust(b+=n);
for (int l=a,r=b;l<r;l>>=1,r>>=1){
if (l&1) update_node_val(l++,x);
if (r&1) update_node_val(--r,x);
}
recalc(a),recalc(b);
}
T query_min(int a,int b){
if (a>=b) return idM;
thrust(a+=n),thrust(b+=n);
T vl=idM,vr=idM;
for (int l=a,r=b;l<r;l>>=1,r>>=1){
if (l&1) vl=min(vl,Nodes[l++].Min);
if (r&1) vr=min(vr,Nodes[--r].Min);
}
return min(vl,vr);
}
T query_max(int a,int b){
if (a>=b) return idm;
thrust(a+=n),thrust(b+=n);
T vl=idm,vr=idm;
for (int l=a,r=b;l<r;l>>=1,r>>=1){
if (l&1) vl=max(vl,Nodes[l++].Max);
if (r&1) vr=max(vr,Nodes[--r].Max);
}
return max(vl,vr);
}
T query_sum(int a,int b){
if (a>=b) return 0;
thrust(a+=n),thrust(b+=n);
T vl=0,vr=0;
for (int l=a,r=b;l<r;l>>=1,r>>=1){
if (l&1) vl+=Nodes[l++].sum;
if (r&1) vr+=Nodes[--r].sum;
}
return vl+vr;
}
T operator[](int i){return Nodes[i+n].sum;}
};
int N;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout << setprecision(10) << fixed;
cin >> N;
int M = 40005;
int K = 20000;
vector<ll> a(M);
SegmentTreeBeats<ll> sgt_max(M);
SegmentTreeBeats<ll> sgt_min(M);
sgt_max.build(a);
sgt_min.build(a);
for(int i = 0; i < N; i++){
ll x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
x1 += K; x2 += K;
ll prev = sgt_max.query_sum(x1, x2+1)-sgt_min.query_sum(x1, x2+1);
sgt_max.update_max(x1, x2, y2);
sgt_min.update_min(x1, x2, y1);
ll cur = sgt_max.query_sum(x1, x2+1)-sgt_min.query_sum(x1, x2+1);
cout << cur-prev << endl;
}
}