結果
問題 | No.1982 [Cherry 4th Tune B] 絶険 |
ユーザー | 👑 Nachia |
提出日時 | 2022-06-17 22:15:21 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WJ
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,786 bytes |
最終ジャッジ日時 | 2024-04-17 14:18:58 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ソースコード
#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;