#967603 (C++23) No.2710 How many more?

提出ソース

結果

問題	No.2710 How many more?
ユーザー	mizuho0613
提出日時	2024-03-31 15:23:46
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	6,728 bytes
コンパイル時間	5,016 ms
コンパイル使用メモリ	321,364 KB
実行使用メモリ	19,968 KB
最終ジャッジ日時	2024-09-30 20:38:08
合計ジャッジ時間	10,282 ms
ジャッジサーバーID （参考情報）	judge1 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,820 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	243 ms 13,312 KB
testcase_03	WA	-
testcase_04	WA	-
testcase_05	AC	98 ms 11,008 KB
testcase_06	WA	-
testcase_07	AC	83 ms 6,824 KB
testcase_08	AC	71 ms 6,912 KB
testcase_09	WA	-
testcase_10	WA	-
testcase_11	AC	167 ms 8,832 KB
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	AC	2 ms 6,816 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include<bits/stdc++.h>
#include<random>
#include<atcoder/all>

#define start_template                 \
    cin.tie(nullptr);                  \
    cout.tie(nullptr);                 \
    ios::sync_with_stdio(false);       \
    cout<<fixed<<setprecision(15);     \
    srand((unsigned)time(NULL));
#define rep(i,n) for(ll i=0;i<(ll)(n);++i)
#define rep1(i,n) for(ll i=1;i<=(ll)(n);++i)
#define rep2(i,m,n) for(ll i=(ll)(m);i<(ll)(n);++i)
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;--i)
#define rrep1(i,n) for(ll i=(ll)(n);i>0;--i)
#define rrep2(i,m,n) for(ll i=(ll)(m);i>n;--i)
#define _GLIBCXX_DEBUG
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define SORT(a) sort(all(a));
#define RSORT(a) sort(rall(a));
#define REV(a) reverse(all(a));
#define MIN(a) *min_element(all(a))
#define MAX(a) *max_element(all(a))
#define SUM(a) accumulate(all(a),0LL)
#define lb(a,x) static_cast<int>(lower_bound(all(a),x)-a.begin())
#define ub(a,x) static_cast<int>(upper_bound(all(a),x)-a.begin())
#define SZ(a) ll(a.size())
#define CEIL(x,y) (x+y-1)/y
#define smallexpect(a,b) (a%smallMOD)*pow_mod(b,smallMOD-2,smallMOD)%smallMOD
#define bigexpect(a,b) (a%bigMOD)*pow_mod(b,bigMOD-2,bigMOD)%bigMOD
#define pf push_front
#define pb push_back
#define eb emplace_back
#define ppf pop_front()
#define ppb pop_back()
#define fi first
#define se second
#define INT(...) int __VA_ARGS__;scan(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;scan(__VA_ARGS__)
#define STRING(...) string __VA_ARGS__;scan(__VA_ARGS__)
#define CHAR(...) char __VA_ARGS__;scan(__VA_ARGS__)
#define DOUBLE(...) double __VA_ARGS__;scan(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;scan(__VA_ARGS__)
#define YES print("YES");
#define Yes print("Yes");
#define yes print("yes");
#define NO print("NO");
#define No print("No");
#define no print("no");
#define YESNO {print("YES");}else{print("NO");}
#define YesNo {print("Yes");}else{print("No");}
#define yesno {print("yes");}else{print("no");}
#define TA {print("Takahashi");}else{print("Aoki");}

