제출 #1196067

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1196067		loom	Pilot (NOI19_pilot)	C++20	100 / 100	380 ms	69760 KiB

pilot

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 5e18
#define nl '\n'

const int N = 1e6;
int p[N], sz[N];
int ans;

int find(int x){
   return x == p[x] ? x : p[x] = find(p[x]);
}

void unite(int x, int y){
   x = find(x);
   y = find(y);
   if(x == y) return;

   ans += sz[x] * sz[y];

   if(sz[x] < sz[y]) swap(x, y);
   sz[x] += sz[y];
   p[y] = x;
}

inline void solve(){
   int n, q;
   cin>>n>>q;
   int a[n];
   vector<pair<int,int>> arr(n), qry(q);
   for(int i=0; i<n; i++) cin>>a[i], arr[i] = {a[i], i};
   for(int i=0; i<q; i++) cin>>qry[i].first, qry[i].second = i;
   sort(arr.begin(), arr.end());
   sort(qry.begin(), qry.end());

   fill(sz, sz+n, 1);
   iota(p, p+n, 0);

   int fans[q];
   for(int i=0, j=0; i<q; i++){
      auto [qx, qi] = qry[i];

      while(j < n and arr[j].first <= qx){
         auto [x, ix] = arr[j];
         ans++;
         if(ix-1 >= 0 and a[ix-1] <= x) unite(ix-1, ix);
         if(ix+1 < n and a[ix+1] <= x) unite(ix, ix+1);
         j++;
      }

      fans[qi] = ans;
   }

   for(int i=0; i<q; i++) cout<<fans[i]<<nl;
}  

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);cout.tie(NULL);

   int t = 1;
   //cin>>t;
   while(t--) solve();

   return 0;
}

• 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