Submission #463565

#TimeUsernameProblemLanguageResultExecution timeMemory
463565KerimExam (eJOI20_exam)C++17
100 / 100
249 ms15068 KiB
#include "bits/stdc++.h" #define MAXN 200009 #define INF 1000000007 #define mp(x,y) make_pair(x,y) #define all(v) v.begin(),v.end() #define pb(x) push_back(x) #define wr cout<<"----------------"<<endl; #define ppb() pop_back() #define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++) #define ff first #define ss second #define my_little_dodge 46 #define debug(x) cerr<< #x <<" = "<< x<<endl; using namespace std; typedef long long ll; typedef pair<int,int> PII; template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;} template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;} int a[MAXN],b[MAXN],n,c,ans; map<int,int>pm; vector<int>adj[MAXN]; int F[MAXN],l[MAXN],r[MAXN]; void upd(int x,int val){ for(;x<MAXN;x+=x&(-x)) umax(F[x],val); } int tap(int x){ int res=0; for(;x;x-=x&(-x)) umax(res,F[x]); return res; } bool subtask2(){ for(int i=1;i<=n;i++) if(b[i]!=b[1]) return 0; return 1; } multiset<int>s; int main(){ //~ freopen("file.in", "r", stdin); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",a+i),pm[a[i]]=1; for(int i=1;i<=n;i++) scanf("%d",b+i),pm[b[i]]=1; a[0]=a[n+1]=INF; if(subtask2()){ int ans=0; for(int i=1;i<=n+1;i++){ if(a[i]>b[1]){ if(s.count(b[1])) ans+=s.size(); s.clear(); } else s.insert(a[i]); } printf("%d\n",ans); return 0; } tr(it,pm)it->ss=++c; stack<int>st; st.push(0); for(int i=1;i<=n;i++){ while(!st.empty() and a[st.top()]<a[i])st.pop(); l[i]=st.top(); st.push(i); } while(!st.empty())st.pop(); st.push(n+1); for(int i=n;i>=1;i--){ while(!st.empty() and a[st.top()]<a[i])st.pop(); r[i]=st.top(); st.push(i); } for(int i=1;i<=n;i++)adj[pm[a[i]]].pb(i); for(int i=1;i<=n;i++){ vector<int>&v=adj[pm[b[i]]]; if(v.empty())continue; for(int ind=v.size()-1;ind>=0;ind--){ int j=v[ind]; if(i<=l[j] or r[j]<=i)continue; int dp=tap(j)+1; umax(ans,dp); upd(j,dp); } } printf("%d\n",ans); return 0; }

Compilation message (stderr)

exam.cpp: In function 'int main()':
exam.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
exam.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   scanf("%d",a+i),pm[a[i]]=1;
      |   ~~~~~^~~~~~~~~~
exam.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |   scanf("%d",b+i),pm[b[i]]=1;
      |   ~~~~~^~~~~~~~~~
#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...