結果
問題 | No.1625 三角形の質問 |
ユーザー | Kude |
提出日時 | 2021-07-23 22:57:16 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 997 ms / 6,000 ms |
コード長 | 3,127 bytes |
コンパイル時間 | 5,054 ms |
コンパイル使用メモリ | 289,148 KB |
実行使用メモリ | 9,676 KB |
最終ジャッジ日時 | 2023-09-26 00:04:59 |
合計ジャッジ時間 | 19,760 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 20 ms
4,384 KB |
testcase_02 | AC | 264 ms
4,832 KB |
testcase_03 | AC | 112 ms
5,108 KB |
testcase_04 | AC | 152 ms
4,380 KB |
testcase_05 | AC | 378 ms
5,132 KB |
testcase_06 | AC | 977 ms
8,492 KB |
testcase_07 | AC | 994 ms
9,412 KB |
testcase_08 | AC | 984 ms
8,832 KB |
testcase_09 | AC | 997 ms
8,824 KB |
testcase_10 | AC | 997 ms
8,744 KB |
testcase_11 | AC | 991 ms
9,676 KB |
testcase_12 | AC | 992 ms
8,680 KB |
testcase_13 | AC | 986 ms
9,092 KB |
testcase_14 | AC | 980 ms
9,008 KB |
testcase_15 | AC | 987 ms
8,992 KB |
testcase_16 | AC | 726 ms
5,080 KB |
testcase_17 | AC | 101 ms
8,344 KB |
testcase_18 | AC | 136 ms
5,420 KB |
testcase_19 | AC | 124 ms
9,012 KB |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; #define rep(i,n)for (int i = 0; i < int(n); ++i) #define rrep(i,n)for (int i = int(n)-1; i >= 0; --i) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() template<class T> void chmax(T& a, const T& b) {a = max(a, b);} template<class T> void chmin(T& a, const T& b) {a = min(a, b);} using ll = long long; using P = pair<int,int>; using VI = vector<int>; using VVI = vector<VI>; using VL = vector<ll>; using VVL = vector<VL>; constexpr int SQ = 500; using TR = tuple<int, int, ll>; TR get_triangle() { int a, b, c, d, e, f; cin >> a >> b >> c >> d >> e >> f; int l = min({a, c, e}); int r = max({a, c, e}) + 1; ll dx1 = c - a, dy1 = d - b; ll dx2 = e - a, dy2 = f - b; ll s = abs(dx1 * dy2 - dx2 * dy1); return {l, r, s}; } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; vector<TR> triangles; rep(_, n) { auto t = get_triangle(); triangles.push_back(t); } auto mycmp = [&](const TR& x, const TR& y) { return get<1>(x) < get<1>(y); }; sort(all(triangles), mycmp); VL ans(q, -1); vector<char> is_ask_query(q); for(int b = 0; b < q; b += SQ) { int nb = min(b + SQ, q); vector<TR> new_triangles; vector<tuple<int, int, int>> ask_queries; for(int i = b; i < nb; i++) { int type; cin >> type; if (type == 1) { auto t = get_triangle(); new_triangles.push_back(t); } else { is_ask_query[i] = true; int l, r; cin >> l >> r; r++; ask_queries.emplace_back(i, l, r); for(auto [li, ri, si]: new_triangles) if (l <= li && ri <= r) { chmax(ans[i], si); } } } sort(all(ask_queries), [&](auto& x, auto& y) {return get<2>(x) < get<2>(y);}); auto nxt = triangles.begin(); map<int, ll> mp; mp[-1] = 3002003004005006007LL; mp[1001001001] = -1; for(auto [i, l, r]: ask_queries) { while(nxt != triangles.end() && get<1>(*nxt) <= r) { auto [li, ri, si] = *nxt; nxt++; if (si <= mp.lower_bound(li)->second) continue; mp[li] = si; for(auto it = mp.find(li);;) { auto t = prev(it); if (t->second <= si) { mp.erase(t); } else { break; } } } auto it = mp.lower_bound(l); chmax(ans[i], it->second); } sort(all(new_triangles), mycmp); int old_sz = triangles.size(); for(auto t: new_triangles) triangles.push_back(t); inplace_merge(triangles.begin(), triangles.begin() + old_sz, triangles.end(), mycmp); } rep(i, q) if (is_ask_query[i]) cout << ans[i] << '\n'; }