#682785 (C++14) No.1625 三角形の質問

提出ソース

結果

問題	No.1625 三角形の質問
ユーザー	kiyoshi0205
提出日時	2021-07-23 22:30:39
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2,598 ms / 6,000 ms
コード長	7,492 bytes
コンパイル時間	7,252 ms
コンパイル使用メモリ	292,796 KB
実行使用メモリ	311,260 KB
最終ジャッジ日時	2024-07-18 18:24:25
合計ジャッジ時間	42,355 ms
ジャッジサーバーID （参考情報）	judge2 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	207 ms 35,236 KB
testcase_02	AC	935 ms 149,096 KB
testcase_03	AC	977 ms 144,120 KB
testcase_04	AC	732 ms 135,736 KB
testcase_05	AC	1,421 ms 169,828 KB
testcase_06	AC	2,387 ms 311,160 KB
testcase_07	AC	2,598 ms 311,108 KB
testcase_08	AC	2,410 ms 311,260 KB
testcase_09	AC	2,376 ms 311,144 KB
testcase_10	AC	2,339 ms 311,004 KB
testcase_11	AC	2,309 ms 311,088 KB
testcase_12	AC	2,300 ms 311,204 KB
testcase_13	AC	2,341 ms 311,008 KB
testcase_14	AC	2,317 ms 311,060 KB
testcase_15	AC	2,453 ms 311,112 KB
testcase_16	AC	513 ms 183,332 KB
testcase_17	AC	607 ms 187,480 KB
testcase_18	AC	1,106 ms 162,492 KB
testcase_19	AC	731 ms 209,024 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// #include<ext/pb_ds/tag_and_trait.hpp>
// using namespace __gnu_pbds;
// #include<boost/multiprecision/cpp_int.hpp>
// namespace multiprecisioninteger = boost::multiprecision;
// using cint=multiprecisioninteger::cpp_int;
using namespace std;
using ll=long long;
using datas=pair<ll,ll>;
using ddatas=pair<long double,long double>;
using tdata=pair<ll,datas>;
using vec=vector<ll>;
using mat=vector<vec>;
using pvec=vector<datas>;
using pmat=vector<pvec>;
// using llset=tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>;
#define For(i,a,b) for(i=a;i<(ll)b;++i)
#define bFor(i,b,a) for(i=b,--i;i>=(ll)a;--i)
#define rep(i,N) For(i,0,N)
#define rep1(i,N) For(i,1,N)
#define brep(i,N) bFor(i,N,0)
#define brep1(i,N) bFor(i,N,1)
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define vsort(v) sort(all(v))
#define vrsort(v) sort(allr(v))
#define uniq(v) vsort(v);(v).erase(unique(all(v)),(v).end())
#define endl "\n"
#define popcount __builtin_popcountll
#define eb emplace_back
#define print(x) cout<<x<<endl
#define printyes print("Yes")
#define printno print("No")
#define printYES print("YES")
#define printNO print("NO")
#define output(v) do{bool f=0;for(auto outi:v){cout<<(f?" ":"")<<outi;f=1;}cout<<endl;}while(0)
#define matoutput(v) do{for(auto outimat:v)output(outimat);}while(0)
constexpr ll mod=1000000007;
// constexpr ll mod=998244353;
constexpr ll inf=1LL<<60;
constexpr long double eps=1e-9;
const long double PI=acosl(-1);
template<class T,class E> ostream& operator<<(ostream& os,const pair<T,E>& p){return os<<"("<<p.first<<","<<p.second<<")";}
template<class T> ostream& operator<<(ostream& os,const vector<T>& v){
  os<<"{";bool f=false;
  for(auto& x:v){if(f)os<<",";os<<x;f=true;}
  os<<"}";
  return os;
}
template<class T> ostream& operator<<(ostream& os,const set<T>& v){
  os<<"{";bool f=false;
  for(auto& x:v){if(f)os<<",";os<<x;f=true;}
  os<<"}";
  return os;
}
template<class T> ostream& operator<<(ostream& os,const multiset<T>& v){
  os<<"{";bool f=false;
  for(auto& x:v){if(f)os<<",";os<<x;f=true;}
  os<<"}";
  return os;
}
template<class T,class E> ostream& operator<<(ostream& os,const map<T,E>& v){
  os<<"{";bool f=false;
  for(auto& x:v){if(f)os<<",";os<<x;f=true;}
  os<<"}";
  return os;
}
template<class T> inline bool chmax(T& a,const T b){bool x=a<b;if(x)a=b;return x;}
template<class T> inline bool chmin(T& a,const T b){bool x=a>b;if(x)a=b;return x;}
#ifdef DEBUG
void debugg(){cout<<endl;}
template<class T,class... Args>void debugg(const T& x,const Args&... args){cout<<" "<<x;debugg(args...);}
#define debug(...) cout<<__LINE__<<" ["<<#__VA_ARGS__<<"]:",debugg(__VA_ARGS__)
#else
#define debug(...) (void(0))
#endif

inline void startupcpp(void) noexcept{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(15);
}

template< typename structure_t, typename get_t, typename update_t >
struct SegmentTree2DCompressed {

  using merge_f = function< get_t(get_t, get_t) >;
  using range_get_f = function< get_t(structure_t &, int, int) >;
  using update_f = function< void(structure_t &, int, update_t) >;

  int sz;
  vector< structure_t > seg;
  const merge_f f;
  const range_get_f g;
  const update_f h;
  const get_t identity;
  vector< vector< int > > LL, RR;
  vector< vector< int > > beet;

