結果
問題 | No.2220 Range Insert & Point Mex |
ユーザー | 00 Sakuda |
提出日時 | 2024-04-11 02:45:29 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 9,459 bytes |
コンパイル時間 | 2,701 ms |
コンパイル使用メモリ | 229,492 KB |
実行使用メモリ | 13,812 KB |
最終ジャッジ日時 | 2024-10-02 21:15:55 |
合計ジャッジ時間 | 13,342 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 3 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 2 ms
5,248 KB |
testcase_09 | AC | 3 ms
5,248 KB |
testcase_10 | AC | 2 ms
5,248 KB |
testcase_11 | AC | 2 ms
5,248 KB |
testcase_12 | AC | 2 ms
5,248 KB |
testcase_13 | AC | 350 ms
13,312 KB |
testcase_14 | AC | 330 ms
13,216 KB |
testcase_15 | AC | 330 ms
13,184 KB |
testcase_16 | AC | 331 ms
13,184 KB |
testcase_17 | AC | 344 ms
13,312 KB |
testcase_18 | AC | 339 ms
13,184 KB |
testcase_19 | AC | 329 ms
13,184 KB |
testcase_20 | AC | 357 ms
13,184 KB |
testcase_21 | AC | 365 ms
13,312 KB |
testcase_22 | AC | 363 ms
13,312 KB |
testcase_23 | AC | 307 ms
13,760 KB |
testcase_24 | AC | 207 ms
9,688 KB |
testcase_25 | AC | 259 ms
12,380 KB |
testcase_26 | AC | 279 ms
11,208 KB |
testcase_27 | AC | 94 ms
6,036 KB |
testcase_28 | AC | 160 ms
8,320 KB |
testcase_29 | WA | - |
testcase_30 | AC | 170 ms
8,328 KB |
testcase_31 | AC | 258 ms
11,204 KB |
testcase_32 | AC | 229 ms
11,648 KB |
testcase_33 | AC | 239 ms
11,776 KB |
testcase_34 | AC | 293 ms
12,328 KB |
testcase_35 | AC | 306 ms
12,416 KB |
testcase_36 | AC | 280 ms
12,672 KB |
testcase_37 | AC | 291 ms
12,672 KB |
testcase_38 | AC | 287 ms
13,812 KB |
ソースコード
#include <bits/stdc++.h> #include <iostream> #include <vector> #include <math.h> #include <algorithm> #include <set> #include <map> #include <unordered_map> #include <queue> #include <deque> #include <stack> #include <string> #include <bitset> #include <iomanip> using namespace std; using ll = long long; using VVI = vector<vector<int>>; using VVL = vector<vector<ll>>; using VI = vector<int>; using VL = vector<ll>; using VS = vector<string>; using VC = vector<char>; using VP = vector<pair<int, int>>; using Graph0 = vector<vector<int>>; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define drep(i, a, b) for (int i = (int)(a);i >= (int)(b);i--) #define urep(i, a, b) for (int i = (int)(a);i <= (int)(b);i++) #define lrep(i, n) for (ll i = 0; i < (ll)(n); i++) #define ldrep(i, a, b) for (ll i = (ll)(a);i >= (ll)(b);i--) #define lurep(i, a, b) for (ll i = (ll)(a);i <= (ll)(b);i++) #define arep(i, v) for (auto i : v) #define all(a) (a).begin(), (a).end() #define yes cout << "Yes" << endl #define no cout << "No" << endl #define eyes cout << "Yes" << endl;exit(0); #define eno cout << "No" << endl;exit(0); template <typename T> bool chmax(T &a, const T& b) { if (a < b) { a = b; return true; } return false; } template <typename T> bool chmin(T &a, const T& b) { if (a > b) { a = b; return true; } return false; } template<typename T> void excout(T A) { cout << A << endl; exit(0); } constexpr long long INF = (1LL << 60); // INFにちゅういい! // 辺の情報 struct Edge { // 行先 int to; // コスト int cost; }; using Graph = std::vector<std::vector<Edge>>; // { distance, from } using Pair = std::pair<long long, int>; // ダイクストラ法 (1.1 基本実装) // distances は頂点数と同じサイズ, 全要素 INF で初期化しておく void Dijkstra(const Graph& graph, std::vector<long long>& distances, int startIndex) { // 「現時点での最短距離, 頂点」の順に取り出す priority_queue // デフォルトの priority_queue は降順に取り出すため std::greater を使う std::priority_queue<Pair, std::vector<Pair>, std::greater<Pair>> q; q.emplace((distances[startIndex] = 0), startIndex); while (!q.empty()) { const long long distance = q.top().first; const int from = q.top().second; q.pop(); // 最短距離でなければ処理しない if (distances[from] < distance) { continue; } // 現在の頂点からの各辺について for (const auto& edge : graph[from]) { // to までの新しい距離 const long long d = (distances[from] + edge.cost); // d が現在の記録より小さければ更新 if (d < distances[edge.to]) { q.emplace((distances[edge.to] = d), edge.to); } } } } template<typename T> T MODS(T a, T mods) { return ((((((a + mods) % mods) + mods) % mods))); } //combination 列挙用 --int ver VVI comb(int n, int r) { VVI v(n + 1, VI (n + 1, 0)); for (int i = 0; i < v.size(); i++) { v[i][0] = 1; v[i][i] = 1; } for (int j = 1; j < v.size(); j++) { for (int k = 1; k < j; k++) { v[j][k] = (v[j - 1][k - 1] + v[j - 1][k]); } } return v; } vector<pair<long long, long long> > prime_factorize(long long N) { // 答えを表す可変長配列 vector<pair<long long, long long> > res; // √N まで試し割っていく for (long long p = 2; p * p <= N; ++p) { // N が p で割り切れないならばスキップ if (N % p != 0) { continue; } // N の素因数 p に対する指数を求める int e = 0; while (N % p == 0) { // 指数を 1 増やす ++e; // N を p で割る N /= p; } // 答えに追加 res.emplace_back(p, e); } // 素数が最後に残ることがありうる if (N != 1) { res.emplace_back(N, 1); } return res; } using UNION_TYPE = int; struct UnionFind { vector<UNION_TYPE> par, siz; UnionFind(UNION_TYPE n) : par(n, -1), siz(n, 1) {} UNION_TYPE root(UNION_TYPE x) { if (par[x] == -1) return x; else return par[x] = root(par[x]); } bool issame(UNION_TYPE x, UNION_TYPE y) { return root(x) == root(y); } bool unite(UNION_TYPE x, UNION_TYPE y) { x = root(x);y = root(y); if (x == y) return false; if (siz[x] < siz[y]) swap(x, y); par[y] = x; siz[x] += siz[y]; return true; } UNION_TYPE size(UNION_TYPE x) { return siz[root(x)]; } }; //mod func の型に注意!!! //Union Find はUNION_TYPE で型変可能! // VI topo_sort(Graph0& G) { int N = G.size(); VI IND(N, 0); rep(v, N) { arep(nv, G[v]) { IND[nv]++; } } queue<int> que; rep(v, N) { if (IND[v] == 0) { que.push(v); } } VI ANS; while (!que.empty()) { int v = que.front(); ANS.push_back(v); que.pop(); arep(nv, G[v]) { IND[nv]--; if (IND[nv] == 0) { que.push(nv); } } } return ANS; } void ADD(int a, int b, Graph0& G) { G[a].push_back(b); G[b].push_back(a); } VP near(int i, int j, int H, int W) { VP ans; VP cand = {{i - 1, j}, {i + 1, j}, {i, j - 1}, {i, j + 1}}; arep(v, cand) { if (v.first < 0 or v.first >= H) continue; if (v.second < 0 or v.second >= W) continue; ans.push_back(v); } return ans; } int cast(int i, int j, int H, int W) { return ((W * i) + j); } ll pows(ll x, ll n, ll mod) { if (!n) return 1; x %= mod; ll r = pows(x, n / 2, mod); (r *= r) %= mod; if (n % 2) (r *=x) %= mod; return r; } struct COMB_MOD { ll mod; int MAX; VL fac, finv, inv; COMB_MOD(int max, ll m) { fac.assign(max, 0); finv.assign(max, 0); inv.assign(max, 0); mod = m; MAX = max; } void solve() { fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (int i = 2; i < MAX; i++){ fac[i] = fac[i - 1] * i % mod; inv[i] = mod - inv[mod%i] * (mod / i) % mod; finv[i] = finv[i - 1] * inv[i] % mod; } } ll comb(int n, int k) { if (n < k) return 0; if (n < 0 || k < 0) return 0; return fac[n] * (finv[k] * finv[n - k] % mod) % mod; } }; struct LCA { vector<vector<int>> parent; // parent[k][u]:= u の 2^k 先の親 vector<int> dist; // root からの距離 LCA(const Graph0 &G, int root = 0) { init(G, root); } // 初期化 void init(const Graph0 &G, int root = 0) { int V = G.size(); int K = 1; while ((1 << K) < V) K++; parent.assign(K, vector<int>(V, -1)); dist.assign(V, -1); dfs(G, root, -1, 0); for (int k = 0; k + 1 < K; k++) { for (int v = 0; v < V; v++) { if (parent[k][v] < 0) { parent[k + 1][v] = -1; } else { parent[k + 1][v] = parent[k][parent[k][v]]; } } } } // 根からの距離と1つ先の頂点を求める void dfs(const Graph0 &G, int v, int p, int d) { parent[0][v] = p; dist[v] = d; for (auto e : G[v]) { if (e != p) dfs(G, e, v, d + 1); } } int query(int u, int v) { if (dist[u] < dist[v]) swap(u, v); // u の方が深いとする int K = parent.size(); // LCA までの距離を同じにする for (int k = 0; k < K; k++) { if ((dist[u] - dist[v]) >> k & 1) { u = parent[k][u]; } } // 二分探索で LCA を求める if (u == v) return u; for (int k = K - 1; k >= 0; k--) { if (parent[k][u] != parent[k][v]) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } int get_dist(int u, int v) { return dist[u] + dist[v] - 2 * dist[query(u, v)]; } }; #include <atcoder/fenwicktree> using namespace atcoder; int main(void) { int N;cin >> N; VI L(N), R(N), A(N); rep(i, N) cin >> L[i] >>R[i] >> A[i]; int Q;cin >> Q; VI X(Q + 1, 0); urep(i, 1, Q) cin >> X[i]; VVI IN(Q + 1); VVI OUT(Q + 1); rep(i, N) { auto itr = lower_bound(all(X), L[i]); if (itr == X.end()) continue; int L = itr - X.begin(); auto it2 = upper_bound(all(X), R[i]); if (it2 == X.begin()) continue; it2--; int R = (it2 == X.end() ? Q : it2 - X.begin()); IN[L].push_back(min(N + 1, A[i])); OUT[R].push_back(min(N + 1, A[i])); // cout << i << " " << L << " " << R << endl; } VI CNT(N + 2, 0); fenwick_tree<int> bit(N + 2); urep(i, 1, Q) { arep(v, IN[i]) { CNT[v]++; //cout << i << " V " << v << endl; if (CNT[v] == 1) bit.add(v, 1); } int ng = -1; int ok = N; while (ok - ng > 1) { int x = (ok + ng) / 2; // cout << x << " S " << bit.sum(0, x + 1) << endl; if (bit.sum(0, x + 1) < x + 1) { ok = x; } else { ng = x; } } cout << ok << endl; arep(v, OUT[i]) { CNT[v]--; if (CNT[v] == 0) { bit.add(v, -1); } } } }