結果
問題 |
No.1982 [Cherry 4th Tune B] 絶険
|
ユーザー |
👑 ![]() |
提出日時 | 2022-06-17 22:15:21 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 327 ms / 3,000 ms |
コード長 | 1,786 bytes |
コンパイル時間 | 3,869 ms |
コンパイル使用メモリ | 140,720 KB |
最終ジャッジ日時 | 2025-01-29 22:09:15 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 35 |
ソースコード
#include <iostream> #include <string> #include <vector> #include <algorithm> #include <atcoder/modint> #include <atcoder/segtree> using namespace std; using i32 = int32_t; using u32 = uint32_t; using i64 = int64_t; using u64 = uint64_t; #define rep(i,n) for(int i=0; i<(int)(n); i++) const i64 INF = 1001001001001001001; using modint = atcoder::static_modint<1000000007>; template<class S> struct SegtreeSum{ static S op(S l, S r){ return l + r; } static S e(){ return S(0); } using Type = struct atcoder::segtree<S,op,e>; struct LessThan{ S y; LessThan(const S& s) : y(s) {} bool operator()(S x) const { return x < y; } }; }; int main(){ int N; cin >> N; int K; cin >> K; int Q; cin >> Q; struct AddQuery{ int p; i64 x; }; vector<vector<AddQuery>> addQueries(N+1); vector<int> col(K+1, -1); rep(i,K){ int l; cin >> l; l--; int r; cin >> r; int c; cin >> c; int k; cin >> k; addQueries[l].push_back({ i, k }); addQueries[r].push_back({ i, -k }); col[i] = c; } struct AnswerQuery{ i64 h; int idx; }; vector<vector<AnswerQuery>> answerQueries(N); rep(i,Q){ int p; cin >> p; p--; i64 h; cin >> h; answerQueries[p].push_back({ h, i }); } vector<int> ans(Q, -1); SegtreeSum<i64>::Type rq(K); rep(i,N){ for(auto q : addQueries[i]) rq.set(q.p, rq.get(q.p) + q.x); for(auto q : answerQueries[i]) ans[q.idx] = col[rq.max_right(0, SegtreeSum<i64>::LessThan(q.h))]; } rep(i,Q) cout << ans[i] << '\n'; return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); } } ios_do_not_sync_instance;