  SegmentTree2DCompressed(int n, const merge_f &f, const range_get_f &g, const update_f &h, const get_t &identity)
      : f(f), g(g), h(h), identity(identity) {
    sz = 1;
    while(sz < n) sz <<= 1;
    beet.resize(2 * sz);
    LL.resize(2 * sz);
    RR.resize(2 * sz);
  }

  void update(int a, int x, update_t z, int k, int l, int r) {
    if(r <= a || a + 1 <= l) return;
    if(a <= l && r <= a + 1) return h(seg[k], x, z);
    update(a, LL[k][x], z, 2 * k + 0, l, (l + r) >> 1);
    update(a, RR[k][x], z, 2 * k + 1, (l + r) >> 1, r);
    return h(seg[k], x, z);
  }

  void update(int x, int y, update_t z) {
    y = lower_bound(begin(beet[1]), end(beet[1]), y) - begin(beet[1]);
    return update(x, y, z, 1, 0, sz);
  }

  get_t query(int a, int b, int x, int y, int k, int l, int r) {
    if(a >= r || b <= l) return identity;
    if(a <= l && r <= b) return g(seg[k], x, y);
    return f(query(a, b, LL[k][x], LL[k][y], 2 * k + 0, l, (l + r) >> 1),
             query(a, b, RR[k][x], RR[k][y], 2 * k + 1, (l + r) >> 1, r));
  }

  get_t query(int a, int b, int x, int y) {
    x = lower_bound(begin(beet[1]), end(beet[1]), x) - begin(beet[1]);
    y = lower_bound(begin(beet[1]), end(beet[1]), y) - begin(beet[1]);
    return query(a, b, x, y, 1, 0, sz);
  }

  void build() {
    for(int k = (int) beet.size() - 1; k >= sz; k--) {
      sort(begin(beet[k]), end(beet[k]));
      beet[k].erase(unique(begin(beet[k]), end(beet[k])), end(beet[k]));
    }
    for(int k = sz - 1; k > 0; k--) {
      beet[k].resize(beet[2 * k + 0].size() + beet[2 * k + 1].size());
      merge(begin(beet[2 * k + 0]), end(beet[2 * k + 0]), begin(beet[2 * k + 1]), end(beet[2 * k + 1]), begin(beet[k]));
      beet[k].erase(unique(begin(beet[k]), end(beet[k])), end(beet[k]));
      LL[k].resize(beet[k].size() + 1);
      RR[k].resize(beet[k].size() + 1);
      int tail1 = 0, tail2 = 0;
      for(int i = 0; i < beet[k].size(); i++) {
        while(tail1 < beet[2 * k + 0].size() && beet[2 * k + 0][tail1] < beet[k][i]) ++tail1;
        while(tail2 < beet[2 * k + 1].size() && beet[2 * k + 1][tail2] < beet[k][i]) ++tail2;
        LL[k][i] = tail1, RR[k][i] = tail2;
      }
      LL[k][beet[k].size()] = (int) beet[2 * k + 0].size();
      RR[k][beet[k].size()] = (int) beet[2 * k + 1].size();
    }
    for(int k = 0; k < beet.size(); k++) {
      seg.emplace_back(structure_t(beet[k].size()));
    }
  }

  void preupdate(int x, int y) {
    beet[x + sz].push_back(y);
  }
};

ll calcS(ll a,ll b,ll c,ll d,ll e,ll f){
  c-=a;d-=b;
  e-=a;f-=b;
  return abs(c*f-d*e);
}

ll max(ll a,ll b){return std::max(a,b);}
ll maxe(){return -1;}
#include<atcoder/all>
using segtree=atcoder::segtree<ll,max,maxe>;
using dtree=SegmentTree2DCompressed<segtree,ll,ll>;
int main(){
  startupcpp();
  ll i,N,Q;
  cin>>N>>Q;
  vec t(Q),l(Q),r(Q),s(Q),fl(N),fr(N),fs(N);
  rep(i,N){
    int a,b,c,d,e,f;
    cin>>a>>b>>c>>d>>e>>f;
    fl[i]=min({a,c,e});
    fr[i]=max({a,c,e});
    fs[i]=calcS(a,b,c,d,e,f);
  }
  rep(i,Q){
    cin>>t[i];
    if(t[i]==1){
      int a,b,c,d,e,f;
      cin>>a>>b>>c>>d>>e>>f;
      l[i]=min({a,c,e});
      r[i]=max({a,c,e});
      s[i]=calcS(a,b,c,d,e,f);
    }else cin>>l[i]>>r[i];
  }
  vec za;
  for(auto& x:l)za.emplace_back(x);
  for(auto& x:r)za.emplace_back(x);
  for(auto& x:fl)za.emplace_back(x);
  for(auto& x:fr)za.emplace_back(x);
  uniq(za);
  dtree tree(za.size(),[](ll a,ll b){return max(a,b);},[](segtree& x,int a,int b){return x.prod(a,b);},[](segtree& x,int a,ll b){x.set(a,b);},-1);
  for(auto& x:l)x=lower_bound(all(za),x)-za.begin();
  for(auto& x:r)x=lower_bound(all(za),x)-za.begin();
  for(auto& x:fl)x=lower_bound(all(za),x)-za.begin();
  for(auto& x:fr)x=lower_bound(all(za),x)-za.begin();
  rep(i,N)tree.preupdate(fl[i],fr[i]);
  rep(i,Q)tree.preupdate(l[i],r[i]);
  tree.build();
  rep(i,N)tree.update(fl[i],fr[i],fs[i]);
  rep(i,Q){
    if(t[i]==1)tree.update(l[i],r[i],s[i]);
    else print(tree.query(l[i],r[i]+1,l[i],r[i]+1));
  }
}

yukicoder

結果

テストケース

ソースコード