Submission #490323

#	Time	Username	Problem	Language	Result	Execution time	Memory
490323		Wayne_Yan	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	138 ms	10980 KiB

fancyfence

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define int long long
typedef int64_t ll;
typedef long double ld;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb emplace_back
#define mp make_pair
#define mt make_tuple
#define pii pair<int,int>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define RF(n) RFi(i,n)
#define RFi(i,n) RFl(i,0,n)
#define RFl(i,l,n) for(int i=n-1;i>=l;i--)
#define all(v) begin(v),end(v)
#define siz(v) (ll(v.size()))
#define get_pos(v,x) (lower_bound(all(v),x)-begin(v))
#define sort_uni(v) sort(begin(v),end(v)),v.erase(unique(begin(v),end(v)),end(v))
#define mem(v,x) memset(v,x,sizeof v)
#define ff first
#define ss second
#define mid ((l+r)>>1)
#define RAN(a,b) uniform_int_distribution<int> (a, b)(rng)

template <typename T> using max_heap = __gnu_pbds::priority_queue<T,less<T> >;
template <typename T> using min_heap = __gnu_pbds::priority_queue<T,greater<T> >;
template <typename T> using rbt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

const int mod = 1e9+7;

signed main(){
  
  int n;
  cin >> n;
  pii section[n+1];
  F(n) cin >> section[i+1].ff;
  F(n) cin >> section[i+1].ss;

  int prefix_w[n+1];
  prefix_w[0] = 0;
  F(n){
    prefix_w[i+1] = prefix_w[i] + section[i+1].ss;
  }

  pii sorting[n];
  F(n){
    sorting[i] = {section[i+1].ff, i+1};
  }

  sort(sorting, sorting + n);

  set<int> processed;
  processed.insert(0);
  processed.insert(n+1);

  int ans = 0;

  F(n){
    // process i;
    pii curr = sorting[i];
    auto it = processed.lower_bound(curr.ss);
    int ub = *it;
    it--;
    int lb = *it;
    ub--;
    lb++;

    int w1,w2,w3;
    w1 = prefix_w[curr.ss-1] - prefix_w[lb-1];
    w2 = section[curr.ss].ss;
    w3 = prefix_w[ub] - prefix_w[curr.ss];

    w1 %= mod;
    w3 %= mod;

    ans +=  ((w1*w2%mod) * (((curr.ff+1) * curr.ff / 2) % mod)) % mod;
    ans %= mod;
    ans +=  ((w3*w2%mod) * (((curr.ff+1) * curr.ff / 2) % mod)) % mod;
    ans %= mod;
    ans +=  ((w3*w1%mod) * (((curr.ff+1) * curr.ff / 2) % mod)) % mod;
    ans %= mod;
    ans +=  ((((w2+1) * w2 / 2) % mod) * (((curr.ff+1) * curr.ff / 2) % mod)) % mod;
    ans %= mod;

    processed.insert(curr.ss);
  }

  printf("%lld", ans);
  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