oj.uz

Submission #754860

# Submission time Handle Problem Language Result Execution time Memory
754860 2023-06-08T18:36:40 Z onebit1024 Index (COCI21_index) C++17
60 / 110
 2500 ms 202692 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#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 1e18;
        if(lx >= l && rx <= r)return seg[curr];
        if(rx<=l || lx >= r)return 1e18;
        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);
    }
};

int32_t main(){
    int n,k;
    cin >> n>> k;
    vector<int>a(n+1);
    for(int i = 1;i<=n;++i)cin >> a[i];
    pstmin pstmn;
    pstactive pstact;
    vector<int>rootmin(n+1), rootactive(n+1);
    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 79 ms 192908 KB Output is correct
2 Correct 78 ms 192832 KB Output is correct
3 Correct 80 ms 192872 KB Output is correct
4 Correct 78 ms 192840 KB Output is correct
5 Correct 82 ms 192868 KB Output is correct
6 Correct 79 ms 192856 KB Output is correct
7 Correct 78 ms 192820 KB Output is correct
8 Correct 90 ms 192812 KB Output is correct
9 Correct 96 ms 192824 KB Output is correct
10 Correct 79 ms 192796 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 192908 KB Output is correct
2 Correct 78 ms 192832 KB Output is correct
3 Correct 80 ms 192872 KB Output is correct
4 Correct 78 ms 192840 KB Output is correct
5 Correct 82 ms 192868 KB Output is correct
6 Correct 79 ms 192856 KB Output is correct
7 Correct 78 ms 192820 KB Output is correct
8 Correct 90 ms 192812 KB Output is correct
9 Correct 96 ms 192824 KB Output is correct
10 Correct 79 ms 192796 KB Output is correct
11 Correct 651 ms 195368 KB Output is correct
12 Correct 629 ms 195500 KB Output is correct
13 Correct 668 ms 195524 KB Output is correct
14 Correct 625 ms 195376 KB Output is correct
15 Correct 613 ms 195428 KB Output is correct
16 Correct 614 ms 195372 KB Output is correct
17 Correct 659 ms 195340 KB Output is correct
18 Correct 750 ms 195428 KB Output is correct
19 Correct 732 ms 195388 KB Output is correct
20 Correct 618 ms 195396 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 192908 KB Output is correct
2 Correct 78 ms 192832 KB Output is correct
3 Correct 80 ms 192872 KB Output is correct
4 Correct 78 ms 192840 KB Output is correct
5 Correct 82 ms 192868 KB Output is correct
6 Correct 79 ms 192856 KB Output is correct
7 Correct 78 ms 192820 KB Output is correct
8 Correct 90 ms 192812 KB Output is correct
9 Correct 96 ms 192824 KB Output is correct
10 Correct 79 ms 192796 KB Output is correct
11 Correct 651 ms 195368 KB Output is correct
12 Correct 629 ms 195500 KB Output is correct
13 Correct 668 ms 195524 KB Output is correct
14 Correct 625 ms 195376 KB Output is correct
15 Correct 613 ms 195428 KB Output is correct
16 Correct 614 ms 195372 KB Output is correct
17 Correct 659 ms 195340 KB Output is correct
18 Correct 750 ms 195428 KB Output is correct
19 Correct 732 ms 195388 KB Output is correct
20 Correct 618 ms 195396 KB Output is correct
21 Execution timed out 2584 ms 202692 KB Time limit exceeded
22 Halted 0 ms 0 KB -