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

提出ソース

結果

問題	No.1625 三角形の質問
ユーザー	naoya_t
提出日時	2021-07-29 11:56:27
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	MLE
実行時間	-
コード長	14,688 bytes
コンパイル時間	3,501 ms
コンパイル使用メモリ	233,764 KB
実行使用メモリ	666,112 KB
最終ジャッジ日時	2024-09-14 08:59:15
合計ジャッジ時間	62,170 ms
ジャッジサーバーID （参考情報）	judge3 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	177 ms 48,212 KB
testcase_02	AC	1,449 ms 203,592 KB
testcase_03	AC	1,077 ms 210,948 KB
testcase_04	AC	972 ms 185,968 KB
testcase_05	AC	2,094 ms 368,012 KB
testcase_06	MLE	-
testcase_07	MLE	-
testcase_08	MLE	-
testcase_09	MLE	-
testcase_10	MLE	-
testcase_11	MLE	-
testcase_12	MLE	-
testcase_13	MLE	-
testcase_14	MLE	-
testcase_15	MLE	-
testcase_16	AC	606 ms 180,604 KB
testcase_17	AC	1,301 ms 244,332 KB
testcase_18	AC	1,109 ms 164,744 KB
testcase_19	AC	1,481 ms 273,196 KB

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

コンパイルメッセージ

