Submission #894886

#TimeUsernameProblemLanguageResultExecution timeMemory
894886adkjtPilot (NOI19_pilot)C++14
26 / 100
72 ms71980 KiB
#include<bits/stdc++.h> using namespace std; #define f first #define s second vector<int> g[1111111]; set<pair<int,int>> s; int a[1111111]; long long ans[1111111],ind[1111111]; int main() { int n,q,hmx=0; scanf("%d %d",&n,&q); for(int i=1;i<=n;i++) ind[i]=ind[i-1]+i; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); hmx=max(hmx,a[i]); g[a[i]].push_back(i); } //s.insert({0,0}); for(int i=1;i<=hmx;i++) { ans[i]=ans[i-1]; //printf("Y"); for(auto x:g[i]) { //printf("OO"); if(s.empty()){ ans[i]+=1,s.insert({x,x}); continue; } int cnt=1,rch=0,lch=0; auto it=s.lower_bound({x,x}); if(it==s.end()) rch=1; auto itr=--it; it++; pair<int,int> left=*itr,right=*it; /*for(auto p=s.begin();p!=s.end();p++) printf("%d,%d ",(*p).f,(*p).s);*/ //printf("\n%d %d %d %d %d\n%d %d\n",x,left.f,left.s,right.f,right.s,lch,rch); if(!rch&&left.s==x-1&&right.f==x+1) { ans[i]-=ind[left.s-left.f+1]; ans[i]-=ind[right.s-right.f+1]; ans[i]+=ind[right.s-left.f+1]; s.erase(it); s.erase(itr); s.insert({left.f,right.s}); } else if(!rch&&right.f==x+1) { ans[i]-=ind[right.s-right.f+1]; ans[i]+=ind[right.s-x+1]; s.erase(it); s.insert({x,right.s}); } else if(left.s==x-1) { ans[i]-=ind[left.s-left.f+1]; ans[i]+=ind[x-left.f+1]; s.erase(itr); s.insert({left.f,x}); } else ans[i]+=1,s.insert({x,x}); //printf("LL"); } } for(int i=1;i<=q;i++) { int qu; scanf("%d",&qu); if(qu>hmx) qu=hmx; printf("%lld\n",ans[qu]); } /* for(int i=1;i<=hmx;i++) printf("%lld ",ind[i]);*/ return 0; }

Compilation message (stderr)

pilot.cpp: In function 'int main()':
pilot.cpp:33:17: warning: unused variable 'cnt' [-Wunused-variable]
   33 |             int cnt=1,rch=0,lch=0;
      |                 ^~~
pilot.cpp:33:29: warning: unused variable 'lch' [-Wunused-variable]
   33 |             int cnt=1,rch=0,lch=0;
      |                             ^~~
pilot.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     scanf("%d %d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~
pilot.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~
pilot.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         scanf("%d",&qu);
      |         ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...