結果

問題 No.1625 三角形の質問
ユーザー batasanblogbatasanblog
提出日時 2023-04-06 20:25:39
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,995 ms / 6,000 ms
コード長 5,416 bytes
コンパイル時間 5,063 ms
コンパイル使用メモリ 272,488 KB
実行使用メモリ 172,492 KB
最終ジャッジ日時 2024-04-10 16:02:37
合計ジャッジ時間 34,061 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 88 ms
13,348 KB
testcase_02 AC 649 ms
53,088 KB
testcase_03 AC 717 ms
69,872 KB
testcase_04 AC 486 ms
45,084 KB
testcase_05 AC 1,156 ms
90,140 KB
testcase_06 AC 1,896 ms
138,896 KB
testcase_07 AC 1,856 ms
137,048 KB
testcase_08 AC 1,888 ms
137,380 KB
testcase_09 AC 1,995 ms
138,524 KB
testcase_10 AC 1,935 ms
139,396 KB
testcase_11 AC 1,921 ms
138,324 KB
testcase_12 AC 1,895 ms
137,008 KB
testcase_13 AC 1,898 ms
137,992 KB
testcase_14 AC 1,877 ms
138,904 KB
testcase_15 AC 1,919 ms
137,400 KB
testcase_16 AC 434 ms
51,668 KB
testcase_17 AC 694 ms
145,204 KB
testcase_18 AC 314 ms
9,464 KB
testcase_19 AC 865 ms
172,492 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
//using mint = static_modint<998244353>;
//using mint = modint;
using mint = static_modint<1000000007>;
using vm = vector<mint>;
using vvm = vector<vm>;
ostream &operator<<(ostream &o,const mint &m){cout<<m.val();return o;}
using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using pl = pair<ll,ll>;
#define rep(i,n) for(ll i=0;i<(ll)(n);++i)
#define reps(i,s,n) for(ll i=(s);i<(ll)(n);++i)
#define rep1(i,n) for(ll i=1;i<=(ll)(n);++i)
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
const long long INF = 1e18;


// CUT begin
// 逆元を要求しない領域木
template <class S, S (*op)(S, S), S (*e)(), class Coordinate> class rangetree {
    int n;
    using Pt = std::pair<Coordinate, Coordinate>;
    std::vector<Pt> _pts;
    std::vector<std::vector<Pt>> _range2yxs;
    std::vector<atcoder::segtree<S, op, e>> segtrees;
    void _set(int v, Pt p, S val) {
        auto i = std::distance(
            _range2yxs[v].begin(),
            std::lower_bound(_range2yxs[v].begin(), _range2yxs[v].end(), Pt{p.second, p.first}));
        segtrees[v].set(i, val);
    }
    void _add(int v, Pt p, S val) {
        auto i = std::distance(
            _range2yxs[v].begin(),
            std::lower_bound(_range2yxs[v].begin(), _range2yxs[v].end(), Pt{p.second, p.first}));
        segtrees[v].set(i, op(segtrees[v].get(i), val));
    }
    S _prod(int v, Coordinate yl, Coordinate yr) const {
        auto comp = [&](const Pt &l, const Pt &r) { return l.first < r.first; };
        auto il = std::distance(
            _range2yxs[v].begin(),
            std::lower_bound(_range2yxs[v].begin(), _range2yxs[v].end(), Pt{yl, yl}, comp));
        auto ir = std::distance(
            _range2yxs[v].begin(),
            std::lower_bound(_range2yxs[v].begin(), _range2yxs[v].end(), Pt{yr, yr}, comp));
        return segtrees[v].prod(il, ir);
    }

public:
    rangetree() = default;
    void add_point(Coordinate x, Coordinate y) noexcept { _pts.emplace_back(x, y); }
    void build() {
        std::sort(_pts.begin(), _pts.end());
        _pts.erase(std::unique(_pts.begin(), _pts.end()), _pts.end());
        n = _pts.size();

        _range2yxs.resize(n * 2);
        for (int i = 0; i < n; i++) _range2yxs[n + i] = {{_pts[i].second, _pts[i].first}};
        for (int i = n - 1; i > 0; i--) {
            auto &lch = _range2yxs[i * 2];
            auto &rch = _range2yxs[i * 2 + 1];
            std::merge(
                lch.begin(), lch.end(), rch.begin(), rch.end(), std::back_inserter(_range2yxs[i]));
            _range2yxs[i].erase(
                std::unique(_range2yxs[i].begin(), _range2yxs[i].end()), _range2yxs[i].end());
        }
        for (const auto &v : _range2yxs) segtrees.emplace_back(v.size());
    }
    void set(Coordinate x, Coordinate y, S val) {
        int i = std::distance(_pts.begin(), std::lower_bound(_pts.begin(), _pts.end(), Pt{x, y}));
        assert(i < n and _pts[i] == std::make_pair(x, y));
        for (i += n; i; i >>= 1) _set(i, {x, y}, val);
    }
    void add(Coordinate x, Coordinate y, S val) {
        int i = std::distance(_pts.begin(), std::lower_bound(_pts.begin(), _pts.end(), Pt{x, y}));
        assert(i < n and _pts[i] == std::make_pair(x, y));
        for (i += n; i; i >>= 1) _add(i, {x, y}, val);
    }
    S prod(Coordinate xl, Coordinate xr, Coordinate yl, Coordinate yr) const {
        auto comp = [](const Pt &l, const Pt &r) { return l.first < r.first; };
        int l = n + std::distance(_pts.begin(),
                                  std::lower_bound(_pts.begin(), _pts.end(), Pt{xl, yr}, comp));
        int r = n + std::distance(_pts.begin(),
                                  std::lower_bound(_pts.begin(), _pts.end(), Pt{xr, yr}, comp));
        S ret = e();
        while (l < r) {
            if (l & 1) ret = op(ret, _prod(l++, yl, yr));
            if (r & 1) ret = op(ret, _prod(--r, yl, yr));
            l >>= 1, r >>= 1;
        }
        return ret;
    }
    S get(Coordinate x, Coordinate y) const { return prod(x, x + 1, y, y + 1); }
};
#ifdef DEBUG
#include <debug.hpp>
#endif

