結果
問題 | No.2710 How many more? |
ユーザー | umezo |
提出日時 | 2024-03-31 14:36:21 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 328 ms / 2,000 ms |
コード長 | 1,592 bytes |
コンパイル時間 | 2,892 ms |
コンパイル使用メモリ | 259,312 KB |
実行使用メモリ | 13,952 KB |
最終ジャッジ日時 | 2024-03-31 14:36:30 |
合計ジャッジ時間 | 7,308 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,676 KB |
testcase_01 | AC | 2 ms
6,676 KB |
testcase_02 | AC | 225 ms
9,600 KB |
testcase_03 | AC | 146 ms
9,984 KB |
testcase_04 | AC | 140 ms
13,184 KB |
testcase_05 | AC | 98 ms
8,320 KB |
testcase_06 | AC | 117 ms
11,776 KB |
testcase_07 | AC | 83 ms
6,676 KB |
testcase_08 | AC | 69 ms
6,676 KB |
testcase_09 | AC | 210 ms
11,392 KB |
testcase_10 | AC | 111 ms
7,680 KB |
testcase_11 | AC | 164 ms
6,912 KB |
testcase_12 | AC | 287 ms
12,928 KB |
testcase_13 | AC | 301 ms
13,952 KB |
testcase_14 | AC | 302 ms
13,952 KB |
testcase_15 | AC | 323 ms
13,952 KB |
testcase_16 | AC | 328 ms
13,952 KB |
testcase_17 | AC | 301 ms
13,952 KB |
testcase_18 | AC | 2 ms
6,676 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; }