結果
問題 | No.2382 Amidakuji M |
ユーザー |
|
提出日時 | 2023-07-16 11:05:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 65 ms / 2,000 ms |
コード長 | 2,038 bytes |
コンパイル時間 | 774 ms |
コンパイル使用メモリ | 102,168 KB |
最終ジャッジ日時 | 2025-02-15 15:12:18 |
ジャッジサーバーID (参考情報) |
judge4 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include<iostream> #include<set> #include<algorithm> #include<vector> #include<string> #include<set> #include<map> #include<numeric> #include<queue> #include<cmath> using namespace std; typedef long long ll; const ll INF=1LL<<60; typedef pair<int,int> P; typedef pair<int,P> PP; const ll MOD=998244353; const double PI=acos(-1); template<class Type> struct binary_indexed_tree{ int N; vector<Type> bit; binary_indexed_tree(int n):N(n+1){ bit = vector<Type>(n+1,0); N=n; } void add(int x,Type a){ x++;//1から始めるための補正 //for(int i=x; i<=N; i+=(i&-i)) bit[i] = addition(bit[i],a); while(x<=N){ //bit[x] = addition(bit[x],a); bit[x] =bit[x]+a; x += x&-x; } } Type sum(int x){ x++;//1から始まることに注意 Type ret=0; //for(int i=x; i>0; i-=(i&-i)) ret = addition(ret,bit[i]); while(x>0){ ret = ret+bit[x]; x -= x&-x; } return ret; } //[l,r]の範囲 // rはN-1以下 Type get(int l,int r){ if(r>N) return 0;//配列の外へのアクセス if(l>r) return 0;//本来は l<=r となるのでおかしい if(l==0) return sum(r);//[0,r]//ここでoutなわけか else return (sum(r) - sum(l-1)); } }; int main(){ int N; ll M; cin>>N>>M; vector<int> p(N); for(int i=0;i<N;i++){ cin>>p[i]; p[i]--; } binary_indexed_tree<ll> bit(N+1); ll cnt=0; for(int i=0;i<N;i++){ //[p[i],N-1]の中ですでに登場した数 cnt+=bit.get(p[i],N-1); bit.add(p[i],1); } //cout<<"cnt="<<cnt<<endl; //cnt以上で最初のMの倍数 ll t=((cnt+M-1)/M)*M; //cout<<"t="<<t<<endl; ll d=t-cnt; if(d%2==0){ cout<<t<<endl; }else if((d+M)%2==0){ //t-cntが奇数のとき cout<<t+M<<endl; }else{ cout<<-1<<endl; } }