結果
問題 | No.2710 How many more? |
ユーザー |
|
提出日時 | 2024-03-31 14:20:44 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 238 ms / 2,000 ms |
コード長 | 1,518 bytes |
コンパイル時間 | 3,103 ms |
コンパイル使用メモリ | 259,944 KB |
実行使用メモリ | 8,448 KB |
最終ジャッジ日時 | 2024-09-30 19:23:23 |
合計ジャッジ時間 | 6,456 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 17 |
ソースコード
#ifndef akinyan #define akinyan #include <bits/stdc++.h> using namespace std; using ch = char; using ll = long long; using ld = long double; using db = double; using st = string; using vdb = vector<db>; using vvdb = vector<vdb>; using vl = vector<ll>; using vvl = vector<vl>; using vvvl = vector<vvl>; using vd = vector<ld>; using vvd = vector<vd>; using vs = vector<st>; using vvs = vector<vs>; using vc = vector<ch>; using vvc = vector<vc>; using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>; const ll mod = 998244353; const ll MOD = 1000000007; const ll INF = 1000000000000000000LL; using pall = pair<ll,ll>; using vp = vector<pall>; #endif #include <atcoder/segtree> ll op(ll a, ll b){ return a + b; } ll e(){ return 0; } int main(){ ll N,Q; cin>>N>>Q; vp A(N); set<ll> X; for(int i=0; i<N; i++){ cin >> A[i].first; A[i].second = i; } vl P(N); sort(A.begin(),A.end()); P[A[0].second] = 0; for(int i=1; i<N; i++){ if(A[i-1].first == A[i].first){ P[A[i].second] = P[A[i-1].second]; } else{ P[A[i].second] = P[A[i-1].second] + 1; } } atcoder::segtree<ll,op,e> Seg(N); for(int i=0; i<N; i++){ Seg.set(P[i],Seg.get(P[i]) + 1); } while(Q--){ ll x,y; cin>>x>>y; x--,y--; if(P[x] <= P[y]){ cout << 0 << endl; } else{ cout << Seg.prod(P[y] + 1,P[x]) << endl; } } }