結果
| 問題 | No.1625 三角形の質問 |
| ユーザー |
 naoya_t
|
| 提出日時 | 2021-07-29 13:23:20 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 4,127 ms / 6,000 ms |
| コード長 | 16,998 bytes |
| コンパイル時間 | 4,079 ms |
| コンパイル使用メモリ | 268,408 KB |
| 実行使用メモリ | 483,316 KB |
| 最終ジャッジ日時 | 2024-09-14 10:33:16 |
| 合計ジャッジ時間 | 55,033 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 136 ms
35,356 KB |
| testcase_02 | AC | 1,324 ms
142,812 KB |
| testcase_03 | AC | 975 ms
148,228 KB |
| testcase_04 | AC | 856 ms
133,232 KB |
| testcase_05 | AC | 1,916 ms
263,264 KB |
| testcase_06 | AC | 3,727 ms
483,124 KB |
| testcase_07 | AC | 4,127 ms
483,128 KB |
| testcase_08 | AC | 3,705 ms
482,864 KB |
| testcase_09 | AC | 3,643 ms
483,144 KB |
| testcase_10 | AC | 3,748 ms
483,316 KB |
| testcase_11 | AC | 3,841 ms
483,152 KB |
| testcase_12 | AC | 3,627 ms
483,216 KB |
| testcase_13 | AC | 3,725 ms
483,132 KB |
| testcase_14 | AC | 3,805 ms
482,996 KB |
| testcase_15 | AC | 4,017 ms
483,136 KB |
| testcase_16 | AC | 393 ms
130,512 KB |
| testcase_17 | AC | 949 ms
173,416 KB |
| testcase_18 | AC | 888 ms
119,864 KB |
| testcase_19 | AC | 1,267 ms
191,832 KB |
ソースコード
#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) remove_reference_t<decltype(a)>().swap(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; }
template <typename T>
struct SegmentTree {
int N;
vector<T> buf_;
using MERGER = function<T(T, T)>;
MERGER merge;
T ident;
int ceil2(int size) {
int n = 1;
while (n < size) n *= 2;
return n;
}
SegmentTree(MERGER merge, T ident) : merge(merge), ident(ident) { }
SegmentTree(int size, MERGER merge, T ident) : merge(merge), ident(ident) {
N = ceil2(size);
buf_.assign(N-1 + size, ident);
}
SegmentTree(vector<T> ar, MERGER merge, T ident) : merge(merge), ident(ident) {
init(ar);
}
void init(vector<T>& ar) {
int size = ar.size();
N = ceil2(size);
buf_.assign(N-1 + size, ident);
for (int i=0; i<size; ++i) buf_[i + (N-1)] = ar[i];
for (int i=N-2; i>=0; --i) {
int left = i * 2 + 1, right = i * 2 + 2;
buf_[i] = merge(
left < buf_.size() ? buf_[left] : ident,
right < buf_.size() ? buf_[right] : ident
);
}
}
void init_cdr(vector<pair<int, T>>& ar) {
int size = ar.size();
N = ceil2(size);
buf_.assign(N-1 + size, ident);
for (int i = 0; i < size; ++i) buf_[i + (N-1)] = ar[i].second;
for (int i=N-2; i>=0; --i) {
int left = i * 2 + 1, right = i * 2 + 2;
buf_[i] = merge(
left < buf_.size() ? buf_[left] : ident,
right < buf_.size() ? buf_[right] : ident
);
}
}
void update(int i, T x) {
i = N + i - 1;
buf_[i] = merge(buf_[i], x);
while (i > 0) {
i = (i - 1) / 2;
int left = i * 2 + 1, right = i * 2 + 2;
buf_[i] = merge(
left < buf_.size() ? buf_[left] : ident,
right < buf_.size() ? buf_[right] : ident
);
}
}
T query(int lo, int hi) {
return query(lo, hi, 0, 0, N);
}
T query(int a, int b, int k, int l, int r) {
if (r <= a || b <= l) return ident;
if (a <= l && r <= b) {
return buf_[k];
} else {
T lv = query(a, b, 2 * k + 1, l, (l + r) / 2);
T rb = query(a, b, 2 * k + 2, (l + r) / 2, r);
return merge(lv, rb);
}
}
void dump() {
}
};
template <typename T>
struct MaxSegmentTree : SegmentTree<T> {
MaxSegmentTree() : SegmentTree<T>([](T a, T b) { return max(a, b); }, numeric_limits<T>::min()) {}
MaxSegmentTree(int size) : SegmentTree<T>(size, [](T a, T b) { return max(a, b); }, numeric_limits<T>::min()) {}
MaxSegmentTree(vector<T> ar) : SegmentTree<T>(ar, [](T a, T b) { return max(a, b); }, numeric_limits<T>::min()) {}
};
template <typename T>
void sort_uniq_max(vector<pair<int,T>>& ar) {
if (ar.empty()) return;
sort(ALL(ar));
int L = ar.size(), i = 0;
for (int j=1; j<ar.size(); ++j){
if (ar[i].first == ar[j].first) {
amax(ar[i].second, ar[j].second);
} else {
++i;
if (i < j) ar[i] = ar[j];
}
}
ar.resize(i+1);
}
template <typename T>
struct SegmentTreeFractionalCascading {
vector<vector<pair<int, T>>> seg;
vector<MaxSegmentTree<T>> rmqs;
vvi LL, RR;
int sz;
SegmentTreeFractionalCascading(vector<vector<pair<int, T>>>& 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 = k + (sz - 1);
sort_uniq_max(data[k]);
seg[ofs_k].reserve(data[k].size());
seg[ofs_k].insert(seg[ofs_k].end(), ALL(data[k]));
rmqs[ofs_k].init_cdr(seg[ofs_k]);
CLEAR(data[k]);
}
for (int k = sz - 2; k >= 0; --k) {
int left = 2 * k + 1, right = 2 * k + 2;
seg[k].resize(seg[left].size() + seg[right].size());
LL[k].resize(seg[k].size() + 1);
RR[k].resize(seg[k].size() + 1);
std::merge(ALL(seg[left]), ALL(seg[right]), begin(seg[k]));
rmqs[k].init_cdr(seg[k]);
int tail1 = 0, tail2 = 0;
rep(i, seg[k].size()) {
while (tail1 < seg[left].size() && seg[left][tail1] < seg[k][i]) ++tail1;
while (tail2 < seg[right].size() && seg[right][tail2] < seg[k][i]) ++tail2;
LL[k][i] = tail1, RR[k][i] = tail2;
}
LL[k][seg[k].size()] = (int)seg[left].size();
RR[k][seg[k].size()] = (int)seg[right].size();
CLEAR(seg[left]);
CLEAR(seg[right]);
}
}
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].update(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]), pair<int,T>(y, -1)) - begin(seg[0]);
int yhi_ix = lower_bound(ALL(seg[0]), pair<int,T>(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].query(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]), pair<int,T>(ylo, -1)) - begin(seg[0]);
int yhi_ix = lower_bound(ALL(seg[0]), pair<int,T>(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>;
vector<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.eb(xmin, xmax, q_area);
ys.insert(q_area);
CLEAR(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++;
CLEAR(xs);
map<ll, int> zy;
int zyid = 0;
vll zyR; zyR.reserve(ys.size());
for (ll y : ys) {
zy[y] = zyid++;
zyR.pb(y);
}
CLEAR(ys);
vector<vii> 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);
}
tmp[xmin].eb(xmax, zy[area[i]]);
}
CLEAR(triangles);
CLEAR(area);
int q = 0;
rep(i, Q) {
int L = queries[i].size();
if (L == 0) {
auto [xmin, xmax, _q_area] = triangles_in_queries[q++];
xmin = zx[xmin];
xmax = zx[xmax];
tmp[xmin].eb(xmax, zy[LLONG_MIN]);
}
}
SegmentTreeFractionalCascading<int> seg(tmp);
CLEAR(tmp);
q = 0;
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[q++];
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;
}