— Dark mode

Datatähti Open 2019

Sunset

  • Start: N/A
  • End: N/A
Submission details
Task:Sunset
Sender:elektrijanes
Submission time:2019-01-22 14:39:26 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.02 s1details
#2ACCEPTED0.03 s1details
#30.03 s1details
#40.01 s1details
#50.03 s1details
#60.02 s1details
#70.03 s1details
#80.02 s1details
#90.02 s1details
#100.03 s1details
#110.02 s1details
#120.03 s1details
#130.02 s1details
#140.03 s1details
#150.03 s1details
#160.03 s1details
#170.03 s1details
#18ACCEPTED0.02 s2details
#190.35 s2details
#200.34 s2details
#210.34 s2details
#220.34 s2details
#230.32 s2details
#240.35 s2details
#250.33 s2details
#260.34 s2details
#270.35 s2details
#280.01 s2details
#290.34 s2details
#300.33 s2details
#310.33 s2details
#32ACCEPTED0.01 s3details
#330.36 s3details
#340.36 s3details
#350.34 s3details
#360.36 s3details
#370.35 s3details
#380.33 s3details
#390.37 s3details
#400.33 s3details
#410.36 s3details
#420.33 s3details
#430.35 s3details
#440.33 s3details
#450.32 s3details
#460.33 s3details
#470.32 s3details
#480.32 s3details
#490.32 s3details
#500.34 s3details
#510.35 s3details
#520.34 s3details
#530.33 s3details
#540.34 s3details

Compiler report