main.cpp: In constructor 'SegmentTreeFractionalCascading<T>::SegmentTreeFractionalCascading(std::vector<std::map<int, int> >&)':
main.cpp:196:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  196 |             for (auto [y, a] : data[k]) {
      |                       ^
main.cpp: In function 'void solve(int, int, vvi&, vvi&)':
main.cpp:360:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  360 |             auto [xmin, xmax, _q_area] = triangles_in_queries[i];
      |                  ^
main.cpp:372:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  372 |             auto [xmin, xmax, q_area] = triangles_in_queries[i];
      |                  ^

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;

#define NDEBUG
#include <cassert>


typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<double> vd;

#define pb  push_back
#define eb  emplace_back
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define repC3(vari,varj,vark,n)  for(int vari=0;vari<(n)-2;++vari)for(int varj=vari+1;varj<(n)-1;++varj)for(int vark=varj+1;vark<(n);++vark)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define whole(f, x, ...)                                     \
    ([&](decltype((x)) whole) {                              \
        return (f)(begin(whole), end(whole), ##__VA_ARGS__); \
    })(x)
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define IN_(x,a,b) ((a)<=(x)&&(x)<(b))
#define tors(a) sort(ALL(a), greater<decltype(a[0])>())
#define nC2(n) ((ll)(n)*((n)-1)/2)

#define clamp(v,lo,hi) min(max(v,lo),hi)
#define ABS(x) max((x),-(x))
#define PQ(T) priority_queue<T,vector<T>,greater<T>>
#define CLEAR(a) a = decltype(a)()
template <typename T>
vector<T> vec(size_t len, T elem) { return vector<T>(len, elem); }

template<typename T1, typename T2> inline void amin(T1 & a, T2 const & b) { if (a>b) a=b; }
template<typename T1, typename T2> inline void amax(T1 & a, T2 const & b) { if (a<b) a=b; }

template <typename T>
void erase_one(multiset<T>& ms, T val) {
    auto iter = ms.find(val);
    if (iter != ms.end()) ms.erase(iter);
}

inline ll square(ll x) { return x * x; }
inline ll gcd(ll a, ll b) { while(a) swap(a, b%=a); return b; }
inline ll lcm(ll a, ll b) { return a/gcd(a,b)*b; }
template <typename T>
inline T mod(T a, T b) { return ((a % b) + b) % b; }


#define is_digit(c) ('0'<=(c)&&(c)<='9')
#define is_whitespace(c) ((c)==' '||(c)=='\n'||(c)=='\r'||(c)=='\t'||(c)==EOF)
void reader(int& x){
  x=0;
  bool neg=false; for(;;){ int k=getchar(); if(k=='-'){ neg=true; break; } if (is_digit(k)){ x=k-'0'; break;} }
  for(;;){ int k=getchar(); if (!is_digit(k)) break; x=x*10+k-'0'; }
  if(neg) x=-x; }
void reader(long long& x){
  x=0;
  bool neg=false; for(;;){ int k=getchar(); if(k=='-'){ neg=true; break; } if (is_digit(k)){ x=k-'0'; break; } }
  for(;;){ int k=getchar(); if (!is_digit(k)) break; x=x*10+k-'0'; }
  if(neg) x=-x; }
void reader(unsigned long long& x){
  x=0;
  for(;;){ int k=getchar(); if (is_digit(k)){ x=(unsigned long long)(k-'0'); break; } }
  for(;;){ int k=getchar(); if (!is_digit(k)) break; x=x*10+k-'0'; } }
int reader(char s[]){
  int c,i=0;
  for(;;){ c=getchar(); if (!is_whitespace(c)) break; } s[i++]=c;
  for(;;){ c=getchar(); if (is_whitespace(c)) break; s[i++]=c; }
  s[i]='\0'; return i; }
int reader(string& s){
  int c;
  for(;;){ c=getchar(); if (!is_whitespace(c)) break; } s.push_back(c);
  for(;;){ c=getchar(); if (is_whitespace(c)) break; s.push_back(c); }
  return s.size(); }
void reader(char& c){
  for(;;){ c=getchar(); if (!is_whitespace(c)) break; } }

void writer(int x, char c=0){
  int s=0; bool neg=false; char f[10]; if(x<0) neg=true,x=-x; if(x==0) f[s++]='0'; else while(x) f[s++]='0'+x%10,x/=10;
  if(neg) putchar('-'); while(s--) putchar(f[s]); if(c) putchar(c); }
void writer(long long x, char c=0){
  int s=0; bool neg=false; char f[20]; if(x<0) neg=true,x=-x; if(x==0) f[s++]='0'; else while(x) f[s++]='0'+x%10,x/=10;
  if(neg) putchar('-'); while(s--) putchar(f[s]); if(c) putchar(c); }
void writer(unsigned long long x, char c=0){
  int s=0; char f[20]; if(x==0) f[s++]='0'; else while(x) f[s++]='0'+x%10,x/=10;
  while(s--) putchar(f[s]); if(c) putchar(c); }
void writer(const string& x, char c=0){
  for(int i=0;i<x.size();++i) putchar(x[i]); if(c) putchar(c); }
void writer(const char x[], char c=0){
  for(int i=0;x[i]!='\0';++i) putchar(x[i]); if(c) putchar(c); }

template <class T,class S> void reader(T& x, S& y){ reader(x); reader(y); }
template <class T,class S,class U> void reader(T& x, S& y, U& z){ reader(x); reader(y); reader(z); }
template <class T,class S,class U,class V> void reader(T& x, S& y, U& z, V& w){ reader(x); reader(y); reader(z); reader(w); }
template <class T> vector<T> readerArray(int n){
  vector<T> ret(n); for(int i=0;i<n;++i) reader(ret[i]); return ret; }
template <class T> vector<vector<T>> readerMatrix(int n,int m=0){
  if (m==0) m = n; vector<vector<T>> ret(n); for(int i=0;i<n;++i) ret[i] = readerArray<T>(m); return ret; }

template <class T> void writerLn(T x){ writer(x,'\n'); }
template <class T,class S> void writerLn(T x, S y){ writer(x,' '); writer(y,'\n'); }
template <class T,class S,class U> void writerLn(T x, S y, U z){ writer(x,' '); writer(y,' '); writer(z,'\n'); }
template <class T,class S,class U,class V> void writerLn(T x, S y, U z, V v){ writer(x,' '); writer(y,' '); writer(z,' '); writer(v,'\n'); }
template <class T> void writerArrayLn(T x[], int n){
  if(n==0){ putchar('\n'); return; }
  for(int i=0;i<n-1;++i) writer(x[i],' '); writer(x[n-1],'\n'); }
template <class T> void writerArrayLn(vector<T>& x){ writerArrayLn(x.data(),(int)x.size()); }
template <class T> void writerArrayLnV(T x[], int n){ for(int i=0;i<n;++i) writerLn(x[i]); }
template <class T> void writerArrayLnV(vector<T>& x){ for(T xi: x) writerLn(xi); }
template <class T> void writerMatrix(vector<vector<T>>& x){
  int n = x.size(); if (n == 0) return;
  int m = x[0].size(); for (int i=0; i<n; ++i) writerArrayLn(x[i]); }

void readerEdges(size_t M,vector<int>& a,vector<int>& b,bool decrement=true){
  a.resize(M); b.resize(M);
  for(int i=0;i<M;++i){ reader(a[i]); reader(b[i]); if(decrement){ --a[i]; --b[i]; } } }
template <class W> void readerEdges(size_t M,vector<int>& a,vector<int>& b,vector<W>& c,bool decrement=true){
  a.resize(M); b.resize(M); c.resize(M);
  for(int i=0;i<M;++i){ reader(a[i]); reader(b[i]); reader(c[i]); if(decrement){ --a[i]; --b[i]; } } }
template <class S,class T> void readerEdges(size_t M,vector<int>& a,vector<int>& b,vector<S>& c,vector<T>& d,bool decrement=true){
  a.resize(M); b.resize(M); c.resize(M); d.resize(M);
  for(int i=0;i<M;++i){ reader(a[i]); reader(b[i]); reader(c[i]); reader(d[i]); if(decrement){ --a[i]; --b[i]; } } }

vector<vector<int>> make_nxt(int N, int M, vector<int>& a, vector<int>& b){
  vector<vector<int>> nxt(N);
  for(int i=0;i<M;++i){ nxt[a[i]].push_back(b[i]); nxt[b[i]].push_back(a[i]); }
  return nxt; }
template <class T> vector<vector<pair<int,T>>> make_nxt(int N, int M, vector<int>& a, vector<int>& b, vector<T>& c){
  vector<vector<pair<int,T>>> nxt(N);
  for(int i=0;i<M;++i){ nxt[a[i]].emplace_back(b[i],c[i]); nxt[b[i]].emplace_back(a[i],c[i]); }
  return nxt; }


#include <atcoder/segtree>



template <typename T>
T max_(T a, T b) { return max(a, b); }


template <typename T>
struct maxsegtree : atcoder::segtree<T, max_<T>, numeric_limits<T>::min> {
    atcoder::segtree<T, max_<T>, numeric_limits<T>::min> *seg;

    maxsegtree() { seg = nullptr; }
    ~maxsegtree() { if (seg) delete seg; }

    void init(vector<T>& ar){
        seg = new atcoder::segtree<T, max_<T>, numeric_limits<T>::min>(ar);
    }
    void set(int p, T x) { seg->set(p, x); }
    T prod(int lo, int hi) { return seg->prod(lo, hi); }
};

template <typename T>
struct SegmentTreeFractionalCascading {
    vvii seg;
    vector<maxsegtree<T>> rmqs;
    vvi LL, RR;
    int sz;

    SegmentTreeFractionalCascading(vector<map<int, int>>& data) {
        int zxid = data.size(), N = zxid;

        sz = 1;
        while (sz < N) sz <<= 1;
        seg.resize(2 * sz - 1);
        LL.resize(2 * sz - 1);
        RR.resize(2 * sz - 1);
        rmqs.resize(2 * sz - 1);

        rep(k, N) {
            int ofs_k = (sz - 1) + k;

            seg[ofs_k].reserve(data[k].size());
            for (auto [y, a] : data[k]) {
                seg[ofs_k].eb(y, a);
            }


            vector<T> vals(seg[ofs_k].size());
            rep(i, seg[ofs_k].size()) vals[i] = seg[ofs_k][i].second;
            rmqs[ofs_k].init(vals);
            vector<T>().swap(vals);
        }


        for (int k = sz - 2; k >= 0; --k) {
            seg[k].resize(seg[2 * k + 1].size() + seg[2 * k + 2].size());
            LL[k].resize(seg[k].size() + 1);
            RR[k].resize(seg[k].size() + 1);
            std::merge(ALL(seg[2 * k + 1]), ALL(seg[2 * k + 2]), begin(seg[k]));


            vector<T> vals(seg[k].size());
            rep(i, seg[k].size()) {
                vals[i] = seg[k][i].second;
            }
            rmqs[k].init(vals);
            vector<T>().swap(vals);

            int tail1 = 0, tail2 = 0;
            rep(i, seg[k].size()) {
                while (tail1 < seg[2 * k + 1].size() && seg[2 * k + 1][tail1] < seg[k][i]) ++tail1;
                while (tail2 < seg[2 * k + 2].size() && seg[2 * k + 2][tail2] < seg[k][i]) ++tail2;
                LL[k][i] = tail1, RR[k][i] = tail2;
            }
            LL[k][seg[k].size()] = (int)seg[2 * k + 1].size();
            RR[k][seg[k].size()] = (int)seg[2 * k + 2].size();
        }
    }

    void update(int x, int y, int ylo_ix, int yhi_ix, int k, int xlo_ix, int xhi_ix, T newval) {
        if (ylo_ix >= yhi_ix) return;

        if (k >= seg.size()) return;
        if (!IN_(x, xlo_ix, xhi_ix)) return;

        if (ylo_ix + 1 == yhi_ix) {
            rmqs[k].set(ylo_ix, newval);
        }
        int xmi_ix = (xlo_ix + xhi_ix) >> 1;
        if (IN_(ylo_ix, 0, LL[k].size()) && IN_(yhi_ix, 0, LL[k].size())) {
            update(x, y, LL[k][ylo_ix], LL[k][yhi_ix], 2 * k + 1, xlo_ix, xmi_ix, newval);
        }
        if (IN_(ylo_ix, 0, RR[k].size()) && IN_(yhi_ix, 0, RR[k].size())) {
            update(x, y, RR[k][ylo_ix], RR[k][yhi_ix], 2 * k + 2, xmi_ix, xhi_ix, newval);
        }
    }
    void update(int x, int y, T newval) {
        int ylo_ix = lower_bound(ALL(seg[0]), ii(y, -1)) - begin(seg[0]);
        int yhi_ix = lower_bound(ALL(seg[0]), ii(y + 1, -1)) - begin(seg[0]);
        update(x, y, ylo_ix, yhi_ix, 0, 0, sz, newval);
    }

    inline T merge(T x, T y) { return max(x, y); }

    inline T query(int xlo, int xhi, int ylo_ix, int yhi_ix, int k, int xlo_ix, int xhi_ix) {
        if (ylo_ix > yhi_ix || xhi_ix <= xlo || xhi <= xlo_ix) {
            return numeric_limits<T>::min();
        } else if (xlo <= xlo_ix && xhi_ix <= xhi) {
            return rmqs[k].prod(ylo_ix, yhi_ix);
        } else {
            int xmi_ix = (xlo_ix + xhi_ix) >> 1;
            return merge(query(xlo, xhi, LL[k][ylo_ix], LL[k][yhi_ix], 2 * k + 1, xlo_ix, xmi_ix), query(xlo, xhi, RR[k][ylo_ix], RR[k][yhi_ix], 2 * k + 2, xmi_ix, xhi_ix));
        }
    }

    T query(int xlo, int xhi, int ylo, int yhi) {
        int ylo_ix = lower_bound(ALL(seg[0]), ii(ylo, -1)) - begin(seg[0]);
        int yhi_ix = lower_bound(ALL(seg[0]), ii(yhi, -1)) - begin(seg[0]);
        return query(xlo, xhi, ylo_ix, yhi_ix, 0, 0, sz);
    }
};

inline ll calc_area(vi& triangle) {
    ll x1 = triangle[2] - triangle[0];
    ll y1 = triangle[3] - triangle[1];
    ll x2 = triangle[4] - triangle[0];
    ll y2 = triangle[5] - triangle[1];
    return ABS(x1 * y2 - x2 * y1);
}

void solve(int N, int Q, vvi& triangles, vvi& queries) {
    set<int> xs;
    set<ll> ys;
    vll area(N, 0);
    using P = tuple<int, int, ll>;
    map<int, P> triangles_in_queries;
    rep(i, N) {
        for (int j = 0; j < 6; j += 2) {
            xs.insert(triangles[i][j]);
        }
        area[i] = calc_area(triangles[i]);
        ys.insert(area[i]);
    }
    rep(i, Q) {
        int L = queries[i].size();
        if (L == 6) {
            int xmin = INT_MAX, xmax = INT_MIN;
            for (int j = 0; j < 6; j += 2) {
                int x = queries[i][j];
                xs.insert(x);
                amin(xmin, x);
                amax(xmax, x);
            }
            ll q_area = calc_area(queries[i]);
            triangles_in_queries[i] = P(xmin, xmax, q_area);
            ys.insert(q_area);

            vi().swap(queries[i]);
        } else {
            xs.insert(queries[i][0]);
            xs.insert(queries[i][1]);
        }
    }
    xs.insert(INT_MIN);
    xs.insert(INT_MAX);
    ys.insert(LLONG_MIN);
    ys.insert(LLONG_MAX);

    map<int, int> zx;
    int zxid = 0;
    for (int x : xs) {
        zx[x] = zxid++;
    }
    set<int>().swap(xs);

    map<ll, int> zy;
    int zyid = 0;
    vll zyR; zyR.reserve(ys.size());
    for (ll y : ys) {
        zy[y] = zyid++;
        zyR.pb(y);
    }
    set<ll>().swap(ys);


    vector<map<int, int>> tmp(zxid);

    rep(i, N) {
        int xmin = INT_MAX, xmax = INT_MIN;
        for (int j = 0; j < 6; j += 2) {
            int x = zx[triangles[i][j]];
            amin(xmin, x);
            amax(xmax, x);
        }
        amax(tmp[xmin][xmax], zy[area[i]]);
    }
    vvi().swap(triangles);
    vector<ll>().swap(area);

    auto prepare_point = [&](int xmin, int xmax) -> void {
        if (!found(tmp[xmin], xmax)) tmp[xmin][xmax] = zy[LLONG_MIN];
    };

    rep(i, Q) {
        int L = queries[i].size();
        if (L == 0) {
            auto [xmin, xmax, _q_area] = triangles_in_queries[i];
            prepare_point(zx[xmin], zx[xmax]);
        }
    }

    SegmentTreeFractionalCascading<int> seg(tmp);
    vector<map<int, int>>().swap(tmp);

    rep(i, Q) {
        int L = queries[i].size();
        int xmin = INT_MAX, xmax = INT_MIN;
        if (L == 0) {
            auto [xmin, xmax, q_area] = triangles_in_queries[i];
            seg.update(zx[xmin], zx[xmax], zy[q_area]);
        } else {
            int l = zx[queries[i][0]], r = zx[queries[i][1]];
            int res = seg.query(l, r, l, r+1);
            ll resR = (res >= 0) ? zyR[res] : LLONG_MIN;
            if (resR < 0) resR = -1;
            printf("%lld\n", resR);
        }
    }
}

int main() {
    int N, Q;
    reader(N, Q);
    vvi triangles(N, vi(6));
    rep(i, N) { triangles[i] = readerArray<int>(6); }
    vvi queries(Q);
    rep(i, Q) {
        int op;
        reader(op);
        if (op == 1) {
            queries[i] = readerArray<int>(6);
        } else {
            queries[i] = readerArray<int>(2);
        }
    }
    solve(N, Q, triangles, queries);
    return 0;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード