Auringonlasku

#include <random>
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <set>


using namespace std;


vector<int> v;

const int N = 1e5 + 5;
const int M = 131072;

typedef long long ll;
typedef pair<int, int> pii;

int t[2*M];
int h[N];

int ma(int a, int b) {
    a+=M;
    b+=M;
    int maa = -1;
    while(a <= b) {
        if(a%2 == 1) {
            maa = max(maa, t[a]);
            ++a;
        }
        if(b%2 == 0) {
            maa = max(maa, t[b]);
            --b;
        }
        a/=2; b/=2;
    }
    return maa;
}

void init() {
    for(int i = M-1; i >= 1; --i) {
        t[i] = max(t[2*i], t[2*i + 1]);
    }
    
}

int a[N];


vector<pair<pii, int> > que;

vector<int> sor[5000];

int root;
int n;
int amo(int i, int c) {
    //Amount of numbers in sor[i] below c
    
    int x = root*i - 1;
    for(int b = 12; b >= 0; --b) {
        int nx = x + (1<<b);
        if(nx >= min(root*i + root, n)) continue;
        if(sor[i][nx - root*i] >= c) continue;
        x = nx;
    }
    return x - root*i + 1;
}


ll su[N][111];

int main() {
    iostream::sync_with_stdio(false);
    cin.tie(0);
    
    int q;
    cin >> n >> q;
    for(int i = 0; i < n; ++i) {
        int hh;
        cin >> hh;
        v.push_back(hh);
        t[i+M] = hh;
        h[i] = hh;
    }
    init();
    
    for(int i = 0; i < n; ++i) {
        if(ma(0, i-1) < h[i]) {
            a[i] = -1;
            continue;
        }
        int aa = 0;
        int b = i-1;
        while(aa < b) {
            int mid = (aa+b)/2;
            if(ma(mid+1, b) >= h[i]) {
                aa = mid+1;
            } else {
                b = mid;
            }
        }
        a[i] = aa;
    }

    
    if(n <= 2000) {
        root = 4*sqrt(n);
        int am = (n+root-1)/root;
        
        
        for(int i = 0; i < am; ++i) {
            for(int j = root*i; j < root*i + root; ++j) {
                    sor[i].push_back(a[j]);
            }
            sort(sor[i].begin(), sor[i].end());
        }
        
        
        for(int i = 0; i < q; ++i) {
            int aa, b;
    //        cin >> aa >> b;
            aa = 1; b = n;
            --aa;
            --b;
            int lowI = aa/root;
            int highI = b/root;
            int ans = 0;
            if(lowI == highI) {
                for(int j = aa; j <= b; ++j) {
                    if(a[j] < aa) ++ans;
                }
              cout << ans << "\n";
                continue;
            }
        for(int j = lowI + 1; j < highI; ++j) {
                ans += amo(j, aa);
            }
            
            for(int j = aa; j < lowI*root + root; ++j) {
                if(a[j] < aa) ++ans;
            }
            
            for(int j = highI*root; j <= b; ++j) {
                if(a[j] < aa) ++ans;
            }
            cout << ans << "\n";
            
        }
    } else {
        set<int> s[111];
        for(int i = n; i >= 1; --i) {
            h[i] = h[i-1];
            s[h[i]].insert(i);
        }
        

        for(int i = 1; i <= q; ++i) {
            int a, b;
            cin >> a >> b;
            int ans = 0;
            for(int j = 100; j >= 1; --j) {
                set<int>::iterator it = s[j].lower_bound(a);
                if(it == s[j].end()) continue;
                if(*it > b) continue;
                ++ans;
                b = *it;
            }
            cout << ans << "\n";
        }
        
        
    }
    
    
    
}

Test 1

Group: 1

Verdict: WRONG ANSWER

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: WRONG ANSWER

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: WRONG ANSWER

Test 6

Group: 1

Verdict: WRONG ANSWER

Test 7

Group: 1

Verdict: WRONG ANSWER

Test 8

Group: 1

Verdict: WRONG ANSWER

Test 9

Group: 1

Verdict: ACCEPTED

Test 10

Group: 1

Verdict: ACCEPTED

Test 11

Group: 1

Verdict: WRONG ANSWER

Test 12

Group: 1

Verdict: WRONG ANSWER

Test 13

Group: 1

Verdict: WRONG ANSWER

Test 14

Group: 1

Verdict: WRONG ANSWER

Test 15

Group: 1

Verdict: WRONG ANSWER

Test 16

Group: 1

Verdict: WRONG ANSWER

Test 17

Group: 1

Verdict: WRONG ANSWER

Test 18

Group: 2

Verdict: ACCEPTED

Test 19

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 20

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 21

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 23

Group: 2

Verdict: ACCEPTED

Test 24

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 25

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 26

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 28

Group: 2

Verdict: WRONG ANSWER

Test 29

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 30

Group: 2

Verdict: ACCEPTED

Test 31

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 32

Group: 3

Verdict: ACCEPTED

Test 33

Group: 3

Verdict: RUNTIME ERROR

Test 34

Group: 3

Verdict: RUNTIME ERROR

Test 35

Group: 3

Verdict: RUNTIME ERROR

Test 36

Group: 3

Verdict: RUNTIME ERROR

Test 37

Group: 3

Verdict: RUNTIME ERROR

Test 38

Group: 3

Verdict: RUNTIME ERROR

Test 39

Group: 3

Verdict: RUNTIME ERROR

Test 40

Group: 3

Verdict: RUNTIME ERROR

Test 41

Group: 3

Verdict: RUNTIME ERROR

Test 42

Group: 3

Verdict: RUNTIME ERROR

Test 43

Group: 3

Verdict: RUNTIME ERROR

Test 44

Group: 3

Verdict: RUNTIME ERROR

Test 45

Group: 3

Verdict: RUNTIME ERROR

Test 46

Group: 3

Verdict: RUNTIME ERROR

Test 47

Group: 3

Verdict: RUNTIME ERROR

Test 48

Group: 3

Verdict: RUNTIME ERROR

Test 49

Group: 3

Verdict: ACCEPTED

Test 50

Group: 3

Verdict: ACCEPTED

Test 51

Group: 3

Verdict: RUNTIME ERROR

Test 52

Group: 3

Verdict: RUNTIME ERROR

Test 53

Group: 3

Verdict: RUNTIME ERROR

Test 54

Group: 3

Verdict: RUNTIME ERROR