結果
問題 | No.1982 [Cherry 4th Tune B] 絶険 |
ユーザー |
![]() |
提出日時 | 2022-06-17 22:36:12 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,672 bytes |
コンパイル時間 | 1,974 ms |
コンパイル使用メモリ | 175,132 KB |
実行使用メモリ | 13,640 KB |
最終ジャッジ日時 | 2024-10-09 08:50:28 |
合計ジャッジ時間 | 8,214 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 3 TLE * 1 -- * 31 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;using P = pair<ll,ll>;#define fix(x) fixed << setprecision(x)#define asc(x) x, vector<x>, greater<x>#define rep(i, n) for(ll i = 0; i < n; i++)#define all(x) (x).begin(),(x).end()template<class T>bool chmin(T&a, const T&b){if(a>b){a=b;return 1;}return 0;}template<class T>bool chmax(T&a, const T&b){if(a<b){a=b;return 1;}return 0;}struct op{ll l,r,c,h;};struct query{ll I,x;};int main(){cin.tie(nullptr);ios::sync_with_stdio(false);ll n,k,q;const ll d = 1;cin >> n >> k >> q;vector<op> a(k);rep(i,k){cin >> a[i].l >> a[i].r >> a[i].c >> a[i].h;a[i].l--;}vector<ll> ans(q,-1);vector<query> b(q);rep(i,q){cin >> b[i].I >> b[i].x;b[i].I--;}ll tail = 0;vector<ll> tot(n+1,0);rep(i,k){vector<ll> imos(n+1,0);if(i*d>=k) break;auto pre = tot;tail += d;for(ll j=i*d;j<min(k,tail);j++){imos[a[j].l] += a[j].h;imos[a[j].r] -= a[j].h;}rep(j,n){tot[j] += imos[j];imos[j+1] += imos[j];}rep(j,q){ll itr = b[j].I, nh = pre[itr];if(ans[j]>0 || tot[itr]<b[j].x) continue;for(ll p=i*d;p<min(k,tail);p++){if(a[p].l<=itr && itr<a[p].r){nh += a[p].h;if(nh>=b[j].x){ans[j] = a[p].c;break;}}}}}rep(i,q) cout << ans[i] << '\n';return 0;}