Submission #1326795

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326795		al95ireyiz	Pilot (NOI19_pilot)	C++20	100 / 100	996 ms	54280 KiB

pilot

#pragma GCC optimize("O3", "fast-math", "unroll-loops", "no-stack-protector")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define len(x) (ll)x.size()
const ll inf = 1e9, infl = 1e18;
const ll MOD = 1e9 + 7;
const ll maxn = 1e6 + 5;
ll n, m, k = 0;

array<ll, 2> a[maxn], b[maxn];
void _() {
  cin >> n >> m;
  for(ll i = 1; i <= n; i ++){
    cin >> a[i][0]; a[i][1] = i;
  }
  for(ll i = 1; i <= m; i ++){
    cin >> b[i][0]; b[i][1] = i;
  }
  sort(a + 1, a + n + 1, greater<array<ll, 2>>());
  sort(b + 1, b + m + 1, greater<array<ll, 2>>());
  set<array<ll, 2>> s;
  ll cv = 0;
  auto add = [&](ll l, ll r) -> void{
    s.insert({l, r});
    cv += (r - l + 1) * (r - l + 2) / 2;
  };
  auto del = [&](ll l, ll r) -> void{
    s.erase({l, r});
    cv -= (r - l + 1) * (r - l + 2) / 2;
  };
  add(1, n);
  for(ll j = 1, i = 1; j <= m; j ++){
    while(a[i][0] > b[j][0]){
      auto it = s.upper_bound({a[i][1], inf});
      it --;
      auto [l, r] = *it;
      del(l, r);
      if(l <= a[i][1] - 1) add(l, a[i][1] - 1);
      if(a[i][1] + 1 <= r) add(a[i][1] + 1, r);
      i ++;
    }
    b[j][0] = cv;
  }
  // for(auto [x, y] : s) cout << x << ' ' << y << '\n';
  sort(b + 1, b + m + 1, [&](auto x, auto y){ return x[1] < y[1]; });
  for(ll i = 1; i <= m; i ++){
    cout << b[i][0] << '\n';
  }
}
signed main() {
  cin.tie(0)->sync_with_stdio(0);
  ll t = 1;
  // cin >> t;
  while(t --) _();
}

• Subtask 1: 3 / 3
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 5 / 5
• Subtask 6: 9 / 9
• Subtask 7: 14 / 14
• Subtask 8: 10 / 10
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11