Submission #1156189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156189		adiyer	Flooding Wall (BOI24_wall)	C++20	0 / 100	5092 ms	23968 KiB

Main

#pragma optimize ("g",on)
#pragma GCC optimize("inline")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("03")

#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define len(s) (ll) s.size()
#define pb push_back
#define F first 
#define S second 

using namespace std;

typedef long long ll;

const int N = 1e6 + 3; 
const int MAX = 2e4 + 11;
const int P = 31;
const int mod = 1e9 + 7;
const ll inf = 1e18;

ll n, sz, res;
ll a[N], b[N], val[N], t[N], pw[N];

vector < ll > comp;

map < ll, ll > mp;

signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> n, pw[0] = 1;
  for(ll i = 1; i <= n; i++) cin >> a[i], comp.pb(a[i]);
  for(ll i = 1; i <= n; i++) cin >> b[i], comp.pb(b[i]);
  for(ll i = 1; i <= n; i++) pw[i] = (pw[i - 1] * 2) % mod;
  sort(all(comp));
  // for(ll i = 0; i < len(comp); i++)
  //   if(i == 0 || comp[i] != comp[i - 1])
  //     mp[comp[i]] = ++sz, val[sz] = comp[i],
  reverse(all(comp));
  for(ll x = 0; x < len(comp); x++){
    if(x && comp[x] == comp[x - 1]) continue;
    ll p = comp[x];
    for(ll i = 1; i <= n; i++){
      t[i] = 0;
      if(a[i] >= p) t[i]++;
      if(b[i] >= p) t[i]++;
    }
    for(ll i = 1, cur; i <= n; i++){
      cur = ((i * t[i]) % mod * pw[i - 1]) % mod;
      for(ll j = i + 1; j <= n; j++) cur *= (2 - t[j]), cur %= mod;
      res += cur;
      res %= mod, res += mod, res %= mod;
      cur = (((i - 1) * t[i]) % mod * pw[n - i]) % mod;
      for(ll j = 1; j <= i - 1; j++) cur *= (2 - t[j]), cur %= mod;
      res -= cur;
      res %= mod, res += mod, res %= mod;
    }
  }
  for(ll i = 1; i <= n; i++){
    res -= pw[n - 1] * (a[i] + b[i]) % mod;
    res %= mod, res += mod, res %= mod;
  }
  cout << res;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 17
• Subtask 3: 0 / 19
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 30