제출 #754862

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
754862		onebit1024	Index (COCI21_index)	C++17	60 / 110	2555 ms	105900 KiB

index

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define all(v) v.begin(), v.end()
#define endl "\n"

void __print(int x){cerr << x;}
void __print(long double x){cerr << x;}
void __print(char x){cerr << '\'' << x << '\'';}
void __print(double x){cerr << x;}
void __print(float x){cerr << x;}
void __print(unsigned int x){cerr << x;}
void __print(bool x){cerr << x;}
void __print(const char *x){cerr << '\"' << x << '"';}
void __print(const string &x){cerr << '\"' << x << '"';}

template<typename T, typename V>
void __print(const pair<T,V>&x){cerr << "{";__print(x.first);cerr<<",";__print(x.second);cerr<<"}";}
template<typename T>
void __print(const T&x){int f = 0;cerr<<"{";for(auto &i:x)cerr<<(f++?",":""),__print(i);cerr<<"}";}
void _print(){cerr << "]\n";}
template<typename T, typename...V>
void _print(T t, V... v){__print(t);if(sizeof...(v))cerr<<",";_print(v...);}

#ifndef ONLINE_JUDGE
#define dbg(x...)cerr << "LINE(" << __LINE__ << ") -> [" << #x << "] = [";_print(x);
#else
#define dbg(x...)
#endif

const int mxn = 2e5+5, mxk = 20;
struct pstactive{
    vector<pair<int,int>>child;
    vector<int>seg;
    int ptr = 0, sz = 1;
    void init(int n){
        while(sz < n)sz*=2;
        seg.resize(mxn*mxk);
        child.resize(mxn*mxk);
    }

    void set(int curr, int prev, int lx, int rx, int i, int v){
        if(rx-lx==1){
            seg[curr] = v;
            return;
        }
        int m = (lx+rx)>>1;
        if(i < m){
            child[curr].first = ++ptr;
            child[curr].second = child[prev].second;
            set(child[curr].first, child[prev].first, lx,m,i,v);
        }else{  
            child[curr].second = ++ptr;
            child[curr].first = child[prev].first;
            set(child[curr].second, child[prev].second,m, rx, i, v);
        }
        seg[curr] = seg[child[curr].first] + seg[child[curr].second];
    }

    void set(int curr, int prev, int i, int v){
        set(curr,prev,0,sz,i,v);
    }

    int sol(int curr, int lx, int rx, int l, int r){
        if(curr==0)return 0;
        if(lx >= l && rx <= r)return seg[curr];
        if(rx<=l || lx >= r)return 0ll;
        int m = (lx+rx)>>1;
        return sol(child[curr].first,lx,m,l,r)+sol(child[curr].second,m,rx,l,r);
    }

    int sol(int curr, int l, int r){
        return sol(curr,0,sz,l,r);
    }
};

struct pstmin{
    vector<pair<int,int>>child;
    vector<int>seg;
    int ptr = 0, sz = 1;
    void init(int n){
        while(sz < n)sz*=2;
        seg.resize(mxn*mxk,1000000000);
        child.resize(mxn*mxk);
    }

    void set(int curr, int prev, int lx, int rx, int i, int v){
        if(rx-lx==1){
            seg[curr] = v;
            return;
        }
        int m = (lx+rx)>>1;
        if(i < m){
            child[curr].first = ++ptr;
            child[curr].second = child[prev].second;
            set(child[curr].first, child[prev].first, lx,m,i,v);
        }else{  
            child[curr].second = ++ptr;
            child[curr].first = child[prev].first;
            set(child[curr].second, child[prev].second,m, rx, i, v);
        }
        seg[curr] = min(seg[child[curr].first], seg[child[curr].second]);
    }

    void set(int curr, int prev, int i, int v){
        set(curr,prev,0,sz,i,v);
    }

    int sol(int curr, int lx, int rx, int l, int r){
        if(!curr)return 1000000000;
        if(lx >= l && rx <= r)return seg[curr];
        if(rx<=l || lx >= r)return 1000000000;
        int m = (lx+rx)>>1;
        return min(sol(child[curr].first,lx,m,l,r),sol(child[curr].second,m,rx,l,r));
    }

    int sol(int curr, int l, int r){
        return sol(curr,0,sz,l,r);
    }
};

int a[mxn],rootmin[mxn],rootactive[mxn];
int32_t main(){
    ios::sync_with_stdio(false); cin.tie(NULL);

    int n,k;
    cin >> n>> k;

    for(int i = 1;i<=n;++i)cin >> a[i];
    pstmin pstmn;
    pstactive pstact;

    pstmn.init(n+1);
    pstact.init(n+1);

    vector<vector<int>>vals(mxn+1);
    for(int i = 1;i<=n;++i)vals[a[i]].pb(i);
    int lst = 1;
    for(int i = mxn;i>=0;--i){
        if(vals[i].empty())continue;
        rootmin[lst] = rootmin[lst-1];
        for(int v : vals[i]){
            int curr = ++pstmn.ptr, prev = rootmin[lst];
            pstmn.set(curr,prev,v,i);
            rootmin[lst] = curr;    
        }
        rootactive[lst] = rootactive[lst-1];
        for(int v : vals[i]){
            int curr = ++pstact.ptr, prev = rootactive[lst];
            pstact.set(curr,prev,v,1);
            rootactive[lst] = curr;
        }
        lst++;
    }
    while(k--){
        int L, R;
        cin >> L >> R;
        int l = 1, r  = lst-1;
        int res = 0;
        while(l <= r){
            int m = (l+r)/2;
            int x = pstact.sol(rootactive[m],L,R+1);
            int y = pstmn.sol(rootmin[m],L,R+1);
            if(x < y){
                res = max(res, x);
                l= m+1;
            }else{
                res = max(res, y);
                r = m-1;
            }
        }
        cout << res << endl;
    }
}   
/*
7 1
3 2 3 1 1 4 7
1 7
*/
/*
atleast x elements should be >= x in the range

x = number of active elements in the range
y = minimum active element in the range

if y == x it doesn't matter you've achieved max possible

4 5 6 7 8
x = 5
y = 4

if y > x then you can achieve x and you want to go to some later versoin of pst (with more elements)
if y < x then you can achieve y and you go to some earlier versin of pst (with less active elements)
*/

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 0 / 50