Submission #36148

#TimeUsernameProblemLanguageResultExecution timeMemory
36148KanvieMoney (IZhO17_money)C++14
100 / 100
413 ms6080 KiB
#include<bits/stdc++.h> using namespace std; int f[1000001]={0},n,ans=0,trc=0,trc_M,x; void update(int pos,int value) { for (int i=pos; i<=1000000; i+=(i&(-i)))f[i]+=value; } int get(int pos) { int r=0; for (int i=pos; i>=1; i-=(i&(-i)))r+=f[i]; return r; } int gets(int ll, int rr) { return get(rr)-get(ll-1); } int main() { ios_base::sync_with_stdio(false);cin.tie(0); stack<int>q; memset(f,0,sizeof(f)); scanf("%d",&n); while(n--) { scanf("%d",&x); if(ans==0) { q.push(x); ans++; trc=x; trc_M=x; continue; } if(x<trc||(trc_M+1<x&&gets(trc_M+1,x-1)>0)) { ans++; trc=x; trc_M=x; while(!q.empty()) { update(q.top(),1); q.pop(); } q.push(x); continue; } trc=x; q.push(x); } printf("%d",ans); }

Compilation message (stderr)

money.cpp: In function 'int main()':
money.cpp:23:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
money.cpp:26:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
                       ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...