Submission #1276288

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276288		altern23	Fancy Fence (CEOI20_fancyfence)	C++20	43 / 100	21 ms	5136 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")

const int MAXN = 1e5;
const ll INF = 1e18;
const int MOD = 1e9 + 7;

ll res = 0;
ll H[MAXN + 5], W[MAXN + 5];

ll expo(ll a, ll b){
      ll ans = 1;
      while(b > 0){
            if(b & 1) ans = ans * a % MOD;
            a = a * a % MOD;
            b /= 2;
      }

      return ans;
}

ll inv = expo(2, MOD - 2);

struct DSU{
      ll N;
      vector<ll> par, val;
      DSU(ll _n){
            N = _n;
            par.resize(N + 5), val.resize(N + 5);
            for(int i = 1; i <= N; i++) par[i] = i, val[i] = -1;
      }

      ll find(ll idx){
            return (par[idx] == idx ? idx : par[idx] = find(par[idx]));
      }

      void join(ll a, ll b){
            a = find(a), b = find(b);
            if(a == b) return;
            res -= (val[a] * (val[a] + 1) % MOD * inv % MOD) + MOD;
            res %= MOD;
            res -= (val[b] * (val[b] + 1) % MOD * inv % MOD) + MOD;
            res %= MOD;

            val[a] += val[b];
            val[a] %= MOD;

            res += val[a] * (val[a] + 1) % MOD * inv % MOD;
            res %= MOD;

            par[b] = a;
      }
};

int main(){
      ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
      int tc = 1;	
      // cin >> tc;
      for(;tc--;){
            ll N; cin >> N;
            vector<pii> v;

            for(int i = 1; i <= N; i++){
                  cin >> H[i];
            }

            for(int i = 1; i <= N; i++){
                  cin >> W[i];
                  v.push_back({H[i], i});
            }

            sort(v.begin(), v.end());

            DSU dsu(N);

            ll ans = 0;
            while(true){
                  ll cur = v.back().fi;
                  while(!v.empty() && v.back().fi == cur){
                        res += W[v.back().sec] * (W[v.back().sec] + 1) % MOD * inv % MOD;
                        res %= MOD;

                        dsu.val[v.back().sec] = W[v.back().sec];

                        if(v.back().sec > 1 && dsu.val[dsu.find(v.back().sec - 1)] != -1){
                              dsu.join(v.back().sec, v.back().sec - 1);
                        }
                        if(v.back().sec < N && dsu.val[dsu.find(v.back().sec + 1)] != -1){
                              dsu.join(v.back().sec, v.back().sec + 1);
                        }

                        v.pop_back();
                  }

                  ll nxt;
                  if(!v.empty()) nxt = v.back().fi;
                  else nxt = 0;

                  ll Sn = (cur - nxt) * (2LL * cur - (cur - nxt - 1) + MOD) % MOD * inv % MOD;
                  ans += res * Sn % MOD;
                  ans %= MOD;

                  if(v.empty()) break;
            }

            cout << ans << "\n";
      }
}

/*

*/

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