using namespace std;using namespace atcoder;
using ull=unsigned long long;using ll=long long;using ld=long double;using i7=__int128_t;
using pii=pair<int,int>;using pid=pair<int,ld>;using pis=pair<int,string>;using pll=pair<ll,ll>;
using pld=pair<ll,ld>;using pls=pair<ll,string>;using pdi=pair<ld,int>;using pdl=pair<ld,ll>;
using pdd=pair<ld,ld>;using pds=pair<ld,string>;using psi=pair<string, int>;using psl=pair<string,ll>;
using psd=pair<string,ld>;using pss=pair<string, string>;using mii=map<int, int>;using mid=map<int,ld>;
using mis=map<int,string>;using mll=map<ll,ll>;using mld=map<ll,ld>;using mls=map<ll,string>;using mli=map<ll,int>;
using mdi=map<ld,int>;using mdl=map<ld,ll>;using mdd=map<ld,ld>;using mds=map<ld,string>;using mil=map<int,ll>;
using msi=map<string, int>;using msl=map<string, ll>;using msd=map<string,ld>;using mss=map<string,string>;
using vi=vector<int>;using vi7=vector<i7>;using vs=vector<string>;using vl=vector<ll>;using vc=vector<char>;
using vb=vector<bool>;using vd=vector<ld>;using vpii=vector<pii>;using vpll=vector<pll>;using vpsi=vector<psi>;
using vpis=vector<pis>;using si=set<int>;using sl=set<ll>;using sc=set<char>;using ss=set<string>;
using sd=set<ld>;using vvi=vector<vi>;using vvi7=vector<vi7>;using vvl=vector<vl>;using vvc=vector<vc>;
using vvs=vector<vs>;using vvb=vector<vb>;using vvd=vector<vd>;using vvpii=vector<vpii>;using vvpll=vector<vpll>;
using vsi=vector<si>;using vsl=vector<sl>;using vvvi=vector<vvi>;using vvvi7=vector<vvi7>;using vvvl=vector<vvl>;
using vvvc=vector<vvc>;using vvvb=vector<vvb>;using vvvd=vector<vvd>;using mint=modint998244353;
using vvvvi=vector<vvvi>;using vvvvl=vector<vvvl>;using vvvvi7=vector<vvvi7>;using vvvvc=vector<vvvc>;
using vvvvb=vector<vvvb>;using vvvvd=vector<vvvd>;using vmii=vector<mii>;using vmil=vector<mil>;using vmli=vector<mli>;
using vmll=vector<mll>;using vmsi=vector<msi>;using vmsl=vector<msl>;using vmis=vector<mis>;using vmls=vector<mls>;
using vmss=vector<mss>;using vmid=vector<mid>;using vmdi=vector<mdi>;using vmdd=vector<mdd>;using vmld=vector<mld>;
using vmdl=vector<mdl>;using vmds=vector<mds>;using vmsd=vector<msd>;

void scan(){}
template<class T>void scan(vector<T> &v){
    for(T &t:v)cin>>t;
}
template<class T>void scan(vector<vector<T>> &v){
    for(auto &row:v)for(T&element:row)cin>>element;
}
template<class Head, class... Tail>void scan(Head &head, Tail &...tail){
    cin>>head;scan(tail...);
}
template<class T>void print(const T &t){
    cout<<t<<endl;
}
template<class Head,class...Tail>void print(const Head &head, const Tail &...tail){
    cout<<head;print(tail...);
}
template<class T>void vecout1(const vector<T> &v,char div='\n'){
    rep(i,v.size())cout<<v[i]<<(i==ll(v.size()-1)?div:' ');
}
template<class T>void vecout2(const vector<T> &v,char div='\n'){
    rep(i,v.size())cout<<v[i]<<div;
}
template<class T>void operator++(vector<T> &v,int){for(T &t:v)t++;}
template<class T>void operator--(vector<T> &v,int){for(T &t:v)t--;}
template<class T>void operator+=(vector<T> &v,T x){for(T &t:v)t+=x;}
template<class T>void operator-=(vector<T> &v,T x){for (T &t:v)t-=x;}
template<class T>void operator*=(vector<T> &v,T x){for(T &t:v)t*=x;}
template<class T>void operator/=(vector<T> &v,T x){for(T &t:v)t/=x;}
template<typename T>bool chmax(T &a, T b){return((a<b)?(a=b,true):(false));}
template<typename T>bool chmin(T &a, T b){return((a>b)?(a=b,true):(false));}
template<class T>void uni(T &a){
    sort(all(a));
    a.erase(unique(all(a)),a.end());
}

const ld PI=3.1415926535897932;
const int INF=INT_MAX-314159;const ll LINF=LLONG_MAX-3141592653;
const int bigMOD=1000000007;int smallMOD=998244353;
const int dx[]={-1,0,1,0,-1,1,1,-1};const int dy[]={0,1,0,-1,1,1,-1,-1};
const string ALPHA="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string alpha="abcdefghijklmnopqrstuvwxyz";
/*--------------------------------------------------------------------------------------------------------------------------*/

/*--------------------------------------------------------------------------------------------------------------------------*/
int main(){
    start_template

    LL(n,q);vl a(n);scan(a);
    vpll p(n);
    rep(i,n){
        p[i].fi=a[i];
        p[i].se=i;
    }
    SORT(p);
    
    map<ll,ll>m;
    rep(i,n){
        m[p[i].se]=p[i].fi;
    }

    vpll p2(n);
    rep(i,n){
        p2[i].fi=p[i].se;
        p2[i].se=i;
    }

    ll cnt=1;
    rep(i,n-1){
        if(m[p2[i].fi]==m[p2[i+1].fi]){
            p2[i+1].se-=cnt;
            cnt++;
        }else{
            cnt=1;
        }
    }

    map<ll,ll>m2;
    rep(i,n){
        m2[p2[i].fi]=p2[i].se;
    }

    while(q--){
        LL(x,y);x--;y--;
        print(max(0LL,m2[x]-m2[y]-1));
    }
}

yukicoder

結果

テストケース

ソースコード