結果

問題 No.1282 Display Elements
ユーザー kkktymkkktym
提出日時 2020-11-07 00:15:47
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 228 ms / 2,000 ms
コード長 4,331 bytes
コンパイル時間 1,324 ms
コンパイル使用メモリ 119,616 KB
実行使用メモリ 18,784 KB
最終ジャッジ日時 2023-09-29 19:49:32
合計ジャッジ時間 3,687 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 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,380 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 1 ms
4,376 KB
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 3 ms
4,376 KB
testcase_15 AC 203 ms
17,916 KB
testcase_16 AC 73 ms
9,352 KB
testcase_17 AC 169 ms
15,940 KB
testcase_18 AC 95 ms
10,720 KB
testcase_19 AC 93 ms
9,540 KB
testcase_20 AC 91 ms
9,548 KB
testcase_21 AC 225 ms
18,732 KB
testcase_22 AC 106 ms
9,852 KB
testcase_23 AC 228 ms
18,784 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <limits>
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }
template<class T> inline int  sz(T &a) { return a.size(); }
using ll = long long; using ld = long double;
using pi = pair<int,int>; using pl = pair<ll,ll>;
using vi = vector<int>; using vvi = vector<vi>;
using vl = vector<ll>; using vvl = vector<vl>;
const int inf = numeric_limits<int>::max();
const ll infll = numeric_limits<ll>::max();
// 一次元座圧.
// 同じ値は同じ値に圧縮される
template <typename T>
class Compress{
public:
  vector<T> a; // 元の配列
  vector<int> data; // 座圧後の配列
  map<T, int> mp; // key->元の配列の値, val->座圧後の値

  void add(T val) {
    a.emplace_back(val);
  }

  void build() {
    vector<T> vals = a;

    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    rep(i,sz(a)) {
      int id = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin();
      // id + 1にすれば1-indexedになる
      mp[a[i]] = id;
      data.push_back(id);
    }
  }

  int a2data(T val) {
    return mp.lower_bound(val)->second;
  }

  void test() {
    vector<T> v = {3, 3, 1, 6, 1};
    for(auto val: v) add(val);
    build();

    for(auto val: data) cout << val << " ";
    cout << "\n";
    // 1 1 0 2 0

    cout << a2data(2) << "\n";
    // 1
  }

};

//----------------------------
// 抽象化セグ木
// 二項演算と単位元を渡して使ってね
///****例****************************
//  auto f = [&](int a,int b){ return a+b;}; // 二項演算:和
//  int id = 0; //単位元:0
//  SegTree<decltype(f),int> seg(f,id);
//************************************
//----------------------------

template <typename F,typename T>
struct SegTree{
  // 二項演算merge,単位元identify
  T identity;
  F merge; 
  int size;
  vector<T> dat;
  
  // 二項演算fと単位元idを渡して宣言する
  SegTree(F f,T id):merge(f),identity(id){}

  // データの要素の数nを渡して初期化、sizeはnより大きい2の冪乗
  void init(int n){
    size = 1;
    while(size<=n) size *= 2;
    dat.resize(size*2-1,identity);
  }

  // 配列を渡して0(n)で初期化
  void build(vector<T> vec){
    rep(i,vec.size()) dat[size-1+i] = vec[i];
    dfs(0);
  }
  
  T dfs(int k){
    if(k>=size-1) return dat[k];
    else return dat[k] = merge(dfs(2*k+1),dfs(2*k+2));
  }

  // index kの要素をaに変更
  void update(int k,T a){
    k += size - 1;
    dat[k] = a;
    while(k > 0){
      k = (k-1)/2;
      dat[k] = merge(dat[2*k+1],dat[2*k+2]);
    }
  }
  
  // index kの要素にaを加算
  void add(int k,T a){
    k += size - 1;
    dat[k] += a;
    while(k > 0){
      k = (k-1)/2;
      dat[k] = merge(dat[2*k+1],dat[2*k+2]);
    }
  }

  // 区間[a,b)に対するクエリに答える。(k,l,r)=(0,0,size)
  T query(int a,int b,int k,int l,int r){
    if(r<=a||b<=l) return identity;
    
    if(a<=l&&r<=b) return dat[k]; 
    else return merge(query(a,b,2*k+1,l,(l+r)/2),query(a,b,2*k+2,(l+r)/2,r));
  }

  T query(int a,int b){
    return query(a, b, 0, 0, size);
  }

  // デバッグ用
  void show(){
    int index = 0;
    int num = 1;
    while(index<size){
      rep(i,num){
	if(dat[i+index]==identity) cout << "e ";
	else cout << dat[i+index] << " ";
      }
      cout << "\n";
      num *= 2;
      index = index*2+1;
    }
  }
  
  
};


int main()
{
  int n; cin >> n;
  vi a(n),b(n);
  rep(i,n) cin >> a[i];
  rep(i,n) cin >> b[i];
  sort(a.begin(), a.end());
  
  Compress<int> cp;
  rep(i,n) cp.add(a[i]);
  rep(i,n) cp.add(b[i]);
  cp.build();
  rep(i,n) a[i] = cp.data[i];
  rep(i,n) b[i] = cp.data[i+n];

  auto f = [&](ll a,ll b){ return a+b;}; // 二項演算:和
  ll id = 0; //単位元:0
  SegTree<decltype(f),ll> seg(f,id);  
  seg.init(2*n);

  ll sum = 0;
  rep(i,n) {
    seg.add(b[i], 1);
    sum += seg.query(0, a[i]);
  }

  cout << sum << "\n";
  
  return 0;
}
0