Submission #1199899

#TimeUsernameProblemLanguageResultExecution timeMemory
1199899midiExam (eJOI20_exam)C++17
100 / 100
189 ms22328 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define vc vector typedef vc<ll> vcll; typedef vc<bool> vcb; #define pr pair typedef pr<ll, ll> prll; typedef set<ll> setll; typedef map<ll,ll> mapll; #define uset unordered_set typedef uset<ll> usetll; #define umap unordered_map typedef umap<ll,ll> umapll; #define f0r(i,a,n) for ((i)=(a); (i)<=(n); (i)++) #define r0f(i,n,a) for ((i)=(n); (i)>=(a); (i)--) #define pb push_back #define ppb pop_back #define pf push_front #define ppf pop_front #define mp make_pair #define fi first #define se second #define sz size #define all(x) (x).begin(), (x).end() #define all0(x, n) (x).begin(), (x).begin()+n #define all1(x, n) (x).begin()+1, (x).begin()+n+1 #define allrev(x) (x).rbegin(), (x).rend() #define in(v, s) ((s).find((v)) != (s).end()) #define GCD(x, y) __gcd(abs((x)), abs((y))) #define INF (LLONG_MAX>>3ll) #define MOD (1'000'000'007ll) #define mxN (100'010ll) #define lgN (17ll) #define sgN (1ll<<17ll) inline void maxa(ll &a, ll b) { if (a<b) a=b; } inline void mina(ll &a, ll b) { if (a>b) a=b; } inline void print (vcll &a, ll n=-1, string name="") { cout << name << ": "; if (n==-1) for (ll x:a) printf("%lli ", x); else { ll i; f0r(i,1,n) printf("%lli ", a[i]); } printf("\n"); } ll n; vcll a(mxN), b(mxN); vc<vcll> arrows0(mxN); vc<vcll> arrows1(mxN); struct ST // range max queries { vcll st; inline ST() { st.resize(sgN*2+10, 0); } ll qry (ll it, ll lt, ll rt, ll l, ll r) { if (rt<=l or r<=lt) return 0; if (l<=lt and rt<=r) return st[it]; ll i2=it*2, mt=(lt+rt)/2; return max(qry(i2,lt,mt,l,r), qry(i2+1,mt,rt,l,r)); } inline ll qry (ll l, ll r) { return qry(1,0,n+1,l,r+1); } inline ll upd (ll it, ll lt, ll rt, ll j, ll x) { if (j<lt or rt<=j) return st[it]; if (lt+1==rt) return st[it] = max(st[it],x); ll i2=it*2, mt=(lt+rt)/2; return st[it] = max(upd(i2,lt,mt,j,x), upd(i2+1,mt,rt,j,x)); } inline void upd (ll j, ll x) { upd(1,0,n+1,j,x); } } stg, dp0, dp1; mapll lasti; inline void bd_arrows() { ll i; f0r(i,1,n) stg.upd(i,a[i]); f0r(i,1,n) { if (in(b[i], lasti) and a[i]!=b[i]) { ll j=lasti[b[i]]; if (stg.qry(j,i) == a[j]) arrows0[i].pb(j); } lasti[a[i]]=i; } lasti.clear(); r0f(i,n,1) { if (in(b[i], lasti) and a[i]!=b[i]) { ll j=lasti[b[i]]; if (stg.qry(i,j) == a[j]) arrows1[j].pb(i); } lasti[a[i]]=i; } f0r(i,1,n) if (a[i]==b[i]) arrows1[i].pb(i); f0r(i,1,n) sort(all(arrows0[i])); f0r(i,1,n) sort(all(arrows1[i])); } inline void doq1 (ll i, ll j) { ll x = dp1.qry(1,j-1) + 1; dp1.upd(j,x); dp0.upd(i,x); } inline void doq0 (ll i, ll j) { ll x = dp0.qry(1,j) + 1; dp0.upd(j,x); dp1.upd(i,x); } inline void bd_dp() { ll i; f0r(i,1,n) { for (ll j:arrows1[i]) doq1(i,j); for (ll j:arrows0[i]) doq0(i,j); } } inline void main2() { scanf("%lli", &n); ll i; f0r(i,1,n) scanf("%lli", &a[i]); f0r(i,1,n) scanf("%lli", &b[i]); bd_arrows(); bd_dp(); printf("%lli\n", max(dp0.qry(1,n), dp1.qry(1,n))); } int main() { // cin.tie(0); cout.tie(0); // ios_base::sync_with_stdio(0); srand(time(0)); // freopen("file.in", "r", stdin); ll t=1; // scanf("%lli", &t); while (t--) main2(); return 0; }

Compilation message (stderr)

exam.cpp: In function 'void main2()':
exam.cpp:148:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |         scanf("%lli", &n);
      |         ~~~~~^~~~~~~~~~~~
exam.cpp:150:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |         f0r(i,1,n) scanf("%lli", &a[i]);
      |                    ~~~~~^~~~~~~~~~~~~~~
exam.cpp:151:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |         f0r(i,1,n) scanf("%lli", &b[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...