Submission #572438

#	Time	Username	Problem	Language	Result	Execution time	Memory
572438		PiejanVDC	Pilot (NOI19_pilot)	C++17	89 / 100	1091 ms	67688 KiB

pilot

#include <bits/stdc++.h>
using namespace std;

vector<int>par((int)1e6+5);
vector<long long>sz((int)1e6+5);

int UF(int u) {
  if(par[u] == u) return u;
  return par[u] = UF(par[u]);
}

signed main() {
  int n,q; cin>>n>>q;
  vector<int>v(n);
  for(int i = 0 ; i < n ; i++)
    par[i] = i, sz[i] = 1;
  vector<vector<int>>p((int)1e6+1);
  int X = 0;
  for(auto &z : v) {
    cin>>z;
    p[z].push_back(X);
    X++;
  }
  auto f = [&] (long long X) -> long long {
    return (X * (X+1))/2;
  };
  vector<long long>Q((int)1e6+5);
  long long ans = 0;
  for(int i = 1 ; i <= (int)1e6 ; i++) {
    for(auto z : p[i]) {
      if(z != 0 && UF(z-1) != UF(z) && v[z-1] <= i) {
        int A = UF(z-1), B = UF(z);
        ans -= f(sz[A]);
        ans += f(sz[A] + sz[B]);
        par[B] = A;
        sz[A] += sz[B];
        sz[B] = 0;
      } else ans++;
      if(z != n-1 && UF(z) != UF(z+1) && v[z+1] < i) {
        int A = UF(z), B = UF(z+1);
        ans -= f(sz[A]) + f(sz[B]);
        ans += f(sz[A] + sz[B]);
        if(sz[A] < sz[B]) {
          par[A] = B;
          sz[B] += sz[A];
          sz[A] = 0;
        } else {
          par[B] = A;
          sz[A] += sz[B];
          sz[B] = 0;
        }
      }
    }
    Q[i] = ans;
  }
  while(q--) {
    int h; cin>>h;
    cout << Q[h] << '\n';
  }
}

• 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: 0 / 11