oj.uz

Submission #754861

# Submission time Handle Problem Language Result Execution time Memory
754861 2023-06-08T18:48:17 Z onebit1024 Index (COCI21_index) C++17
60 / 110
 2500 ms 105688 KB 
#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)/2;
        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)/2;
        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,1e9);
        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)/2;
        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==0)return 1e9;
        if(lx >= l && rx <= r)return seg[curr];
        if(rx<=l || lx >= r)return 1e9;
        int m = (lx+rx)/2;
        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(){
    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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 98924 KB Output is correct
2 Correct 48 ms 98892 KB Output is correct
3 Correct 50 ms 98924 KB Output is correct
4 Correct 50 ms 98852 KB Output is correct
5 Correct 47 ms 98876 KB Output is correct
6 Correct 48 ms 98892 KB Output is correct
7 Correct 48 ms 98920 KB Output is correct
8 Correct 53 ms 98896 KB Output is correct
9 Correct 62 ms 98968 KB Output is correct
10 Correct 52 ms 98952 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 98924 KB Output is correct
2 Correct 48 ms 98892 KB Output is correct
3 Correct 50 ms 98924 KB Output is correct
4 Correct 50 ms 98852 KB Output is correct
5 Correct 47 ms 98876 KB Output is correct
6 Correct 48 ms 98892 KB Output is correct
7 Correct 48 ms 98920 KB Output is correct
8 Correct 53 ms 98896 KB Output is correct
9 Correct 62 ms 98968 KB Output is correct
10 Correct 52 ms 98952 KB Output is correct
11 Correct 541 ms 100640 KB Output is correct
12 Correct 522 ms 100576 KB Output is correct
13 Correct 568 ms 100752 KB Output is correct
14 Correct 613 ms 100592 KB Output is correct
15 Correct 582 ms 100576 KB Output is correct
16 Correct 626 ms 100612 KB Output is correct
17 Correct 542 ms 100732 KB Output is correct
18 Correct 580 ms 100652 KB Output is correct
19 Correct 570 ms 100660 KB Output is correct
20 Correct 574 ms 100912 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 98924 KB Output is correct
2 Correct 48 ms 98892 KB Output is correct
3 Correct 50 ms 98924 KB Output is correct
4 Correct 50 ms 98852 KB Output is correct
5 Correct 47 ms 98876 KB Output is correct
6 Correct 48 ms 98892 KB Output is correct
7 Correct 48 ms 98920 KB Output is correct
8 Correct 53 ms 98896 KB Output is correct
9 Correct 62 ms 98968 KB Output is correct
10 Correct 52 ms 98952 KB Output is correct
11 Correct 541 ms 100640 KB Output is correct
12 Correct 522 ms 100576 KB Output is correct
13 Correct 568 ms 100752 KB Output is correct
14 Correct 613 ms 100592 KB Output is correct
15 Correct 582 ms 100576 KB Output is correct
16 Correct 626 ms 100612 KB Output is correct
17 Correct 542 ms 100732 KB Output is correct
18 Correct 580 ms 100652 KB Output is correct
19 Correct 570 ms 100660 KB Output is correct
20 Correct 574 ms 100912 KB Output is correct
21 Execution timed out 2570 ms 105688 KB Time limit exceeded
22 Halted 0 ms 0 KB -