Submission #314113

#	Time	Username	Problem	Language	Result	Execution time	Memory
314113		kimbj0709	Pilot (NOI19_pilot)	C++14	100 / 100	734 ms	83756 KiB

pilot

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 1000050
#define f first
#define s second
int currsum = 0;
vector<int> ufds(maxn);
vector<int> s(maxn,1);
int find(int k){
  if(ufds[k]!=k){
    ufds[k] = find(ufds[k]);
  }
  return ufds[k];
}
void merge(int a,int b){
  int temp1 = find(a);
  int temp2 = find(b);
  currsum -= (s[temp1]*(s[temp1]+1))/2;
  currsum -= (s[temp2]*(s[temp2]+1))/2;
  int tt = s[temp1]+s[temp2];
  currsum += (tt*(tt+1))/2;
  ufds[temp1] = temp2;
  s[temp2] = tt;
  s[temp1] = tt;
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
  int n,q;
  vector<pair<int,int> > height,query;
  vector<int> visited(maxn,0);
  int input;
  cin >> n >> q;
  for(int i=0;i<ufds.size();i++){
    ufds[i] = i;
  }
  for(int i=1;i<=n;i++){
    cin >> input;
    height.push_back({input,i});
  }
  vector<int> ans(q);
  for(int i=0;i<q;i++){
    cin >> input;
    query.push_back({input,i});
  }
  sort(height.begin(),height.end());
  sort(query.begin(),query.end());
  int currpos = 0;
  for(int i=0;i<query.size();i++){
    while(currpos<height.size()&&height[currpos].f<=query[i].f){
      currsum++;
      visited[height[currpos].s] = 1;
      if(visited[height[currpos].s-1]==1){
        merge(height[currpos].s,height[currpos].s-1);
      }
      if(visited[height[currpos].s+1]==1){
        merge(height[currpos].s,height[currpos].s+1);
      }
      currpos++;
    }
    ans[query[i].s] = currsum;
  }
  for(auto k:ans){
    cout << k << "\n";
  }
}

Compilation message (stderr)

pilot.cpp: In function 'int32_t main()':
pilot.cpp:35:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for(int i=0;i<ufds.size();i++){
      |               ~^~~~~~~~~~~~
pilot.cpp:50:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for(int i=0;i<query.size();i++){
      |               ~^~~~~~~~~~~~~
pilot.cpp:51:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     while(currpos<height.size()&&height[currpos].f<=query[i].f){
      |           ~~~~~~~^~~~~~~~~~~~~~

• 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