結果
問題 | No.2101 [Cherry Alpha N] ずっとこの数列だったらいいのに |
ユーザー |
![]() |
提出日時 | 2022-10-14 22:28:19 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 218 ms / 6,000 ms |
コード長 | 1,833 bytes |
コンパイル時間 | 2,069 ms |
コンパイル使用メモリ | 185,072 KB |
実行使用メモリ | 20,544 KB |
最終ジャッジ日時 | 2024-06-26 15:50:48 |
合計ジャッジ時間 | 13,905 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 42 |
コンパイルメッセージ
main.cpp: In function 'int main()': main.cpp:57:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 57 | for(auto [d,l,r,i]:query){ | ^
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using P = pair<ll,ll>; using T = tuple<ll,ll,ll,int>; #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;} template <typename T> struct BIT{ int n; vector<T> data; BIT(int n=0) : n(n), data(n+1){} T sum(int i){ T res = 0; for(; i; i -= i&-i){ res += data[i]; } return res; } void add(int i, T x){ for(; i <= n; i += i&-i){ data[i] += x; } } }; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n,q; cin >> n; BIT<ll> bit(n), ok(n); vector<P> a(n), t(n); rep(i,n){ cin >> a[i].first >> t[i].first; t[i].first--; bit.add(i+1, a[i].first); a[i].first += t[i].first; a[i].second = t[i].second = i+1; } sort(all(a)); sort(all(t)); cin >> q; vector<ll> ans(q); vector<T> query(q); rep(i,q){ ll d,l,r; cin >> d >> l >> r; l--; query[i] = {d,l,r,i}; } sort(all(query)); int nb = 0, ne = 0; for(auto [d,l,r,i]:query){ while(nb<n && t[nb].first<d){ ok.add(t[nb].second, 1); bit.add(t[nb].second, t[nb].first); nb++; } while(ne<n && a[ne].first<d){ ok.add(a[ne].second, -1); bit.add(a[ne].second, -a[ne].first); ne++; } ans[i] = (bit.sum(r) - bit.sum(l)) - d * (ok.sum(r) - ok.sum(l)); } rep(i,q) cout << ans[i] << '\n'; return 0; }