結果

問題 No.1282 Display Elements
ユーザー yamakeyamake
提出日時 2020-11-06 22:38:23
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 313 ms / 2,000 ms
コード長 2,121 bytes
コンパイル時間 1,047 ms
コンパイル使用メモリ 96,752 KB
実行使用メモリ 21,116 KB
最終ジャッジ日時 2023-09-29 19:16:05
合計ジャッジ時間 3,947 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 2 ms
4,380 KB
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 2 ms
4,380 KB
testcase_15 AC 270 ms
15,976 KB
testcase_16 AC 85 ms
10,120 KB
testcase_17 AC 218 ms
17,744 KB
testcase_18 AC 118 ms
9,748 KB
testcase_19 AC 94 ms
10,384 KB
testcase_20 AC 97 ms
10,356 KB
testcase_21 AC 302 ms
17,176 KB
testcase_22 AC 109 ms
10,432 KB
testcase_23 AC 313 ms
21,116 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>
#include<map>

using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
#define debug(output) cout<<#output<<"= "<<output<<endl

using P=pair<int,int>;
using lint=long long;
using ll=long long;
const lint inf=1e18+7;
const int MOD=1000000007;
//use template macro
void press(vector<long long>& x,vector<lint>& a){
    map<int,int> memo;
    int n=x.size();
    rep(i,n){
        memo[x[i]]+=1;
        memo[a[i]]+=1;
    }
    int cur=0;
    for(auto& val:memo){
        val.second=cur;
        ++cur;
    }
    rep(i,n){
        x[i]=memo[x[i]];
        a[i]=memo[a[i]];
    }
}
class Seg_Tree{
    private:
    int e=0;
    int n;
    vector<int> node;
    public:
    int process(int left,int right){
        if(left==e)return right;
        if(right==e)return left;
        return left+right;
    }
    Seg_Tree(vector<int> v){
        int num=1;
        int size=v.size();
        while(num<size){
            num*=2;
        }
        n=num;
        node.resize(2*num-1,e);
        for(int i=0;i<size;i++)node[i+num-1]=v[i];
        for(int i=n-2;i>=0;i--)node[i]=process(node[i*2+1],node[i*2+2]);
    }
    void update(int x,int val){
        x+=(n-1);
        node[x]+=val;
        while(x>0){
            x=(x-1)/2;
            node[x]=process(node[x*2+1],node[x*2+2]);
        }
    }
    int out(int a,int b,int k=0,int l=0,int r=-1){
        if(r<0)r=n;
        if(a>=r||b<=l)return e;
        if(a<=l&&b>=r)return node[k];
        int vl=out(a,b,k*2+1,l,(l+r)/2);
        int vr=out(a,b,k*2+2,(l+r)/2,r);
        return process(vl,vr);
    }
};
signed main(){
  int n;cin>>n;
  vector<int> a(n),b(n);
  rep(i,n)cin>>a[i];
  rep(i,n)cin>>b[i];
  sort(a.begin(),a.end());
  press(b,a);
  Seg_Tree tree(vector<int>(n+5+n,0));
  lint res=0;
  rep(i,n){
    tree.update(b[i],1);
    res+=tree.out(0,a[i]);
    //debug(res);
  }
  cout<<res<<"\n";
  return 0;
}
0