Auringonlasku

#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
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[3000];

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 = 10; 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;
}

int main() {
    iostream::sync_with_stdio(false);
    cin.tie(0);
    
    int q;
    cin >> n >> q;
    for(int i = 0; i < n; ++i) {
     //   int hh = 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;
    }
    
    root = 5*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";
        
    }
    
    
    
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 1

Verdict: ACCEPTED

Test 7

Group: 1

Verdict: ACCEPTED

Test 8

Group: 1

Verdict: ACCEPTED

Test 9

Group: 1

Verdict: ACCEPTED

Test 10

Group: 1

Verdict: ACCEPTED

Test 11

Group: 1

Verdict: ACCEPTED

Test 12

Group: 1

Verdict: ACCEPTED

Test 13

Group: 1

Verdict: ACCEPTED

Test 14

Group: 1

Verdict: ACCEPTED

Test 15

Group: 1

Verdict: ACCEPTED

Test 16

Group: 1

Verdict: ACCEPTED

Test 17

Group: 1

Verdict: ACCEPTED

Test 18

Group: 2

Verdict: ACCEPTED

Test 19

Group: 2

Verdict: ACCEPTED

Test 20

Group: 2

Verdict: ACCEPTED

Test 21

Group: 2

Verdict: ACCEPTED

Test 22

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 23

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 24

Group: 2

Verdict: ACCEPTED

Test 25

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 26

Group: 2

Verdict: ACCEPTED

Test 27

Group: 2

Verdict: ACCEPTED

Test 28

Group: 2

Verdict: ACCEPTED

Test 29

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 30

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 31

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 32

Group: 3

Verdict: ACCEPTED

Test 33

Group: 3

Verdict: ACCEPTED

Test 34

Group: 3

Verdict: ACCEPTED

Test 35

Group: 3

Verdict: ACCEPTED

Test 36

Group: 3

Verdict: ACCEPTED

Test 37

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 38

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 39

Group: 3

Verdict: ACCEPTED

Test 40

Group: 3

Verdict: ACCEPTED

Test 41

Group: 3

Verdict: ACCEPTED

Test 42

Group: 3

Verdict: ACCEPTED

Test 43

Group: 3

Verdict: ACCEPTED

Test 44

Group: 3

Verdict: ACCEPTED

Test 45

Group: 3

Verdict: ACCEPTED

Test 46

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 47

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 48

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 49

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 50

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 51

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 52

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 53

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 54

Group: 3

Verdict: TIME LIMIT EXCEEDED