# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
466076 | nickmet2004 | popa (BOI18_popa) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include "popa.h"
using namespace std;
/*
int query(int a , int b , int l , int r){
int k =s[a];
for(int i = a+1; i<= b; ++i)k = __gcd(k , s[i]);
int j = s[l];
for(int i = l + 1; i <= r; ++i)j = __gcd(j , s[i]);
return k == j;
}
*/
int solve(int n , int *Left , int *Right) {
stack<int> st;
int root = 0;
memset(Left , -1 , sizeof(Left));
memset(Right , -1 , sizeof(Right));
st.push(0);
for(int i =1; i < n; ++i){
while(st.size() && query(st.top() , i , i , i)){
Right[st.top()] = left[i];
Left[i] = st.top();
st.pop();
}
}
if(st.size()) Right[st.top()] = i;
else root = i;
return root;
}
/*
int main (){
int n;
cin >> n;
for(int i = 0; i< n; ++i)cin >> s[i];
memset(Left , -1 , sizeof(Left));memset(Right , -1 , sizeof(Right));
cout << solve(n)<<endl;
for(int i = 0; i < n; ++i)cout << Left[i] << " " << Right[i] << endl;
}
*/
///20 80 40
///40 80 20