input/code.cpp: In function 'void vaar(ll, ll, ll, ll, ll)':
input/code.cpp:43:7: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
     if(x>=i && j>=y) if(t[n]>ma){
       ^

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ifstream fin("AAtest.in.txt");
ll n,q,mit[100005],c,k,x,y,koht,ma;
pair<ll,ll> p[100005];
vector<ll> t;

bool boo(pair<ll,ll> e,pair<ll,ll> v){
    if(v.first!=e.first) return e.first>v.first;
    return e.second<v.second;
}

void pane(ll n,ll x,ll y,ll i,ll j,ll v){
    if(x>y || j<x || y<i) return ;
    if(x==y){
        t[n]=v;
        return ;
    }
    pane(2*n,x,(x+y)/2,i,j,v);
    pane(2*n+1,(x+y)/2+1,y,i,j,v);
    t[n]=t[2*n]+t[2*n+1];
}

ll otsi(ll n,ll x,ll y,ll i){ //cout<<n<<" "<<x<<" "<<y<<" "<<c/2<<"\n";
    if(x>y || y<=i) return 0;
    if(!t[n]) return 0;
    if(x==y) return n-c/2+1;
    ll l=otsi(2*n,x,(x+y)/2,i);
    if(l==0) l=otsi(2*n+1,(x+y)/2+1,y,i);
    return l;
}

void vaar(ll n,ll x,ll y,ll i,ll j){
    if(x>y || j<x || y<i) return ;
    if(x==y){
        if(t[n]>ma){
            ma=t[n];
            koht=n-c/2+1;
        }
        return ;
    }
    if(x>=i && j>=y) if(t[n]>ma){
        if(t[2*n]==t[n]) vaar(2*n,x,(x+y)/2,i,j);
        else vaar(2*n+1,(x+y)/2+1,y,i,j);
    }
    else {
        if(t[2*n]>ma) vaar(2*n,x,(x+y)/2,i,j);
        if(t[2*n+1]>ma) vaar(2*n+1,(x+y)/2+1,y,i,j);
    }
}

void pane2(ll n,ll x,ll y,ll i,ll j,ll v){
    if(x>y || i>y || j<x) return ;
    if(x==y){
        t[n]=v;
        return;
    }
    pane2(2*n,x,(x+y)/2,i,j,v);
    pane2(2*n+1,(x+y)/2+1,y,i,j,v);
    t[n]=max(t[2*n],t[2*n+1]);
}

int main(){
    ios::sync_with_stdio(0);
    cin>>n>>q;
    c=1;
    while(c<n) c*=2;
    c*=2;
    t.resize(c+3);
    for(int i=1; i<=n; i++) cin>>p[i].first,p[i].second=i;
    sort(p,p+n+1,boo);
    memset(mit,-1,sizeof(mit));
    for(int i=0; i<n; i++){
        pane(1,1,c/2,p[i].second,p[i].second,1);
        k=otsi(1,1,c/2,p[i].second);
        mit[p[i].second]=mit[k]+1;
    }
    t.resize(0);
    t.resize(c+3,0);
    for(int i=0; i<n; i++) pane2(1,1,c/2,p[i].second,p[i].second,p[i].first);
    for(int i=0; i<q; i++){
        cin>>x>>y;
        ma=0;
        vaar(1,1,c/2,x,y);
        //cout<<koht<<"\n";
        cout<<mit[x]-mit[koht]+1<<"\n";
    }
}

Test details

Test 1

Group: 1

Verdict:

input
5 3
4 1 2 2 3
1 5
2 5
3 4
view save

correct output
1
3
1
view save

user output
2
4
3
view save

Test 2

Group: 1

Verdict: ACCEPTED

input
1 1
1
1 1
view save

correct output
1
view save

user output
1
view save

Test 3

Group: 1

Verdict:

input
2 3
1 1000000000
1 1
2 2
1 2
view save

correct output
1
1
2
view save

user output
3
2
2
view save

Test 4

Group: 1

Verdict:

input
2 3
1000000000 1
1 1
2 2
1 2
view save

correct output
1
1
1
view save

user output
2
2
1
view save

Test 5

Group: 1

Verdict:

input
2000 2000
387547790 498212511 224378606 ...
view save

correct output
14
10
10
3
7
...
view save

user output
15
12
11
7
8
...
Truncated

Test 6

Group: 1

Verdict:

input
2000 2000
13604803 27447643 34139694 383...
view save

correct output
198
43
38
58
50
...
view save

user output
202
63
40
60
51
...
Truncated

Test 7

Group: 1

Verdict:

input
2000 2000
387547790 498212511 224378606 ...
view save

correct output
1
1
1
1
1
...
view save

user output
11
10
11
8
4
...
Truncated

Test 8

Group: 1

Verdict:

input
2000 2000
409666302 646936685 583741760 ...
view save

correct output
8
9
12
8
11
...
view save

user output
9
10
13
9
12
...
Truncated

Test 9

Group: 1

Verdict:

input
2000 2000
1000000000 1000000000 10000000...
view save

correct output
1
1
1
1
1
...
view save

user output
2
2
2
2
2
...
Truncated

Test 10

Group: 1

Verdict:

input
2000 2000
785263 793567 1573404 1750090 ...
view save

correct output
2000
2000
2000
2000
2000
...
view save

user output
2001
2001
2001
2001
2001
...
Truncated

Test 11

Group: 1

Verdict:

input
2000 2000
785263 793567 1573404 1750090 ...
view save

correct output
1960
1947
1963
1942
1944
...
view save

user output
2000
1985
1975
1983
1974
...
Truncated

Test 12

Group: 1

Verdict:

input
1999 2000
129087461 494922181 482953911 ...
view save

correct output
10
6
6
7
7
...
view save

user output
14
10
8
9
10
...
Truncated

Test 13

Group: 1

Verdict:

input
2000 2000
409666302 646936685 583741760 ...
view save

correct output
8
7
6
7
7
...
view save

user output
9
8
8
9
8
...
Truncated

Test 14

Group: 1

Verdict:

input
2000 2000
44989 1437234 1640005 1765235 ...
view save

correct output
1233
1389
1026
150
796
...
view save

user output
1659
1686
1341
257
1527
...
Truncated

Test 15

Group: 1

Verdict:

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

correct output
988
994
981
979
973
...
view save

user output
993
998
984
981
985
...
Truncated

Test 16

Group: 1

Verdict:

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

correct output
1
2
1
1
2
...
view save

user output
3
4
3
3
4
...
Truncated

Test 17

Group: 1

Verdict:

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

correct output
2
1
1
2
3
...
view save

user output
3
2
2
3
4
...
Truncated

Test 18

Group: 2

Verdict: ACCEPTED

input
1 1
1
1 1
view save

correct output
1
view save

user output
1
view save

Test 19

Group: 2

Verdict:

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

correct output
4
9
6
5
4
...
view save

user output
5
10
7
6
5
...
Truncated

Test 20

Group: 2

Verdict:

input
100000 200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
view save

correct output
89
35
59
25
12
...
view save

user output
90
36
60
26
95
...
Truncated

Test 21

Group: 2

Verdict:

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

correct output
1
1
1
1
1
...
view save

user output
7
4
7
10
8
...
Truncated

Test 22

Group: 2

Verdict:

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

correct output
5
7
5
6
2
...
view save

user output
6
8
6
7
3
...
Truncated

Test 23

Group: 2

Verdict:

input
100000 200000
100 100 100 100 100 100 100 10...
view save

correct output
1
1
1
1
1
...
view save

user output
2
2
2
2
2
...
Truncated

Test 24

Group: 2

Verdict:

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

correct output
4
7
6
7
4
...
view save

user output
5
8
7
8
5
...
Truncated

Test 25

Group: 2

Verdict:

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

correct output
5
5
5
5
5
...
view save

user output
6
6
6
6
6
...
Truncated

Test 26

Group: 2

Verdict:

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

correct output
5
7
6
3
3
...
view save

user output
6
8
7
4
4
...
Truncated

Test 27

Group: 2

Verdict:

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

correct output
6
4
9
2
5
...
view save

user output
7
5
10
3
6
...
Truncated

Test 28

Group: 2

Verdict:

input
5 1
4 1 5 6 9
1 3
view save

correct output
2
view save

user output
5
view save

Test 29

Group: 2

Verdict:

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

correct output
44
4
27
46
29
...
view save

user output
45
5
28
47
30
...
Truncated

Test 30

Group: 2

Verdict:

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

correct output
3
3
3
3
2
...
view save

user output
4
4
4
4
3
...
Truncated

Test 31

Group: 2

Verdict:

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

correct output
39
10
37
20
43
...
view save

user output
40
11
38
21
44
...
Truncated

Test 32

Group: 3

Verdict: ACCEPTED

input
1 1
1
1 1
view save

correct output
1
view save

user output
1
view save

Test 33

Group: 3

Verdict:

input
100000 200000
994198482 687493351 579440176 ...
view save

correct output
8
6
8
10
5
...
view save

user output
10
8
10
11
8
...
Truncated

Test 34

Group: 3

Verdict:

input
100000 200000
138644593 592364551 919805093 ...
view save

correct output
10
11
13
7
12
...
view save

user output
14
12
14
9
13
...
Truncated

Test 35

Group: 3

Verdict:

input
100000 200000
10770 195579 349462 442791 450...
view save

correct output
2468
1986
2632
129
4010
...
view save

user output
7156
1987
2633
130
4011
...
Truncated

Test 36

Group: 3

Verdict:

input
100000 200000
994198482 687493351 579440176 ...
view save

correct output
1
2
1
2
1
...
view save

user output
11
14
13
9
14
...
Truncated

Test 37

Group: 3

Verdict:

input
100000 200000
398809514 622635167 133376912 ...
view save

correct output
15
13
16
11
17
...
view save

user output
16
14
17
12
18
...
Truncated

Test 38

Group: 3

Verdict:

input
100000 200000
1000000000 1000000000 10000000...
view save

correct output
1
1
1
1
1
...
view save

user output
2
2
2
2
2
...
Truncated

Test 39

Group: 3

Verdict:

input
100000 200000
398809514 622635167 133376912 ...
view save

correct output
10
16
7
18
10
...
view save

user output
11
17
8
19
11
...
Truncated

Test 40

Group: 3

Verdict:

input
100000 200000
11465 15800 19042 19282 20348 ...
view save

correct output
99542
99728
99391
99890
99716
...
view save

user output
99926
99804
99773
99977
99749
...
Truncated

Test 41

Group: 3

Verdict:

input
99999 200000
587542096 890780320 258438313 ...
view save

correct output
8
6
11
11
17
...
view save

user output
9
8
13
12
19
...
Truncated

Test 42

Group: 3

Verdict:

input
100000 200000
11283 24634 28852 37453 37625 ...
view save

correct output
100000
100000
100000
100000
100000
...
view save

user output
100001
100001
100001
100001
100001
...
Truncated

Test 43

Group: 3

Verdict:

input
100000 200000
398809514 622635167 133376912 ...
view save

correct output
13
13
10
15
15
...
view save

user output
14
16
11
16
16
...
Truncated

Test 44

Group: 3

Verdict:

input
100000 200000
11465 15800 19042 19282 20348 ...
view save

correct output
36112
6013
51073
8123
82052
...
view save

user output
88750
54943
51208
48508
82356
...
Truncated

Test 45

Group: 3

Verdict:

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

correct output
99407
99529
99590
99589
99679
...
view save

user output
99497
99900
99823
99987
99918
...
Truncated

Test 46

Group: 3

Verdict:

input
100000 200000
100000 99999 99998 99997 99996...
view save

correct output
1
1
1
1
1
...
view save

user output
2
2
2
2
2
...
Truncated

Test 47

Group: 3

Verdict:

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

correct output
49946
49703
49786
49864
49720
...
view save

user output
49979
50001
49960
49902
49853
...
Truncated

Test 48

Group: 3

Verdict:

input
100000 200000
99999 100000 99997 99998 99995...
view save

correct output
2
1
2
2
1
...
view save

user output
4
3
4
4
3
...
Truncated

Test 49

Group: 3

Verdict:

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

correct output
3
3
3
3
2
...
view save

user output
4
4
4
4
3
...
Truncated

Test 50

Group: 3

Verdict:

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

correct output
19
23
2
21
4
...
view save

user output
20
24
3
22
5
...
Truncated

Test 51

Group: 3

Verdict:

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

correct output
112
237
49
141
57
...
view save

user output
113
238
50
142
58
...
Truncated

Test 52

Group: 3

Verdict:

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

correct output
2457
2199
2351
2450
2475
...
view save

user output
2458
2200
2352
2451
2476
...
Truncated

Test 53

Group: 3

Verdict:

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

correct output
24841
24973
24865
24823
24969
...
view save

user output
24842
24974
24866
24824
24970
...
Truncated

Test 54

Group: 3

Verdict:

input
100000 200000
49999 50000 49997 49998 49995 ...
view save

correct output
210
1
2
2
1
...
view save

user output
255
52
92
10
43
...
Truncated

Tasks

A Sum-B Bit string-C Sunset-D Binary tree-E Function-F Robot-G Classifier-

Submissions (elektrijanes)

2019-01-22 14:40:09 1002019-01-22 14:39:26 02019-01-22 14:37:26 162019-01-22 14:31:32 1002019-01-21 14:05:32 1002019-01-21 13:53:52 02019-01-21 13:21:04 512019-01-21 12:48:07 512019-01-21 12:44:31 162019-01-20 22:14:55 02019-01-20 21:52:54 02019-01-20 21:46:03 02019-01-20 21:39:58 02019-01-20 21:24:03 04:20:38 03:42:19 0