Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cstdlib>
- #include <iostream>
- #include <fstream>
- #include <sstream>
- #include <set>
- #include <map>
- #include <vector>
- #include <list>
- #include <algorithm>
- #include <cstring>
- #include <cmath>
- #include <string>
- #include <queue>
- #include <bitset> //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
- #include <cassert>
- #include <iomanip> //do setprecision
- #include <ctime>
- #include <complex>
- using namespace std;
- #define FOR(i,b,e) for(int i=(b);i<(e);++i)
- #define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
- #define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
- #define REP(x, n) for(int x = 0; x < (n); ++x)
- #define ST first
- #define ND second
- #define PB push_back
- #define MP make_pair
- #define LL long long
- #define ULL unsigned LL
- #define LD long double
- const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
- #define MR 1000010
- int a[MR], b[MR], wa[MR], wb[MR]; //hieroglify i wystapienia hieroglifow
- int main()
- {
- memset(wa,-1,sizeof(wa));
- memset(wb,-1,sizeof(wb));
- int la, lb;
- scanf("%d%d", &la, &lb);
- REP(i,la)
- {
- scanf("%d", &a[i]);
- wa[a[i]] = i;
- }
- REP(i,lb)
- {
- scanf("%d", &b[i]);
- wb[b[i]] = i;
- }
- if(la == 1)
- {
- printf("%d\n", wb[a[0]] == -1 ? 0 : 1);
- return 0;
- }
- if(lb == 1)
- {
- printf("%d\n", wa[b[0]] == -1 ? 0 : 1);
- return 0;
- }
- int res = 0;
- int end = -1, x = wb[a[0]], y = wb[a[0]];
- bool cond = 0;
- REP(i,la)
- {
- if(wb[a[i]] == -1) break; //nie ma hieroglifu w b
- if(wb[a[i]] < x && !cond) //od tego momentu trzeba wprowadzic warunek
- {
- cond = 1;
- y = wb[a[i]];
- end = i; //przesun koniec
- }
- if(!cond)
- {
- if(wb[a[i]] < y)
- break;
- y = wb[a[i]]; //indeksy dalej rosna
- end = i;
- }
- else if(cond) //spr, czy indeks trafia tam gdzie trzeba
- {
- if(wb[a[i]] < y || wb[a[i]] > x) //nie wystepuje jako podciag
- break;
- y = wb[a[i]];
- end = i; //przesun koniec
- }
- }
- if(end != -1) res = end+1;
- if(res == la)
- {
- printf("%d\n", la);
- return 0;
- }
- //przesuwaj poczatek o 1 i probuj poszerzac koniec
- bool endza = 0;
- FOR(i,1,la)
- {
- if(wb[a[i]] == -1) continue; //nie ma poczatku w b, od razu mozemy go pominac i sprawdzic nastepny
- if(!endza && end < i) end = i;
- if(wb[a[i]] < x) cond = 0; //nie ma warunku
- x = wb[a[i]];
- while(true)
- {
- if(endza && end == i-1) break; //mamy cale a
- if(wb[a[(end+1)%la]] == -1) break; //nie ma kolejnego hieroglifu w b -> nie da sie poszerzyc konca
- if(wb[a[(end+1)%la]] < x && !cond) //od tego momentu trzeba wprowadzic warunek
- {
- cond = 1;
- y = wb[a[(end+1)%la]];
- if(end == la-1) endza = 1; //end sie przekrecil
- end = (end+1)%la; //przesun koniec
- }
- if(!cond)
- {
- if(wb[a[(end+1)%la]] < y)
- break;
- y = wb[a[(end+1)%la]]; //indeksy rosna dalej
- if(end == la-1) endza = 1; //end sie przekrecil
- end = (end+1)%la; //przesun koniec
- }
- else //spr czy indeks trafil tam gdzie trzeba
- {
- if(wb[a[(end+1)%la]] < y || wb[a[(end+1)%la]] > x)
- break;
- y = wb[a[(end+1)%la]]; //indeksy rosna dalej
- if(end == la-1) endza = 1; //end sie przekrecil
- end = (end+1)%la;
- }
- }
- //spr nowa dlugosc
- if(!endza) res = max(res, end-i+1);
- else res = max(res, end+1+la-i);
- }
- printf("%d\n", res);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement