CSES - Datatähti 2019 loppu - Results
Submission details
Task:Auringonlasku
Sender:Tuukka Yildirim
Submission time:2019-01-17 15:28:13 +0200
Language:C++
Status:READY
Result:16
Feedback
groupverdictscore
#1ACCEPTED16
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1details
#2ACCEPTED0.01 s1details
#3ACCEPTED0.01 s1details
#4ACCEPTED0.01 s1details
#5ACCEPTED0.06 s1details
#6ACCEPTED0.04 s1details
#7ACCEPTED0.02 s1details
#8ACCEPTED0.09 s1details
#9ACCEPTED0.08 s1details
#10ACCEPTED0.07 s1details
#11ACCEPTED0.07 s1details
#12ACCEPTED0.04 s1details
#13ACCEPTED0.06 s1details
#14ACCEPTED0.05 s1details
#15ACCEPTED0.08 s1details
#16ACCEPTED0.08 s1details
#17ACCEPTED0.07 s1details
#18ACCEPTED0.01 s2details
#190.05 s2details
#200.03 s2details
#210.05 s2details
#220.04 s2details
#230.03 s2details
#240.05 s2details
#250.06 s2details
#260.04 s2details
#270.05 s2details
#28ACCEPTED0.02 s2details
#290.03 s2details
#300.04 s2details
#310.05 s2details
#32ACCEPTED0.03 s3details
#330.15 s3details
#340.15 s3details
#350.10 s3details
#360.15 s3details
#370.15 s3details
#380.04 s3details
#390.15 s3details
#40--3details
#410.16 s3details
#42--3details
#430.15 s3details
#440.10 s3details
#45--3details
#460.09 s3details
#470.10 s3details
#480.09 s3details
#490.03 s3details
#500.05 s3details
#510.06 s3details
#520.05 s3details
#530.08 s3details
#540.07 s3details

Compiler report

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;
       ^~

Code

// 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,101) {
    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 details

Test 1

Group: 1

Verdict: ACCEPTED

input
5 3
4 1 2 2 3
1 5
2 5
3 4

correct output
1
3
1

user output
1
3
1

Test 2

Group: 1

Verdict: ACCEPTED

input
1 1
1
1 1

correct output
1

user output
1

Test 3

Group: 1

Verdict: ACCEPTED

input
2 3
1 1000000000
1 1
2 2
1 2

correct output
1
1
2

user output
1
1
2

Test 4

Group: 1

Verdict: ACCEPTED

input
2 3
1000000000 1
1 1
2 2
1 2

correct output
1
1
1

user output
1
1
1

Test 5

Group: 1

Verdict: ACCEPTED

input
2000 2000
387547790 498212511 224378606 ...

correct output
14
10
10
3
7
...

user output
14
10
10
3
7
...

Test 6

Group: 1

Verdict: ACCEPTED

input
2000 2000
13604803 27447643 34139694 383...

correct output
198
43
38
58
50
...

user output
198
43
38
58
50
...

Test 7

Group: 1

Verdict: ACCEPTED

input
2000 2000
387547790 498212511 224378606 ...

correct output
1
1
1
1
1
...

user output
1
1
1
1
1
...

Test 8

Group: 1

Verdict: ACCEPTED

input
2000 2000
409666302 646936685 583741760 ...

correct output
8
9
12
8
11
...

user output
8
9
12
8
11
...

Test 9

Group: 1

Verdict: ACCEPTED

input
2000 2000
1000000000 1000000000 10000000...

correct output
1
1
1
1
1
...

user output
1
1
1
1
1
...

Test 10

Group: 1

Verdict: ACCEPTED

input
2000 2000
785263 793567 1573404 1750090 ...

correct output
2000
2000
2000
2000
2000
...

user output
2000
2000
2000
2000
2000
...

Test 11

Group: 1

Verdict: ACCEPTED

input
2000 2000
785263 793567 1573404 1750090 ...

