結果

問題 No.2710 How many more?
ユーザー mealy
提出日時 2024-03-31 15:41:40
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 256 ms / 2,000 ms
コード長 1,646 bytes
コンパイル時間 5,561 ms
コンパイル使用メモリ 319,616 KB
実行使用メモリ 6,128 KB
最終ジャッジ日時 2024-09-30 20:53:23
合計ジャッジ時間 8,774 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using mint = atcoder::modint998244353;
// using mint = atcoder::modint1000000007;
using namespace atcoder;
using namespace std;

#define rep(i,n) for (int i = 0; i < n; i++)
using ll = long long;
set<char> abc = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
const int inf =1e9;
const ll infl = 4e18;

template <typename T>
bool chmax(T &a, const T& b) {if (a < b) {a = b;  return true;}return false;
}
template <typename T>
bool chmin(T &a, const T& b) {if (a > b) {a = b;  return true;}return false;}

template<typename T>
struct compress {
    vector<T> xs;
    void add(const T &x){
        xs.emplace_back(x);
    }
    void build(){
        sort(xs.begin(), xs.end());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());
    }
    int get(const T &x){
        return lower_bound(xs.begin(), xs.end(), x) - xs.begin();
    }
    int size() const {
        return xs.size();
    }
    const T &operator[](int i) const {
        return xs[i];
    }
};

int main(){
    int N,Q; cin >> N >> Q;
    vector<ll> A(N);rep(i,N) cin >> A[i];
    vector<pair<int,int>> xy(Q);
    rep(i,Q){
        int x,y; cin >> x >> y;
        x--;y--;
        xy[i] = {x,y};
    }
    compress<ll> cc;
    rep(i,N){
        cc.add(A[i]);
    }
    cc.build();
    fenwick_tree<int> ft(cc.size());
    rep(i,N){
        ft.add(cc.get(A[i]),1);
    }
    for (auto [x,y] : xy){
        if (cc.get(A[x])<=cc.get(A[y])){
            cout << 0 << endl;
            continue;
        }
        cout << ft.sum(cc.get(A[y])+1,cc.get(A[x])) << endl;
    }
}
0