結果
問題 | No.1982 [Cherry 4th Tune B] 絶険 |
ユーザー | milanis48663220 |
提出日時 | 2022-06-17 22:13:42 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 892 ms / 3,000 ms |
コード長 | 3,297 bytes |
コンパイル時間 | 1,381 ms |
コンパイル使用メモリ | 127,136 KB |
実行使用メモリ | 18,832 KB |
最終ジャッジ日時 | 2024-04-17 14:16:01 |
合計ジャッジ時間 | 17,836 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 9 ms
5,596 KB |
testcase_03 | AC | 293 ms
9,100 KB |
testcase_04 | AC | 356 ms
9,384 KB |
testcase_05 | AC | 222 ms
9,352 KB |
testcase_06 | AC | 385 ms
12,124 KB |
testcase_07 | AC | 432 ms
13,488 KB |
testcase_08 | AC | 365 ms
9,744 KB |
testcase_09 | AC | 401 ms
11,500 KB |
testcase_10 | AC | 355 ms
11,476 KB |
testcase_11 | AC | 191 ms
8,248 KB |
testcase_12 | AC | 435 ms
11,660 KB |
testcase_13 | AC | 301 ms
8,072 KB |
testcase_14 | AC | 234 ms
10,240 KB |
testcase_15 | AC | 286 ms
8,156 KB |
testcase_16 | AC | 293 ms
11,392 KB |
testcase_17 | AC | 620 ms
16,144 KB |
testcase_18 | AC | 500 ms
14,336 KB |
testcase_19 | AC | 566 ms
15,716 KB |
testcase_20 | AC | 125 ms
6,944 KB |
testcase_21 | AC | 146 ms
7,800 KB |
testcase_22 | AC | 328 ms
9,068 KB |
testcase_23 | AC | 149 ms
6,820 KB |
testcase_24 | AC | 207 ms
8,136 KB |
testcase_25 | AC | 569 ms
14,636 KB |
testcase_26 | AC | 550 ms
14,916 KB |
testcase_27 | AC | 100 ms
5,960 KB |
testcase_28 | AC | 300 ms
5,632 KB |
testcase_29 | AC | 892 ms
18,688 KB |
testcase_30 | AC | 770 ms
18,712 KB |
testcase_31 | AC | 319 ms
9,288 KB |
testcase_32 | AC | 727 ms
17,800 KB |
testcase_33 | AC | 698 ms
18,832 KB |
testcase_34 | AC | 653 ms
17,152 KB |
ソースコード
#include <iostream> #include <algorithm> #include <iomanip> #include <vector> #include <queue> #include <deque> #include <set> #include <map> #include <tuple> #include <cmath> #include <numeric> #include <functional> #include <cassert> #define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl; #define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } using namespace std; typedef long long ll; template<typename T> vector<vector<T>> vec2d(int n, int m, T v){ return vector<vector<T>>(n, vector<T>(m, v)); } template<typename T> vector<vector<vector<T>>> vec3d(int n, int m, int k, T v){ return vector<vector<vector<T>>>(n, vector<vector<T>>(m, vector<T>(k, v))); } template<typename T> void print_vector(vector<T> v, char delimiter=' '){ if(v.empty()) { cout << endl; return; } for(int i = 0; i+1 < v.size(); i++) cout << v[i] << delimiter; cout << v.back() << endl; } //1-indexed template <typename T> struct bit{ int n; vector<T> data; bit(int n_){ n = 1; while(n < n_) n *= 2; data = vector<T>(n+1); for(int i = 0; i <= n; i++) data[i] = 0; } T sum(int i){ T ret = 0; while(i > 0){ ret += data[i]; i -= i&-i; } return ret; } void add(int i, T x){ while(i <= n){ data[i] += x; i += i&-i; } } }; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; int n, k, q; cin >> n >> k >> q; vector<int> l(k), r(k), c(k), h(k); for(int i = 0; i < k; i++){ cin >> l[i] >> r[i] >> c[i] >> h[i]; } vector<int> pos(q); vector<ll> x(q); for(int i = 0; i < q; i++){ cin >> pos[i] >> x[i]; } if(k == 0){ for(int i = 0; i < q; i++) cout << -1 << endl; return 0; } vector<int> cnt_l(q, -1), cnt_r(q, k-1); vector<bool> ok(q, true); auto judge_final = [&](){ vector<ll> imos(n+2); for(int i = 0; i < k; i++){ imos[l[i]] += h[i]; imos[r[i]+1] -= h[i]; } for(int i = 1; i <= n; i++) imos[i] += imos[i-1]; for(int i = 0; i < q; i++){ if(imos[pos[i]] < x[i]){ ok[i] = false; } } }; judge_final(); int rem = 20; while(rem--){ bit<ll> bt(n+1); vector<vector<int>> query(k); for(int i = 0; i < q; i++){ if(!ok[i]) continue; if(cnt_r[i] == cnt_l[i]+1) continue; int x = (cnt_l[i]+cnt_r[i])/2; query[x].push_back(i); } for(int i = 0; i < k; i++){ bt.add(l[i], h[i]); bt.add(r[i]+1, -h[i]); for(int idx: query[i]){ if(bt.sum(pos[idx]) >= x[idx]) cnt_r[idx] = i; else cnt_l[idx] = i; } } } for(int i = 0; i < q; i++){ if(!ok[i]) cout << -1 << endl; else cout << c[cnt_r[i]] << endl; } }