correct output
1960
1947
1963
1942
1944
...

user output
1960
1947
1963
1942
1944
...

Test 12

Group: 1

Verdict: ACCEPTED

input
1999 2000
129087461 494922181 482953911 ...

correct output
10
6
6
7
7
...

user output
10
6
6
7
7
...

Test 13

Group: 1

Verdict: ACCEPTED

input
2000 2000
409666302 646936685 583741760 ...

correct output
8
7
6
7
7
...

user output
8
7
6
7
7
...

Test 14

Group: 1

Verdict: ACCEPTED

input
2000 2000
44989 1437234 1640005 1765235 ...

correct output
1233
1389
1026
150
796
...

user output
1233
1389
1026
150
796
...

Test 15

Group: 1

Verdict: ACCEPTED

input
2000 2000
2 1 4 3 6 5 8 7 10 9 12 11 14 ...

correct output
988
994
981
979
973
...

user output
988
994
981
979
973
...

Test 16

Group: 1

Verdict: ACCEPTED

input
2000 2000
1999 2000 1997 1998 1995 1996 ...

correct output
1
2
1
1
2
...

user output
1
2
1
1
2
...

Test 17

Group: 1

Verdict: ACCEPTED

input
2000 2000
2 1 4 3 5 4 5 2 3 1 2 1 4 3 5 ...

correct output
2
1
1
2
3
...

user output
2
1
1
2
3
...

Test 18

Group: 2

Verdict: ACCEPTED

input
1 1
1
1 1

correct output
1

user output
1

Test 19

Group: 2

Verdict:

input
100000 200000
32 22 35 59 37 2 5 5 79 53 22 ...

correct output
4
9
6
5
4
...

user output
(empty)

Test 20

Group: 2

Verdict:

input
100000 200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
89
35
59
25
12
...

user output
(empty)

Test 21

Group: 2

Verdict:

input
100000 200000
32 22 35 59 37 2 5 5 79 53 22 ...

correct output
1
1
1
1
1
...

user output
(empty)

Test 22

Group: 2

Verdict:

input
100000 200000
72 58 92 12 32 29 55 87 6 49 5...

correct output
5
7
5
6
2
...

user output
(empty)

Test 23

Group: 2

Verdict:

input
100000 200000
100 100 100 100 100 100 100 10...

correct output
1
1
1
1
1
...

user output
(empty)

Test 24

Group: 2

Verdict:

input
100000 200000
72 58 92 12 32 29 55 87 6 49 5...

correct output
4
7
6
7
4
...

user output
(empty)

Test 25

Group: 2

Verdict:

input
100000 200000
72 58 92 12 32 29 55 87 6 49 5...

correct output
5
5
5
5
5
...

user output
(empty)

Test 26

Group: 2

Verdict:

input
99999 200000
20 47 84 90 88 63 39 16 74 19 ...

correct output
5
7
6
3
3
...

user output
(empty)

Test 27

Group: 2

Verdict:

input
100000 200000
72 58 92 12 32 29 55 87 6 49 5...

correct output
6
4
9
2
5
...

user output
(empty)

Test 28

Group: 2

Verdict: ACCEPTED

input
5 1
4 1 5 6 9
1 3

correct output
2

user output
2

Test 29

Group: 2

Verdict:

input
100000 200000
2 1 4 3 6 5 8 7 10 9 12 11 14 ...

correct output
44
4
27
46
29
...

user output
(empty)

Test 30

Group: 2

Verdict:

input
100000 200000
2 1 4 3 5 4 5 2 3 1 2 1 4 3 5 ...

correct output
3
3
3
3
2
...

user output
(empty)

Test 31

Group: 2

Verdict:

input
100000 200000
2 1 4 3 6 5 8 7 10 9 12 11 14 ...

correct output
39
10
37
20
43
...

user output
(empty)

Test 32

Group: 3

Verdict: ACCEPTED

