結果
問題 | No.2710 How many more? |
ユーザー | umezo |
提出日時 | 2024-03-31 14:36:21 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 291 ms / 2,000 ms |
コード長 | 1,592 bytes |
コンパイル時間 | 3,235 ms |
コンパイル使用メモリ | 259,268 KB |
実行使用メモリ | 13,824 KB |
最終ジャッジ日時 | 2024-09-30 19:44:49 |
合計ジャッジ時間 | 7,094 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,820 KB |
testcase_02 | AC | 199 ms
9,472 KB |
testcase_03 | AC | 131 ms
9,856 KB |
testcase_04 | AC | 127 ms
13,056 KB |
testcase_05 | AC | 79 ms
8,064 KB |
testcase_06 | AC | 107 ms
11,520 KB |
testcase_07 | AC | 73 ms
6,820 KB |
testcase_08 | AC | 62 ms
6,824 KB |
testcase_09 | AC | 194 ms
11,264 KB |
testcase_10 | AC | 98 ms
7,552 KB |
testcase_11 | AC | 154 ms
6,820 KB |
testcase_12 | AC | 252 ms
12,672 KB |
testcase_13 | AC | 264 ms
13,824 KB |
testcase_14 | AC | 291 ms
13,824 KB |
testcase_15 | AC | 281 ms
13,696 KB |
testcase_16 | AC | 274 ms
13,824 KB |
testcase_17 | AC | 283 ms
13,696 KB |
testcase_18 | AC | 1 ms
6,820 KB |
ソースコード
#include<bits/stdc++.h>using namespace std;#define rep(i,n) for(int i=0;i<(int)(n);i++)#define ALL(v) v.begin(),v.end()typedef long long ll;template <class T> using V=vector<T>;template <class T> using VV=V<V<T>>; //B(n,V<int>(n))#define rep(i,n) for(int i=0;i<(int)(n);i++)#define ALL(v) v.begin(),v.end()typedef long long ll;#include <bits/stdc++.h>using namespace std;template<typename T>struct BIT{private:vector<T> A;const int n;public:BIT(int _n) : A(_n+1,0), n(_n){}T sum(int i){i++;T s=0;while(i>0){s+=A[i];i-=i&-i;}return s;}T sum(int i,int j){return sum(j)-sum(i-1);}void add(int i,T x){i++;while(i<=n){A[i]+=x;i+=i&-i;}}void update(int i,T x){T tmp=sum(i,i);if(tmp!=x) add(i,x-tmp);}int lower_bound(T w){if(w<=0) return 0;if(sum(n-1)<w) return n;int x=0,r=1;while(r<n) r=r<<1;for(int len=r;len>0;len=len>>1){if(x+len<n && A[x+len]<w){w-=A[x+len];x+=len;}}return x;}};int main(){ios::sync_with_stdio(false);std::cin.tie(nullptr);int n,q;cin>>n>>q;V<int> A(n);set<int> s;rep(i,n){cin>>A[i];s.insert(A[i]);}map<int,int> m;int now=0;for(auto x:s) m[x]=now++;BIT<ll> bit(now);rep(i,n) bit.add(m[A[i]],1);while(q--){int x,y;cin>>x>>y;x--,y--;if(A[x]<=A[y]){cout<<0<<endl;continue;}ll tmp=bit.sum(m[A[y]]+1,m[A[x]]-1);cout<<tmp<<endl;}return 0;}