結果
問題 | No.2101 [Cherry Alpha N] ずっとこの数列だったらいいのに |
ユーザー |
![]() |
提出日時 | 2022-10-17 11:21:02 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 297 ms / 6,000 ms |
コード長 | 2,569 bytes |
コンパイル時間 | 13,576 ms |
コンパイル使用メモリ | 304,948 KB |
最終ジャッジ日時 | 2025-02-08 07:33:27 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 42 |
ソースコード
#pragma GCC optimize("Ofast")#pragma GCC optimize(1)#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC target("popcnt")#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef string str;typedef pair<ll,ll> pii;#define F first#define S second#define pb push_back#define pq priority_queue#define all(x) (x).begin(),(x).end()#define bug(x) cerr << (x) << '\n'#define yn(x) cout << (x==1?"Yes\n":"No\n")#define PI 3.14159265358979323#define Ststone ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)const ll max_n=2e5+20,max_int=2147483647,mod1=1e9+7,mod2=998244353;const bool online = 0;ll dx[8] = {1,0,0,-1,1,1,-1,-1};ll dy[8] = {0,1,-1,0,1,-1,1,-1};ll t,n,q,m,k,a,b,c,d,e,f,x,bit[max_n][3];vector<ll> v1,v2,v3,v4;vector<pii> v,era,out;vector<pair<pii,pii>> ans;char cc;str s;void update(ll index,ll dalta,ll num){while(index<=max_n){bit[index][num] += dalta;index += index&(-index);}}ll query(ll index,ll num){ll sum = 0;while(index){sum += bit[index][num];index -= index&(-index);}return sum;}void solve(){cin >> n;for(ll i=1;i<=n;i++){cin >> a >> b;v1.pb(a);v2.pb(b);v.pb({b,i});era.pb({a+b-1,i});update(i,a,0);}cin >> q;for(ll i=0;i<q;i++){cin >> a >> b >> c;ans.pb({{a,i},{b,c}});}sort(all(v));sort(all(era));sort(all(ans));ll l = 0,r = 0;for(ll i=0;i<q;i++){ll x = ans[i].F.F,y = ans[i].S.F,z = ans[i].S.S;while(l<n&&v[l].F<=x){update(v[l].S,v[l].F,1);update(v[l].S,1,2);l++;}while(r<n&&era[r].F<=x){//cout << r << " : " << era[r].S << '\n';update(era[r].S,-v1[era[r].S-1],0);update(era[r].S,-v2[era[r].S-1],1);update(era[r].S,-1,2);r++;}ll sum = query(z,0)-query(y-1,0) -( (x+1)*(query(z,2)-query(y-1,2)) - (query(z,1)-query(y-1,1)));out.pb({ans[i].F.S,sum});//cout << x << ' ' << query(100,0) << ' ' <<query(100,1) << '\n';}sort(all(out));for(ll i=0;i<q;i++){cout << out[i].S << '\n';}}int main(){Ststone;if(online){#ifndef ONLINE_JUDGEfreopen("input.txt","r",stdin);freopen("output.txt","w",stdout);#else#endif}//cin >> t;t = 1;for(ll i=1;i<=t;i++){//cout << "Case #"<<i<<": ";solve();}}/**/