結果
問題 | No.1625 三角形の質問 |
ユーザー |
|
提出日時 | 2021-07-24 06:57:59 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 12,211 bytes |
コンパイル時間 | 18,098 ms |
コンパイル使用メモリ | 238,296 KB |
最終ジャッジ日時 | 2025-01-23 09:27:51 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 2 WA * 17 |
ソースコード
#pragma GCC target("avx2")//#pragma GCC target("avx")//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")#pragma GCC optimize("O3")//#pragma GCC optimize("Ofast")//#pragma GCC optimize("unroll-loops")// #include<bits/stdc++.h>// #include <array>#include <vector>// #include <list>// #include <forward_list>#include <deque>#include <queue>#include <stack>// #include <bitset>#include <unordered_map>#include <map>#include <unordered_set>#include <set>#include <algorithm>#include <string>#include <iostream>#include <iomanip>// #include <sstream>// #include <bit>// #include <complex>// #include <exception>// #include <fstream>// #include <functional>// #include <iosfwd>// #include <iterator>// #include <limits>// #include <locale>// #include <memory>// #include <new>// #include <numeric>// #include <stdexcept>// #include <typeinfo>// #include <utility>// #include <valarray>// #include <atomic>// #include <chrono>// #include <condition_variable>// #include <future>// #include <mutex>// #include <random>// #include <ratio>// #include <regex>// #include <scoped_allocator>// #include <system_error>// #include <thread>// #include <tuple>// #include <typeindex>// #include <type_traits>// #include <cctype>// #include <cerrno>// #include <cfloat>// #include <ciso646>// #include <climits>// #include <clocale>// #include <cmath>// #include <csetjmp>// #include <csignal>// #include <cstdarg>// #include <cstddef>// #include <cstdio>// #include <cstdlib>// #include <cstring>#include <ctime>// #include <ccomplex>// #include <cfenv>// #include <cinttypes>// #include <cstdbool>// #include <cstdint>// #include <ctgmath>// #include <cwchar>// #include <cwctype>using namespace std;#include <atcoder/all>using namespace atcoder;#define STRINGIFY(n) #n#define TOSTRING(n) STRINGIFY(n)using ll = long long;using ull = unsigned long long;template<typename T> using maxque = priority_queue<T>;template<typename T> using minque = priority_queue<T,vector<T>,greater<T>>;#define int ll#define endl "\n"#define unless(cond) if(!(cond))#define until(cond) while(!(cond))#define rep(i,s,e) for(ll i = (s); i < (e); ++i)#define repR(i,s,e) for(ll i = (e)-1; (s) <= i; --i)#define repE(i,s,e) for(ll i = (s); i <= (e); ++i)#define repER(i,s,e) for(ll i = (e); (s) <= i; --i)#define repSubsetR(set,super) for(ll _super=super,set = _super; 0 <= set; --set)if(set &= _super, true)#define ALL(xs) begin(xs), end(xs)#define ALLR(xs) rbegin(xs), rend(xs)#define ALLC(xs) cbegin(xs), cend(xs)#define ALLCR(xs) crbegin(xs), crend(xs)template<typename C> void uniq(C &xs){ xs.erase(unique(ALL(xs)), xs.end()); }template<typename C> constexpr ll len(C &&xs){ return size(forward<C>(xs)); }ll BIT(ll n){ return 1LL<<n; }auto clock0 = clock();void debug_h(const char *file, signed line, const char *str_args){ cerr << file << ":" << line << ": " << str_args << " => "; }template<class X, class... Xs> void debug_(const X &x, const Xs&... xs){ cerr << x; (void)initializer_list<int>{ (cerr << ", " << xs,0)... };cerr <<endl; }void debug_(){ cerr << endl; }#define ASSERT(pred,...) (static_cast<bool>(pred) ? void(0) : (debug_h(__FILE__, __LINE__, "ASSERT FAIL! " #pred "; " #__VA_ARGS__),debug_(__VA_ARGS__),exit(1)))template<class X> X &&dbg_(X &&x){ cerr<<x<<endl; return forward<X>(x); }#ifdef DEBUG#define dbg(x) (debug_h(__FILE__, __LINE__, "" #x),dbg_(x))#define debug(...) (debug_h(__FILE__, __LINE__, "" #__VA_ARGS__),debug_(__VA_ARGS__))#define clk(...) (cerr << __VA_ARGS__ " @ " << (clock()-clock0) <<endl,(void)0)#else#define dbg(x) (x)#define debug(...) ((void)0)#define clk(...) ((void)0)//#define ASSERT(pred,...) ((void)0)#endif#define DEF_ORD(op) bool operator op(SELF_ const &b)const { return Ord() op b.Ord(); }#define ORD(...) auto Ord()const{ return tie(__VA_ARGS__); } typedef auto self_fn_() -> decltype(*this); using SELF_ = decltype(((self_fn_*)nullptr)()); DEF_ORD(==) DEF_ORD(!=) DEF_ORD(<) DEF_ORD(>) DEF_ORD(<=) DEF_ORD(>=)template<class C> auto operator<<(ostream &out, const C &xs) -> enable_if_t<!is_same_v<decay_t<C>, char*> && !is_same_v<decay_t<C>, string>, decltype(begin(xs),out)&> { out<<"[ "; for(auto&&x:xs)out<<x<<", "; return out<<"]"; }template<class C> auto operator>>(istream &in, C &xs) -> enable_if_t<!is_same_v<decay_t<C>, char*> && !is_same_v<decay_t<C>, string>, decltype(begin(xs),in)&> { for(auto&x:xs)in>>x; return in; }template<class Tuple, size_t... I> void print_tuple_(ostream &out, Tuple const &xs, std::index_sequence<I...>){ out << "("; (void)initializer_list<int>{ (out << (I==0?"":", ") << std::get<I>(xs),0)... }; out << ")"; }template<class... T> ostream &operator<<(ostream &out, tuple<T...> const &xs){ print_tuple_(out, xs, make_index_sequence<sizeof...(T)>()); return out; }template<class Tuple, size_t... I> void read_tuple_(istream &in, Tuple &xs, std::index_sequence<I...>){ (void)initializer_list<int>{ (in >> std::get<I>(xs),0)... }; }template<class... T> istream &operator>>(istream &in, tuple<T...> &xs){ read_tuple_(in, xs, make_index_sequence<sizeof...(T)>()); return in; }template<class S, class T> ostream &operator<<(ostream &out, pair<S, T> const &p){ return out << "(" << p.first << ", " << p.second << ")"; }template<class S, class T> istream &operator>>(istream &in, pair<S, T> &p){ return in >> p.first >> p.second; }template<typename MINT, typename = internal::is_modint_t<MINT>> ostream &operator<<(ostream &out, MINT x){ return out << x.val(); }template<typename MINT, typename = internal::is_modint_t<MINT>> istream &operator>>(istream &in, MINT &x){ ll a; in>>a; x = a; return in; }template<typename F> struct Fix : F {template<typename G> Fix(G &&g) : F{forward<G>(g)} {}template<typename... Xs> decltype(auto) operator()(Xs&&... xs)const{ return F::operator()(*this, forward<Xs>(xs)...); }};template<typename F> Fix(F&&) -> Fix<decay_t<F>>;template<typename T,typename U> bool chmin(T &a, U b){ if(a <= b)return false; a = b; return true; }template<typename T,typename U> bool chmax(T &a, U b){ if(a >= b)return false; a = b; return true; }//const signed MOD = 998244353;const signed MOD = 1000000007; // 10^9+7using mint = static_modint<MOD>;// using mint = dynamic_modint<-1>; // mint::set_mod(mod);// using mint0 = dynamic_modint<0>; // mint0::set_mod(mod);const ll INF = BIT(60);struct xor128 {uint32_t x = 123456789;uint32_t y = 362436069;uint32_t z = 521288629;uint32_t w = 88675123;uint32_t next(){auto t = x ^ (x << 11);x = y; y = z; z = w;return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));}} rnd;struct Treap {struct Node{Node *ch[2] = {};ll pri;ll k;ll v;ll q;Node(ll k, ll v):pri(rnd.next()),k(k),v(v),q(v){}void update(){q = max({ query_(ch[0]), v, query_(ch[1]) });}Node *rotate(int b){auto tmp = ch[1-b];ch[1-b] = tmp->ch[b];tmp->ch[b] = this;update(); tmp->update();return tmp;}friend Node *set_(Node *x, ll k, ll v){unless(x) return new Node(k, v);if(k==x->k){x->v = v;x->update();}else{ll b = x->k < k;x->ch[b] = set_(x->ch[b], k, v);x->update();if(x->pri > x->ch[b]->pri) x = x->rotate(1-b);}return x;}friend ll query_(Node *x) { return x ? x->q : -1; }friend ll query_(Node *x, ll k){unless(x) return -1;ll ret = query_(x->ch[0]);if(k < x->k) return ret;chmax(ret, x->v);if(k==x->k) return ret;chmax(ret, query_(x->ch[1], k));return ret;}friend Node *clone(Node const *x){unless(x) return nullptr;auto ret = new Node(x->k, x->v);ret->pri = x->pri;ret->q = x->q;rep(i,0,2) ret->ch[i] = clone(x->ch[i]);return ret;}};Node *root = nullptr;void set(ll k, ll v){root = set_(root, k, v);}ll query(ll k){ // sum (-INF, k]return query_(root, k);}Treap &operator=(Treap const &x){ASSERT(root == nullptr);root = clone(x.root);return *this;}};struct Seg2D {struct Node{Treap trp;Node *ch[2] = {};};Node *root = nullptr;ll root_ye=1;void set(ll x, ll y, ll v) {if(root == nullptr){root = new Node();until(y < root_ye) root_ye <<= 1;}else{until(y < root_ye) {root_ye <<= 1;auto old = root;root = new Node();root->trp = old->trp;root->ch[0] = old;}}Fix impl = [&](auto impl, Node *node, ll ys, ll ye){node->trp.set(x, v);if(ys+1 == ye) return;ll ym = (ys+ye)>>1;ll c = ym <= y;if(node->ch[c] == nullptr) node->ch[c] = new Node();if(c == 0){impl(node->ch[c], ys, ym);}else{impl(node->ch[c], ym, ye);}};impl(root, 0, root_ye);}ll query(ll r, ll t, ll b){Fix impl = [&](auto impl, Node *node, ll ys, ll ye)->ll{if(node == nullptr || b <= ys || ye <= t) return -1;if(t <= ys && ye <= b) return node->trp.query(r-1);ll ym = (ys+ye)>>1;return max(impl(node->ch[0], ys, ym),impl(node->ch[1], ym, ye));};return impl(root, 0, root_ye);}void print(ostream &out){Fix impl = [&](auto impl, Node *node, ll ys, ll ye, ll lv){if(node == nullptr) return;rep(foo,0,lv) out << " ";out << "y: ["<<ys<<","<<ye<<")" << endl;//node->trp.print(out, lv+2);ll ym = (ys+ye)>>1;impl(node->ch[0], ys, ym, lv+1);impl(node->ch[1], ym, ye, lv+1);};impl(root, 0, root_ye, 0);}};struct Tri{ll l,r,s2;};Tri readTri(){ll a,b,c,d,e,f;cin>>a>>b>>c>>d>>e>>f;ll l = min({a,c,e});l=-l;ll r = max({a,c,e});c -= a; d -= b;e -= a; f -= b;ll s2 = abs(c*f-d*e);return {l,r,s2};};template<typename T>struct compress{vector<T> xs;size_t size()const{return xs.size()+1;}void add(T const&x){xs.push_back(x);}void prepare(){sort(ALL(xs));xs.erase(unique(ALL(xs)), xs.end());}ll operator[](T const& x){ll i = lower_bound(ALL(xs), x) - begin(xs);return i+1;}};ll solve(){ll n,q;cin>>n>>q;vector<Tri> tris;rep(i,0,n) tris.push_back(readTri());vector<tuple<signed,signed,signed>> queries(q);compress<signed> zl,zr;rep(i,0,q){signed t;cin>>t;if(t == 1){queries[i] = {t,0,0};tris.push_back(readTri());}else{signed l,r;cin>>l>>r;l=-l;queries[i] = {t,l,r};zl.add(l);zr.add(r);}}zl.prepare();zr.prepare();Seg2D trp;rep(i,0,n){auto tri = tris[i];trp.set(zl[tri.l], zr[tri.r], tri.s2);}ll i = n;for(auto [t,l,r]:queries){if(t==1){auto tri = tris[i++];trp.set(zl[tri.l], zr[tri.r], tri.s2);continue;}cout << trp.query(zl[l]+1, 0, zr[r]+1) << endl;}exit(0);}signed main(){cin.tie(nullptr);ios_base::sync_with_stdio(false);cout << fixed << setprecision(15);try{cout << solve() << endl;/*cout << (solve()?"Yes":"No") << endl; // */return 0;}catch(exception& e){cerr << e.what() << endl;}catch(char *s){cerr << s << endl;}return 1;}