Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- weak weak we ak we akwea weak we
- weak weak we ak weak weak we ak we
- weakweak we ak wea ak we akwe
- wea we ak we ak we akwe
- wea we ak we ak we akwe
- wea eak weak we ak we ak we
- wea wea ak we ak weak we
- we
- we ak wea ak weak we
- we ak wea weak wea eak we
- we ak we ak wea wea we we
- weak we ak we we we we
- we we ak we we we we
- we wea weak wea wea weak weak
- weak wea akw weak weak
- */
- using namespace std;
- #include <vector>
- #include <queue>
- #include <algorithm>
- #include <cmath>
- #include <utility>
- #include <bitset>
- #include <set>
- #include <string>
- #include <stack>
- #include <iomanip>
- #include <map>
- #include <memory.h>
- #include <deque>
- typedef long long LL;
- typedef pair<int,int> pii;
- typedef pair<LL,LL> pll;
- typedef vector<int> vi;
- typedef vector<LL> vl;
- typedef vector<vector<int>> vvi;
- typedef vector<vector<LL>> vvl;
- #define pb push_back
- #define F first
- #define S second
- #define mid (LB+RB+1)/2
- #define mkp make_pair
- //iterators
- #define iter(x) x.begin(),x.end()
- #define aiter(a,n) a,a+n
- //loops
- #define REP(n) for (int ___=n;___--;)
- #define REP0(i,n) for (int i=0;i<n;++i)
- #define REP1(i,n) for (int i=1;i<=n;++i)
- #define FOR(i,b,l,k) for (int i=b;i!=l;i+=k)
- #define MEM(e,val) memset (e,val,sizeof(e))
- #define FE(i,v) for (auto i:v)
- /*
- yungyao so weeeeeeeeeeeeeeeeeeeeeeeeeeak
- 8e7 so dian
- FHVirus so dian
- youou so dian
- KYW so dian
- hubert so dian
- jass so dian
- tingyu so dian
- panda so dian
- */
- //IO
- #include <cstdio>
- #include <iostream>
- #include <fstream> //mainly for USACO, sometimes for benjidabiao
- #define theyRSOOOOOOOOODIAN ios_base::sync_with_stdio(false),cin.tie(0);
- //testing some stuff, still under construction
- //a lot more useful while debug
- inline void print(vector <int> v){
- for (auto i:v)
- cout << i << ' ';
- cout << '\n';
- }
- inline void print(vector <int> v,char sep,char end){
- for (auto i:v)
- cout << i << sep;
- cout << end;
- }
- //pbds
- /*
- #include <ext/pb_ds/tree_policy.hpp>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/priority_queue.hpp>
- using namespace __gnu_pbds;
- */
- //constants
- #include <climits>
- const int maxn = 1e5+100,mod = 1e9+7;
- //workspace
- //pow
- inline long long pow_(long long n,long long k){
- long long val = 1;
- for (;k;k>>=1){
- if (k & 1)
- val = val * n % mod;
- n = n*n % mod;
- }
- return val;
- }
- LL pow2[maxn],pre[maxn];
- bool arr[maxn];
- bool isSame(int l1,int r1,int l2,int r2){
- int const len = r1 - l1 + 1;
- return (pre[r1] - (pre[l1-1] * pow2[len] % mod) + mod) % mod ==
- (pre[r2] - (pre[l2-1] * pow2[len] % mod) + mod) % mod;
- }
- inline void solve(){
- int n,q;
- cin >> n >> q;
- REP1(i,n){
- int x;
- cin >> x;
- arr[i] = pow_(x,(mod-1)>>1) == 1;
- pre[i] = ((pre[i-1] << 1) + arr[i]) % mod;
- }
- while (q--){
- int a,b;
- cin >> a >> b;
- ++a; ++b;
- int LB = 0,RB = n - max(a,b);
- if (arr[a] ^ arr[b]) cout << "0\n";
- else{
- while (LB != RB){
- if (isSame(a,a+mid,b,b+mid))
- LB = mid;
- else
- RB = mid-1;
- }
- cout << LB + 1 << '\n';
- }
- }
- }
- signed main(){
- theyRSOOOOOOOOODIAN
- pow2[0] = 1;
- REP1(i,int(1e5)){pow2[i] = (pow2[i-1] << 1) % mod;}
- //for (int ;cin;)//use in multi-testcases and end in EOF problems
- //int t,i=1;for (cin >> t;i<=t;++i)//use in multi-testcases problems
- //cout << "Case #" << i << ": ",//use in Google, FB competitions
- solve();//always used
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement