Submission #654766

#TimeUsernameProblemLanguageResultExecution timeMemory
654766AntekbMatching (CEOI11_mat)C++14
73 / 100
2043 ms65536 KiB
#include<bits/stdc++.h> //#pragma GCC optimize("Ofast") //#pragma GCC optimize("trapv") #define st first #define nd second #define pb push_back #define pp pop_back #define eb emplace_back #define mp(a, b) make_pair(a, b) #define all(x) (x).begin(), (x).end() #define rev(x) reverse(all(x)) #define sor(x) sort(all(x)) #define sz(x) (int)(x).size() #define rsz(x) resize(x) using namespace std; ///~~~~~~~~~~~~~~~~~~~~~~~~~~ template <typename H, typename T> ostream& operator<<(ostream& os, pair<H, T> m){ return os <<"("<< m.st<<", "<<m.nd<<")"; } template <typename H> ostream& operator<<(ostream& os, vector<H> V){ os<<"{"; for(int i=0; i<V.size(); i++){ if(i)os<<" "; os<<V[i]; } os<<"}"; return os; } void debug(){cerr<<"\n";} template <typename H, typename... T> void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);} #define deb(x...) cerr<<#x<<" = ";debug(x); ///~~~~~~~~~~~~~~~~~~~~~~~~~ typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<pii > vii; typedef vector<ll> vl; typedef vector<pll> vll; typedef string str; #define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const int N=1e6+5, INF=1e9+5, mod=1e9+7; int co[N], co2[N], gdzie[N]; int main(){ BOOST; int n, m; cin>>n>>m; vi V(n), V3(n), V2; for(int &i:V3)cin>>i; for(int i=0; i<n; i++){ V[V3[i]-1]=i+1; } V3.clear(); //for(int i:V)cout<<i<<" "; set<int> S, S2; S.insert(0); S2.insert(n+1); gdzie[0]=gdzie[n+1]=-1; for(int i=0; i<n; i++){ gdzie[V[i]]=i; co[i]=gdzie[-*S.upper_bound(-V[i])]; S.insert(-V[i]); //deb(co[i], co2[i]); } S.clear(); for(int i=0; i<n; i++){ co2[i]=gdzie[*S2.upper_bound(V[i])]; S2.insert(V[i]); } S2.clear(); for(int i:V)V2.pb(i); V.clear(); for(int i=0; i<m; i++){ int x; cin>>x; V2.pb(x); } vi ans; int pi=0; vi pref(n); for(int i=2; i<n+m; i++){ while(pi){ if(pi!=n-1 && (co[pi+1]==-1 || V2[i]>V2[i-pi-1+co[pi+1]]) && (co2[pi+1]==-1 || V2[i]<V2[i-pi-1+co2[pi+1]])){ break; } pi=pref[pi]; } if(pi!=n-1 && (co[pi+1]==-1 || V2[i]>V2[i-pi-1+co[pi+1]]) && (co2[pi+1]==-1 || V2[i]<V2[i-pi-1+co2[pi+1]])){ pi++; } //deb(i-n, pi); if(pi==n-1 && i-n>=n-1){ ans.pb(i-n-n+2); } if(i<n)pref[i]=pi; } cout<<ans.size()<<"\n"; for(int i:ans)cout<<i<<" "; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...