Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define LL long long
- #define N ((int)1e5 + 8)
- #define MAX ((int)1e9 + 8)
- #define fastio ios_base::sync_with_stdio(false),cin.tie(NULL)
- #define Type pair < int , int >
- using namespace std;
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // generator
- int GetRandomNumber(int a , int b)
- {
- return uniform_int_distribution<int>(a, b)(rng); //rand([a,b])
- }
- Type Opp(Type a , Type b, int type)
- {
- if(type == 0) return min(a,b);
- if(type == 1) return max(a,b);
- }
- int range[N];
- void PreProcess(int n , vector < vector < Type > >& tab , vector < int >& arr, int type)
- {
- for(int i = 1 ; i <= n ; i++) tab[i][0] = {arr[i] , i};
- for(int p = 1 ; p <= 20 ; p++){
- for(int i = 1 ; i <= n ; i++){
- tab[i][p] = tab[i][p-1];
- ///int L = (i + 2^p - 1) - 2^(p-1) + 1; => i + 2^p - 2^(p-1) => i + 2^(p-1)
- int L = i + (1<<(p-1));
- if(L <= n) tab[i][p] = Opp(tab[i][p] , tab[L][p-1], type);
- }
- }
- /// O(nlogn)
- }
- void Cal(int n)
- {
- range[1] = 0; /// range[len] = p ; 2^p <= len and 2^(p+1) > len
- for(int i = 2 ; i <= n ; i++){
- range[i] = range[i-1];
- if((i & (i-1)) == 0) range[i]++;
- ///range[i] = range[i/2] + 1;
- }
- }
- Type Query(int L , int R , vector < vector < int > >& tab, int type) /// find minimum, overlapping allowed
- {
- if(L > R) return MAX; /// invalid
- int len = R - L + 1;
- int p = range[len];
- ///int i = L + (1<<p) - 1;
- int ans = tab[L][p]; /// green portion
- int i = R - (1<<p) + 1;
- ans = Opp(ans , tab[i][p], type); /// blue portion
- return ans;
- } /// O(1)
- int main()
- {
- /// problem: https://lightoj.com/problem/ghajini
- int n , d;
- cin>>n>>d;
- vector < int > arr(n+1);
- for(int i = 1 ; i <= n ; i++) cin>>arr[i];
- vector < vector < int > > maxTab(n+1 , vector < int >(22)) , minTab(n+1 , vector < int >(22));
- Cal(n);
- PreProcess(n, maxTab , arr, 1);
- PreProcess(n, minTab , arr, 0);
- int ans = 0;
- for(int i = 1 ; i <= n - d + 1 ; i++){
- int L = i , R = i + d - 1;
- int val = Query(L , R , maxTab , 1) - Query(L , R , minTab , 0);
- ans = max(ans , val);
- }
- cout<<ans<<endl;
- /// problem: https://www.spoj.com/problems/MOZPWS/
- vector < int > ans(n - d + 1 + 1);
- for(int i = 1 ; i <= n - d + 1 ; i++){
- int L = i , R = i + d - 1;
- ans[i] = Query(L , R , minTab , 0);
- }
- PreProcess(n - d + 1 , maxTab , ans , 1);
- int q;
- cin>>q;
- while(q--){
- int L , R;
- cin>>L>>R;
- R = R - d + 1;
- if(L > R) cout<<"Impossible\n";
- else cout<<Query(L , R , maxTab , 1);
- }
- return 0;
- }
- LL Solve(int L , int R, vector < vector < int > >& tab)
- {
- if(L > R) return -MAX;
- Type val = Query(L , R , tab , 0);
- int hieght = val.first , pos = val.second;
- LL ans = 1LL*height*(R - L + 1);
- /// O(1)
- return max(ans , max(Solve(L , pos - 1 , tab) , Solve(pos+1 , R , tab)) );
- } /// O(n)
- int main()
- {
- /// problem: https://lightoj.com/problem/histogram
- int n ;
- cin>>n;
- for(int i = 1 ; i <= n ; i++) cin>>arr[i];
- vector < vector < pair < int , int > > > minTab(n+1 , vector < pair < int , int > >(22));
- Cal(n);
- PreProcess(n , minTab , arr, 0); /// O(nlogn)
- cout<<Solve(1 , n , minTab, 1)<<endl;
- }
- LL Solve(int L , int R, vector < vector < int > >& tab , int type)
- {
- if(L > R) return 0;
- Type val = Query(L , R , tab , type);
- int hieght = val.first , pos = val.second;
- LL con = 1LL*(pos - L + 1) * (R - pos + 1);
- LL ans = 1LL*height*con;
- /// O(1)
- return ans + Solve(L , pos - 1 , tab , type) + Solve(pos+1 , R , tab , type) ;
- } /// O(n)
- int main()
- {
- /// problem: https://www.spoj.com/problems/DIFERENC/
- int n ;
- cin>>n;
- for(int i = 1 ; i <= n ; i++) cin>>arr[i];
- vector < vector < pair < int , int > > > minTab(n+1 , vector < pair < int , int > >(22)) , maxTab(n+1 , vector < Type > (22));
- Cal(n);
- PreProcess(n , minTab , arr, 0); /// O(nlogn)
- PreProcess(n , maxTab , arr, 1); /// O(nlogn)
- cout<<Solve(1 , n , maxTab, 1) - Solve(1 , n , minTab , 0)<<endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement