結果
問題 | No.1982 [Cherry 4th Tune B] 絶険 |
ユーザー |
![]() |
提出日時 | 2022-06-17 21:52:28 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 347 ms / 3,000 ms |
コード長 | 1,188 bytes |
コンパイル時間 | 4,246 ms |
コンパイル使用メモリ | 254,148 KB |
最終ジャッジ日時 | 2025-01-29 21:48:20 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 35 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:19:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 19 | scanf("%d %d %d %d",&L[i],&R[i],&C[i],&H[i]); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ main.cpp:27:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 27 | scanf("%lld %lld",&I[i],&X[i]); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 1000000001 int main(){ int N,K,Q; cin>>N>>K>>Q; vector<vector<int>> Add(N),Del(N); vector<int> L(K),R(K),C(K),H(K); rep(i,K){ scanf("%d %d %d %d",&L[i],&R[i],&C[i],&H[i]); L[i]--,R[i]--; Add[L[i]].push_back(i); Del[R[i]].push_back(i); } vector<vector<int>> Qs(N); vector<long long> I(Q),X(Q); rep(i,Q){ scanf("%lld %lld",&I[i],&X[i]); I[i]--; Qs[I[i]].push_back(i); } fenwick_tree<long long> F(K); vector<int> ans(Q,-1); rep(i,N){ //cout<<i<<endl; rep(j,Add[i].size()){ int ii = Add[i][j]; F.add(ii,H[ii]); } //cout<<i<<endl; rep(j,Qs[i].size()){ int ii = Qs[i][j]; if(F.sum(0,K)<X[ii])continue; int ok = 0,ng = K; while(ng-ok>1){ int mid = (ok+ng)/2; if(F.sum(0,mid) < X[ii])ok = mid; else ng = mid; } ans[ii] = C[ok]; } //cout<<i<<endl; rep(j,Del[i].size()){ int ii = Del[i][j]; F.add(ii,-H[ii]); } //cout<<i<<endl; } rep(i,Q){ printf("%d\n",ans[i]); } return 0; }