Submission #893389

#TimeUsernameProblemLanguageResultExecution timeMemory
893389WarinchaiPilot (NOI19_pilot)C++14
100 / 100
306 ms106548 KiB
#include<bits/stdc++.h> #define int long long using namespace std; int n,q; int ar[1000005]; int asum[1000005]; int ssum[1000005]; int rsum[1000005]; vector<int>v; struct node{ int val; int sz; node *l; node *r; node(int x=0){ val=x; l=NULL; r=NULL; sz=0; } }; node *rt=NULL; vector<int>qr; stack<node*>s; void dfs(node *u){ u->sz=1; if(u->l){ dfs(u->l); u->sz+=u->l->sz; } if(u->r){ dfs(u->r); u->sz+=u->r->sz; } //cerr<<u->val<<" "<<u->sz<<"\n"; } void dfs2(node *u,int pn=0){ asum[u->val]+=(u->sz)*((u->sz)+1)/2; ssum[pn-1]+=(u->sz)*((u->sz)+1)/2; if(u->l)dfs2(u->l,u->val); if(u->r)dfs2(u->r,u->val); } int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin>>n>>q; for(int i=1;i<=n;i++){ cin>>ar[i]; } for(int i=0;i<q;i++){ int a;cin>>a; qr.push_back(a); } //sort(qr.begin(),qr.end(),greater<pair<int,int> >()); for(int i=1;i<=n;i++){ int x=ar[i]; node *p=NULL; while(!s.empty()&&s.top()->val<x){ p=s.top(); s.pop(); } if(s.empty()){ rt=new node(x); rt->l=p; s.push(rt); }else{ s.top()->r=new node(x); s.top()->r->l=p; s.push(s.top()->r); } } dfs(rt); dfs2(rt,1e6+2); long long sum=0; //cerr<<endl; for(int i=0;i<=1e6;i++){ sum+=asum[i]; rsum[i]=sum; sum-=ssum[i]; //cerr<<"i:"<<i<<" "<<asum[i]<<" "<<ssum[i]<<"\n"; } for(auto x:qr)cout<<rsum[x]<<"\n"; }
#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...