Auringonlasku

input/code.cpp: In function 'int add(int, int)':
input/code.cpp:36:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
input/code.cpp: In function 'int ans(int, int)':
input/code.cpp:63:7: warning: unused variable 'mx' [-Wunused-variable]
   int mx = 0;
       ^~

// RIP KUN Mo's algorithm C:hen ON MONIMUTKAINEN :EE









#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a; i<(b); i++)
#define IO ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;

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

#define N (1<<17)
#define INF 2147483647
#define ff first
#define ss second

struct Query {
  int l, r, idx;
} queries[2*N];

int n, q;
int t[2*N], cur_cnt[N];

int add(int k, int x) {
  k += N;
  for (k /= 2; k >= 1; k /= 2) {
    t[k] = t[2*k] + t[2*k+1];
  }
}

int sumq(int a, int b) {
  a += N; b += N;
  int s = 0;
  while (a <= b) {
    if (a % 2 == 1) s += t[a++];
    if (b % 2 == 0) s += t[b--];
    a /= 2; b /= 2;
  }
  return s;
}

int S = 500;

bool cmp(const Query& a, const Query& b) {
  if (a.l / S == b.l / S) return a.r < b.r;
  return (a.l / S) < (b.l / S);
}

int v[N];
map<int, int> comp;
set<int> idx_comp;
int lbig[N];
int result[N];

int ans(int a, int b) {
  int mx = 0;
  stack<pii> pq;
  lbig[a] = a-1;
  int ans = 1;
  
  pq.push({v[a], a});
  FOR(i,a+1,b+1) {
    while (pq.size() && pq.top().ff < v[i]) pq.pop();
    if (pq.size() == 0) {
      lbig[i] = 0;
    } else {
      if (v[i] == pq.top().ff) {
        lbig[i] = INF;
      }
      else lbig[i] = pq.top().ss;
    }
    
    if (lbig[i] < a) {
      ans++;
    }
    pq.push({v[i], i});
  }
  
  return ans;
}

vector<int> vals[111];

int main() {
  IO; cin>>n>>q;
  
  FOR(i,1,n+1) {
    int x; cin>>x; v[i] = x;
    idx_comp.insert(x);
  }
  
  int counter = 0;
  for (int val : idx_comp) {
    counter++;
    comp[val] = counter;
  }
  
  FOR(i,1,n+1) {
    v[i] = comp[v[i]];
  }
  
  //goto qaq;
  if (n <= 2000 && q <= 2000) {
    FOR(i,0,q) {
      int a,b; cin>>a>>b;
      cout<<ans(a,b)<<"\n";
    }
    return 0;
  }
  
  //qaq:
  stack<pii> pq;
  lbig[1] = 0;
  
  pq.push({v[1], 1});
  FOR(i,2,n+1) {
    while (pq.size() && pq.top().ff < v[i]) pq.pop();
    if (pq.size() == 0) {
      lbig[i] = 0;
    } else {
      lbig[i] = pq.top().ss;
    }
    
    pq.push({v[i], i});
  }
  
  FOR(i,2,n+1) {
    if (v[i] > v[i-1]) {
      lbig[i] = 0;
    } else break;
  }
  
  FOR(i,1,n+1) {
    vals[lbig[i]].push_back(i);
  }
  
  FOR(i,0,n) {
    vals[i].erase(unique(vals[i].begin(), vals[i].end()), vals[i].end());
    sort(vals[i].begin(), vals[i].end());
    continue;
    cout<<"vals["<<i<<"] = ";
    for (int j : vals[i]) cout<<j<<" ";
    cout<<"\n";
  }
  
  FOR(i,1,q+1) {
    int a,b; cin>>a>>b;
    int ans = 0;
    FOR(j,0,n) {
      if (a <= j && j <= b) continue;
      if (vals[j].size() == 0) continue;
      int betw = upper_bound(vals[j].begin(), vals[j].end(), b) - lower_bound(vals[j].begin(), vals[j].end(), a);
      ans += betw;
    }
    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: RUNTIME ERROR

Test 20

Group: 2

Verdict: RUNTIME ERROR

Test 21

Group: 2

Verdict: RUNTIME ERROR

Test 22

Group: 2

Verdict: RUNTIME ERROR

Test 23

Group: 2

Verdict: RUNTIME ERROR

Test 24

Group: 2

Verdict: RUNTIME ERROR

Test 25

Group: 2

Verdict: RUNTIME ERROR

Test 26

Group: 2

Verdict: RUNTIME ERROR

Test 27

Group: 2

Verdict: RUNTIME ERROR

Test 28

Group: 2

Verdict: ACCEPTED

Test 29

Group: 2

Verdict: RUNTIME ERROR

Test 30

Group: 2

Verdict: RUNTIME ERROR

Test 31

Group: 2

Verdict: RUNTIME ERROR

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: RUNTIME ERROR

Test 50

Group: 3

Verdict: RUNTIME ERROR

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