Submission #6665112


Source Code Expand

Copy
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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 (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
template<int MOD> struct ModInt {
    static const int Mod = MOD; unsigned x; ModInt() : x(0) { }
    ModInt(signed sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
    ModInt(signed long long sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
    int get() const { return (int)x; }
    ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
    ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }
    ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
    ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
    ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
    ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
    ModInt inverse() const { long long a = x, b = MOD, u = 1, v = 0;
        while (b) { long long t = a / b; a -= t * b; std::swap(a, b); u -= t * v; std::swap(u, v); }
        return ModInt(u); }
    bool operator==(ModInt that) const { return x == that.x; }
    bool operator!=(ModInt that) const { return x != that.x; }
    ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; }
};
template<int MOD> ostream& operator<<(ostream& st, const ModInt<MOD> a) { st << a.get(); return st; };
template<int MOD> ModInt<MOD> operator^(ModInt<MOD> a, unsigned long long k) {
    ModInt<MOD> r = 1; while (k) { if (k & 1) r *= a; a *= a; k >>= 1; } return r; }
typedef ModInt<1000000007> mint;
template<class V> struct BIT {
    BIT() {}  // [L, R)
    int NV;vector<V> bit;
    BIT(int n){ init(n); }
    void init(int n) { NV = 1; while (NV < n)NV *= 2; bit.resize(NV); clear(); }
    V operator[](int e) { V s = 0; e++; while (e) s += bit[e - 1], e -= e&-e; return s; }
    void add(int e, V v) { e++; while (e <= NV) bit[e - 1] += v, e += e&-e; }
    int lower_bound(V val) { 
        V tv = 0; int i, ent = 0; for (i = NV - 1; i >= 0; i--)
        if(tv+bit[ent+(1<<i)-1]<=val)tv+=bit[ent+(1<<i)-1],ent += (1 << i);return ent;
    }
    V get(int L, int R) {
        assert(0 <= L); assert(R <= NV); assert(L <= R);
        V res = 0; if(R) res += operator[](R - 1); if (L) res -= operator[](L - 1);return res;
    }
    void clear() { rep(i, 0, NV) bit[i] = 0; }
};
/*---------------------------------------------------------------------------------------------------
            ∧_∧
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i     @hamayanhamayan
    /   \     | |
    /   / ̄ ̄ ̄ ̄/  |
  __(__ニつ/     _/ .| .|____
     \/____/ (u ⊃
---------------------------------------------------------------------------------------------------*/










int N, M, A[201010], B[201010];
int cntA[401010];
BIT<int> cntB(401010);
BIT<mint> lft(401010), rht(401010);
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> M;
	rep(i, 0, N) cin >> A[i];
	rep(i, 0, M) cin >> B[i];

	// compression
	vector<int> dict;
	rep(i, 0, N) dict.push_back(A[i]);
	rep(i, 0, M) dict.push_back(B[i]);
	sort(all(dict));
	dict.erase(unique(all(dict)), dict.end());
	rep(i, 0, N) A[i] = lower_bound(all(dict), A[i]) - dict.begin();
	rep(i, 0, M) B[i] = lower_bound(all(dict), B[i]) - dict.begin();

	rep(i, 0, N) cntA[A[i]]++;
	rep(i, 0, M) cntB.add(B[i], 1);

	rep(i, 0, 401010) rht.add(i, cntB.get(i + 1, 401010) * cntA[i]);

	mint ans = 0;
	rep(p, 0, 401010 - 10) {
		mint lf = cntB.get(0, p);
		mint rh = rht.get(p + 1, 401010);
		ans += lf * rh * cntA[p];
	}
	cout << ans << endl;
}




Submission Info

Submission Time
Task I - school competition 1
User hamayanhamayan
Language C++14 (GCC 5.4.1)
Score 400
Code Size 4660 Byte
Status AC
Exec Time 174 ms
Memory 11248 KB

Judge Result

Set Name Sample Subtask1
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 26
Set Name Test Cases
Sample 01s.txt, 02s.txt, 03s.txt
Subtask1 01s.txt, 02s.txt, 03s.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt
Case Name Status Exec Time Memory
01s.txt AC 42 ms 6400 KB
02s.txt AC 42 ms 6400 KB
03s.txt AC 41 ms 6400 KB
04.txt AC 41 ms 6400 KB
05.txt AC 42 ms 6400 KB
06.txt AC 42 ms 6400 KB
07.txt AC 43 ms 6400 KB
08.txt AC 42 ms 6400 KB
09.txt AC 42 ms 6400 KB
10.txt AC 41 ms 6400 KB
11.txt AC 43 ms 6528 KB
12.txt AC 72 ms 7800 KB
13.txt AC 104 ms 8948 KB
14.txt AC 174 ms 11248 KB
15.txt AC 100 ms 8948 KB
16.txt AC 101 ms 8948 KB
17.txt AC 106 ms 8312 KB
18.txt AC 106 ms 9076 KB
19.txt AC 150 ms 10352 KB
20.txt AC 174 ms 11248 KB
21.txt AC 174 ms 11248 KB
22.txt AC 174 ms 11248 KB
23.txt AC 108 ms 10480 KB
24.txt AC 107 ms 10480 KB
25.txt AC 122 ms 10480 KB
26.txt AC 140 ms 10480 KB