Submission #295340

#	Time	Username	Problem	Language	Result	Execution time	Memory
295340		beso123	Pilot (NOI19_pilot)	C++14	100 / 100	964 ms	83548 KiB

pilot

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
const int N=1000006;
int n,a[N],p[N],s[N],Size[N];
int ans=n;
void MS(){
    for(int k=1;k<=n;k++){
        p[k]=k;
        Size[k]=1;
    }
}
int FS(int v){
    if(p[v]==v) return v;
    return p[v]=FS(p[v]);
}
void US(int a,int b){
    a=FS(a);
    b=FS(b);
    if(a!=b){
       Size[a]+=Size[b];
       p[b]=a;
    }
}
bool comp_sort(pii a,pii b){
return a.x<b.x;
}
int Q;
int bo[N];
pii b[N];
int anss[N];
main(){
   scanf("%lld%lld",&n,&Q);
ans=0;
for(int k=1;k<=n;k++){
        int bb;
        scanf("%lld",&bb);
    b[k].x=bb;
    b[k].y=k;
}
sort(b+1,b+n+1,comp_sort);
vector<pii> q;
for(int k=1;k<=Q;k++){
    int x;
    scanf("%lld",&x);
    q.push_back({x,k});
}
MS();
int j=0;
sort(q.begin(),q.end(),comp_sort);
  b[n+1].x=LONG_LONG_MAX;
while(q[j].x<b[1].x && j<Q){
    j++;
}
for(int k=1;k<=n;k++){
    bo[b[k].y]=1;
    int ind=0;
  if(bo[b[k].y-1]==1){
        ans-=((Size[FS(b[k].y-1)])*(Size[FS(b[k].y-1)]+1))/2;
  }
  if(bo[b[k].y+1]==1){
        ans-=(Size[FS(b[k].y+1)]*(Size[FS(b[k].y+1)]+1))/2;
  }
  if(bo[b[k].y-1]==1){
        US(b[k].y,b[k].y-1);
  }
  if(bo[b[k].y+1]==1){
           US(b[k].y,b[k].y+1);
  }
  ans+=(Size[FS(b[k].y)]*(Size[FS(b[k].y)]+1))/2;
    if(b[k].x!=b[k+1].x){
       while(j<Q && q[j].x>=b[k].x&& q[j].x<b[k+1].x){
            anss[q[j].y]=ans;
            j++;
       }
}
}
if(j<Q)
while(j<Q && q[j].x>b[n].x){
     anss[q[j].y]=ans;
    j++;
}
for(int k=1;k<=Q;k++)
    printf("%lld\n",anss[k]);
return 0;
}

Compilation message (stderr)

pilot.cpp:35:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   35 | main(){
      |      ^
pilot.cpp: In function 'int main()':
pilot.cpp:60:9: warning: unused variable 'ind' [-Wunused-variable]
   60 |     int ind=0;
      |         ^~~
pilot.cpp:36:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   36 |    scanf("%lld%lld",&n,&Q);
      |    ~~~~~^~~~~~~~~~~~~~~~~~
pilot.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |         scanf("%lld",&bb);
      |         ~~~~~^~~~~~~~~~~~
pilot.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |     scanf("%lld",&x);
      |     ~~~~~^~~~~~~~~~~

• 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