Submission #476720

#	Time	Username	Problem	Language	Result	Execution time	Memory
476720		pluto_ish	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	77 ms	10072 KiB

fancyfence

#include <bits/stdc++.h>
 
#define pb push_back
#define ff first
#define ss second
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
const ll INF = (ll)1<<62;
const ll MOD = 1e9+7;
const int iINF = 1<<30;
const double PI = 3.14159265359;

ll nC2(ll n){
  if(n < 0) return 0;
  return (n*(n-1)/2) % MOD;
}  

void solve(){
  int n;
  cin >> n;

  vector<ll> h(n), w(n);
  for(ll& x : h) cin >> x;
  for(ll& x : w) cin >> x;

  map<ll, ll> mp;
  ll s = 0, ans = 0;
  for(int i=0;i<n;i++){
    auto it = mp.upper_bound(h[i]);
    for(;it!=mp.end();){
      s = (s - nC2(it->ff+1)*it->ss + MOD)%MOD;
      s = (s + nC2(h[i]+1)*it->ss + MOD)%MOD;

      mp[h[i]] = (mp[h[i]] + it->ss)%MOD;
      it = mp.erase(it);
    }  
    
    ans = (ans + nC2(h[i]+1)*nC2(w[i]+1)%MOD + s*w[i]%MOD)%MOD;
    s = (s + nC2(h[i]+1)*w[i]%MOD)%MOD;
    mp[h[i]] = (mp[h[i]] + w[i])%MOD;
  }  
  cout << ans << "\n";
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int t = 1;
  //cin >> t;
  while(t--){
    solve();
  }  
  
  return 0;
}  

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 27 / 27