結果
問題 | No.742 にゃんにゃんにゃん 猫の挨拶 |
ユーザー |
![]() |
提出日時 | 2020-03-10 16:12:08 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 26 ms / 2,500 ms |
コード長 | 8,545 bytes |
コンパイル時間 | 2,053 ms |
コンパイル使用メモリ | 188,964 KB |
実行使用メモリ | 36,096 KB |
最終ジャッジ日時 | 2024-11-15 23:23:50 |
合計ジャッジ時間 | 2,895 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
#include "bits/stdc++.h"#include <random>#include <algorithm>#include <unordered_set>#define rep(i,n) for(int i = 0; i < n; i++)typedef long long ll;typedef unsigned long long ull;using namespace std;#define vll vector<vector<long long>>#define vl vector<long long>#define vi vector<int>#define vii vector<vector<int>>#define pb push_back#define pf push_front#define ld long double#define Sort(a) sort(a.begin(),a.end())#define cSort(a,cmp) sort(a.begin(),a.end(),cmp)#define reSort(a) sort(a.rbegin(), a.rend())static const ll llMAX = numeric_limits<long long>::max();static const int intMAX = numeric_limits<int>::max();static const ll llMIN = numeric_limits<long long>::min();static const int intMIN = numeric_limits<int>::min();static const ll d_5 = 100000;static const ll d9_7 = 1000000007;static const ll d_9 = 1000000000;static const double PI=3.14159265358979323846;template<class T>void Printvector(std::vector<T> a){int size = a.size();rep(i,size){cout<<a[i]<<" ";}cout<<endl;}template<class T>void Printvector(std::vector<std::vector<T>> a){int size = a.size();rep(i,size){int size2=a[i].size();rep(j,size2){cout<<a[i][j]<<" ";}cout<<endl;}cout<<endl;}template<class T>vector<T> getaccum(vector<T> a){int size=a.size();vector<T> ans(size);ans[0]=a[0];for(int i=0;i<size-1;i++){ans[i+1]=ans[i]+a[i+1];//ans[i+1]%=d9_7;}return ans;}template<class T>vector<vector<T>> getaccum2D(vector<vector<T>> a){int sizey=a.size();int sizex=a[0].size();vector<vector<T>> ans(sizey,vector<T>(sizex,0));//ans=a;ans[0][0]=a[0][0];for(int i=1;i<sizex;i++){ans[0][i]=ans[0][i-1]+a[0][i];}for(int i=1;i<sizex;i++){ans[i][0]=ans[i-1][0]+a[i][0];}for (int i = 0; i < sizey-1; i++)for (int j = 0; j < sizex-1; j++)ans[i+1][j+1] = ans[i][j+1] + ans[i+1][j] - ans[i][j] + a[i+1][j+1];return ans;}ll getaccumnum(vector<ll> accum,int l,int r){//閉区間[l,r]の総和if(l==0){return accum[r];}else{return accum[r]-accum[l-1];}}template<class T>T getaccumnum2D(vector<vector<T>>& accum,int x1,int y1,int x2,int y2){//2の方が右下、閉区間T ans=accum[y2][x2];if(x1==0 && y1==0){;}else if(x1>0 && y1==0){ans-=accum[y2][x1-1];}else if(x1==0 && y1>0){ans-=accum[y1-1][x2];}else{ans-=accum[y1-1][x2];ans-=accum[y2][x1-1];ans+=accum[y1-1][x1-1];}return ans;}ll digitpower(ll a,ll b){//aのb乗を計算if(b==1){return a;}else if(b==0){return 1;}int mode=0;if(b%2==1){ll tmp = digitpower(a,(b-1)/2);if(mode==1){tmp%=d9_7;}tmp*=tmp;if(mode==1){tmp%=d9_7;}tmp*=a;if(mode==1){return tmp%d9_7;}else{return tmp;}}else{ll tmp = digitpower(a,(b)/2);if(mode==1){tmp%=d9_7;}tmp*=tmp;if(mode==1){tmp%=d9_7;}if(mode==1){return tmp%d9_7;}else{return tmp;}}}vl facs(2000010,-1);ll Factrial(ll num){if(facs[num]!=-1){return facs[num];}if(num==1||num<=0){return 1;}else if(num<0){printf("ERROR_minus\n");return 0;}else{facs[num]=(num*Factrial(num-1))%d9_7;return facs[num];}}long long modinv(long long a, long long m) {//modの逆元long long b = m, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}u %= m;if (u < 0) u += m;return u;}vl invs(2000010,-1);ll linercomb(ll n,ll k, ll mod){//n,kの線形時間で求めるif(n<k)return 0;if(n<0)return 0;if(k==0 || k==n)return 1;ll ans=Factrial(n);if(invs[k]==-1){invs[k]=modinv(Factrial(k),mod);}ans*=invs[k];ans%=d9_7;ll k1=Factrial(n-k);k1%=mod;ans*=modinv(k1,mod);ans%=mod;return ans;}unordered_map<ll,ll> prime_factor(int64_t n) {unordered_map<ll,ll> ret;for(int64_t i = 2; i * i <= n; i++) {while(n % i == 0) {ret[i]++;n /= i;}}if(n != 1) ret[n] = 1;return ret;}struct datas{ll p;ll q;};/*bool cmp(const datas &a, const datas &b){return a.num < b.num;}*/template<class T>T gcd(T a,T b){if(a==0){return b;}else if(b==0){return a;}while(1) {if(a < b) swap(a, b);if(!b) break;a %= b;}return a;}int LCS(string s,string t) {int n=s.size();int m=t.size();vector<vector<int>> dp=vector<vector<int>>(n+1,vector<int>(m+1,0));for (int i=0; i<n; ++i) {for (int j=0; j<m; ++j) {if (s[i] == t[j]) {dp[i+1][j+1] = dp[i][j] + 1;}else {dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);}}}return dp[n][m];}//素数列挙#define P 100000vl primes;vl primenum(P+1);vector<bool> bprime(P+200);ll searchprime(ll max){//発見した素因数の個数を返す//max+=180;bprime[1]=false;// cout<<"rrr"<<endl;;//cout<<max<<" "<<bprime.size()<<endl;for(ll i=2;i<=max;i++){bprime[i]=true;}//// cout<<"r";ll nowprimes=1;primes.pb(2);for(ll i=4;i<max;i+=2){bprime[i]=false;}// cout<<"e";for(ll i=3;i<=max;i+=2){if(bprime[i]==true){//primes[nowprimes]=i;primes.pb(i);nowprimes++;for(ll j=2;i*j<=max;j++){bprime[i*j]=false;}}}return nowprimes;}class Inversion_number{//Segment Treeprivate:int n=-1;bool calced=false;vector<int> vec;vector<int> locs;vector<int> invnum;class SegmentTree{public:int n;vector<int> nodes;//constructorSegmentTree(int size,int init){initialize(size,init);}SegmentTree(){;}//関数を定義(minなのかmaxなのかとか)int thisoperator(int a, int b){return a+b;}void update(int x,int a){//xがindexx+=n-1;nodes[x]+=a;while(x>0){x=(x-1)/2;nodes[x]=thisoperator(nodes[2*x+1],nodes[2*x+2]);}}void initialize(int inputn,int init){int k=0;while(inputn>(1<<k)){k++;}n=(1<<k);nodes=vector<int> ((1<<k)*2-1,init);}int sec_get(int reql,int reqr,int nowindex=0,int nowl=0,int nowr=-1){// 最初に呼び出されたときの対象区間は [0, n)//reqrは開区間であることに注意if(nowr < 0) nowr = n;// 要求区間と対象区間が交わらない -> 適当に返すif(nowr <= reql || reqr <= nowl) return 0;// 要求区間が対象区間を完全に被覆 -> 対象区間を答えの計算に使うif(reql <= nowl && nowr <= reqr) return nodes[nowindex];// 要求区間が対象区間の一部を被覆 -> 子について探索を行う// 左側の子を vl ・ 右側の子を vr としている// 新しい対象区間は、現在の対象区間を半分に割ったものint val1 = sec_get(reql, reqr, 2*nowindex+1, nowl, (nowl+nowr)/2);int val2 = sec_get(reql, reqr, 2*nowindex+2, (nowl+nowr)/2, nowr);return thisoperator(val1, val2);}void Printn(){cout<<"Printvector"<<endl;rep(i,n){cout<<nodes[i+n-1]<<" ";}cout<<endl;}};SegmentTree seg;public:Inversion_number(vector<int> invec){//constructorvec=invec;n=invec.size();seg.initialize(n,0);invnum=vector<int>(n,0);locs=vector<int>(n,-1);for(int i=0;i<n;i++){locs[vec[i]]=i;}}void calc(){if(n==-1){cout<<"unconstructed"<<endl;return;}for(int i=0;i<n;i++){int num=seg.sec_get(0,vec[i]+1);invnum[i]=i-num;seg.update(vec[i],1);}calced=true;}int getinvnum(int index){if(!calced){cout<<"not calced"<<endl;return -1;}return invnum[index];}};int main(void){ll n;cin>>n;vi m(n);rep(i,n){cin>>m[i];m[i]--;}Inversion_number inv(m);inv.calc();int ans=0;rep(i,n){ans+=inv.getinvnum(i);}cout<<ans<<endl;return 0;}//<<std::setprecision(30)//重複削除/* std::sort(vec.begin(), vec.end());vec.erase(std::unique(vec.begin(), vec.end()), vec.end());*/