//struct S{
	//ll minx,maxx;
	//ll area;
//}
using S=ll;
S op(S a,S b){
	return max(a,b);
}
S e(){
	return -1;
}
int main(){
#ifdef DEBUG
	cout << "--- Input ---" << endl;
#endif
	ll N,Q;cin>>N>>Q;
	vl X(N),Y(N),A(N);
	rangetree<S,op,e,ll> seg;
	rep(i,N){
		ll a,b,c,d,e,f;cin>>a>>b>>c>>d>>e>>f;
		ll x=min({a,c,e});
		ll y=max({a,c,e});
		ll area=abs((e-a)*(d-b)-(f-b)*(c-a));
		seg.add_point(x,y);
		X.at(i)=x;Y.at(i)=y;A.at(i)=area;
	}
	vl T(Q),L(Q),R(Q);
	rep(qi,Q){
		ll t;cin>>t;
		T.at(qi)=t;
		if(t==1){
			ll a,b,c,d,e,f;cin>>a>>b>>c>>d>>e>>f;
			ll x=min({a,c,e});
			ll y=max({a,c,e});
			ll area=abs((e-a)*(d-b)-(f-b)*(c-a));
			seg.add_point(x,y);
			X.push_back(x);Y.push_back(y);A.push_back(area);
		}else{
			cin>>L.at(qi)>>R.at(qi);
		}
	}
	
	seg.build();
	rep(i,N){
		seg.add(X.at(i),Y.at(i),A.at(i));
	}
#ifdef DEBUG
	cout<<X<<Y<<A;
	rep(i,N){
		cout<<seg.get(X.at(i),Y.at(i))<<" ";
	}
	cout<<endl;
	cout << "--- Logic ---" << endl;
#endif

	ll p=N;
	rep(qi,Q){
		if(T.at(qi)==1){
			seg.add(X.at(p),Y.at(p),A.at(p));
			++p;
		}else{
			cout<<seg.prod(L.at(qi),R.at(qi)+1,L.at(qi),R.at(qi)+1)<<endl;
		}
	}
#ifdef DEBUG
	cout << "--- Answer ---" << endl;
#endif

	return 0;
}
//cout << fixed << setprecision(9);
0