input
1 1
1
1 1

correct output
1

user output
1

Test 33

Group: 3

Verdict:

input
100000 200000
994198482 687493351 579440176 ...

correct output
8
6
8
10
5
...

user output
(empty)

Test 34

Group: 3

Verdict:

input
100000 200000
138644593 592364551 919805093 ...

correct output
10
11
13
7
12
...

user output
(empty)

Test 35

Group: 3

Verdict:

input
100000 200000
10770 195579 349462 442791 450...

correct output
2468
1986
2632
129
4010
...

user output
(empty)

Test 36

Group: 3

Verdict:

input
100000 200000
994198482 687493351 579440176 ...

correct output
1
2
1
2
1
...

user output
(empty)

Test 37

Group: 3

Verdict:

input
100000 200000
398809514 622635167 133376912 ...

correct output
15
13
16
11
17
...

user output
(empty)

Test 38

Group: 3

Verdict:

input
100000 200000
1000000000 1000000000 10000000...

correct output
1
1
1
1
1
...

user output
(empty)

Test 39

Group: 3

Verdict:

input
100000 200000
398809514 622635167 133376912 ...

correct output
10
16
7
18
10
...

user output
(empty)

Test 40

Group: 3

Verdict:

input
100000 200000
11465 15800 19042 19282 20348 ...

correct output
99542
99728
99391
99890
99716
...

user output
(empty)

Test 41

Group: 3

Verdict:

input
99999 200000
587542096 890780320 258438313 ...

correct output
8
6
11
11
17
...

user output
(empty)

Test 42

Group: 3

Verdict:

input
100000 200000
11283 24634 28852 37453 37625 ...

correct output
100000
100000
100000
100000
100000
...

user output
(empty)

Test 43

Group: 3

Verdict:

input
100000 200000
398809514 622635167 133376912 ...

correct output
13
13
10
15
15
...

user output
(empty)

Test 44

Group: 3

Verdict:

input
100000 200000
11465 15800 19042 19282 20348 ...

correct output
36112
6013
51073
8123
82052
...

user output
(empty)

Test 45

Group: 3

Verdict:

input
100000 200000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
99407
99529
99590
99589
99679
...

user output
(empty)

Test 46

Group: 3

Verdict:

input
100000 200000
100000 99999 99998 99997 99996...

correct output
1
1
1
1
1
...

user output
(empty)

Test 47

Group: 3

Verdict:

input
100000 200000
2 1 4 3 6 5 8 7 10 9 12 11 14 ...

correct output
49946
49703
49786
49864
49720
...

user output
(empty)

Test 48

Group: 3

Verdict:

input
100000 200000
99999 100000 99997 99998 99995...

correct output
2
1
2
2
1
...

user output
(empty)

Test 49

Group: 3

Verdict:

input
100000 200000
2 1 4 3 5 4 5 2 3 1 2 1 4 3 5 ...

correct output
3
3
3
3
2
...

user output
(empty)

Test 50

Group: 3

Verdict:

input
100000 200000
2 1 4 3 6 5 8 7 10 9 12 11 14 ...

correct output
19
23
2
21
4
...

user output
(empty)

Test 51

Group: 3

Verdict:

input
100000 200000
2 1 4 3 6 5 8 7 10 9 12 11 14 ...

correct output
112
237
49
141
57
...

user output
(empty)

Test 52

Group: 3

Verdict:

input
100000 200000
2 1 4 3 6 5 8 7 10 9 12 11 14 ...

correct output
2457
2199
2351
2450
2475
...

user output
(empty)

Test 53

Group: 3

Verdict:

input
100000 200000
2 1 4 3 6 5 8 7 10 9 12 11 14 ...

correct output
24841
24973
24865
24823
24969
...

user output
(empty)

Test 54

Group: 3

Verdict:

input
100000 200000
49999 50000 49997 49998 49995 ...

correct output
210
1
2
2
1
...

user output
(empty)