結果
問題 | No.1625 三角形の質問 |
ユーザー |
![]() |
提出日時 | 2021-08-12 17:37:01 |
言語 | cLay (20241019-1) |
結果 |
AC
|
実行時間 | 492 ms / 6,000 ms |
コード長 | 1,023 bytes |
コンパイル時間 | 7,423 ms |
コンパイル使用メモリ | 226,896 KB |
実行使用メモリ | 78,464 KB |
最終ジャッジ日時 | 2024-07-05 15:24:00 |
合計ジャッジ時間 | 18,125 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 19 |
ソースコード
struct T { ll v; T(){ } T(ll i){ v=i; } void operator=(ll i){ v=i; } void operator+=(T a){ v>?=a.v; } }; T operator-(T a,T b){ return a; } bool operator<(T a,T b){ return a.v<b.v; } rangeTree2d<T,int,int>t; int dd1[2d5],dd2[]; T ww[]; struct Q { int t; ll l,r,s; }; Q qs[1d5]; ll area(ll a,ll b,ll c,ll d,ll e,ll f){ return abs((c-a)*(f-b)-(d-b)*(e-a)); } int l_offs=int_inf; { ll@n,@q; rep(i,n){ ll@a,@b,@c,@d,@e,@f; ll l=min(a,c,e); ll r=max(a,c,e); ll s=area(a,b,c,d,e,f); dd1[i]=l_offs-l; dd2[i]=r; ww[i].v=s; } ll m=n; rep(i,q){ ll@t; qs[i].t=t; if(t&1){ ll@a,@b,@c,@d,@e,@f; ll l=min(a,c,e); ll r=max(a,c,e); ll s=area(a,b,c,d,e,f); dd1[m]=l_offs-l; dd2[m]=r; ww[m].v=0; ++m; qs[i].l=l; qs[i].r=r; qs[i].s=s; }else{ ll@l,@r; qs[i].l=l; qs[i].r=r; } } t.build(m,dd1,dd2,ww); rep(i,q){ if(qs[i].t&1){ t.add(l_offs-qs[i].l,qs[i].r,qs[i].s); }else{ wt(t.query(0,l_offs-qs[i].l+1,0,qs[i].r+1).v?:-1); } } }