oj.uz

Submission #835287

# Submission time Handle Problem Language Result Execution time Memory
835287 2023-08-23T11:47:31 Z Wael Radio Towers (IOI22_towers) C++17
100 / 100
 1830 ms 675748 KB 
#include <bits/stdc++.h>
using namespace std;
#include "towers.h"
typedef int ll;
int const M = 2e5 + 10 , lg = 20 , Mx = M * 31;
int n , s[M] , Size = (1 << 30) , sparse[M][lg + 2] , Left[M] , Right[M];

struct sgtree {

    int Left[Mx] , Right[Mx] , cur = 1;
    vector<ll>elem[Mx];

    inline void Init() {
        for(int i = 0 ; i < Mx ; ++i) Left[i] = Right[i] = 0;
    } 

    inline void Update(int i , int val , int node = 1 , int lx = 1 , int rx = Size) {
        if(lx == rx) {
            elem[node].push_back(val);
            return;
        }
        int mid = (lx + rx) / 2;
        if(i <= mid) {
            if(Left[node] == 0) Left[node] = ++cur;
            Update(i , val , Left[node] , lx , mid);
        } else {
            if(Right[node] == 0) Right[node] = ++cur;
            Update(i , val , Right[node] , mid + 1 , rx);
        }
    }

    inline void Build(int node = 1 , int lx = 1 , int rx = Size) {
        if(node == 0 || lx == rx) return;
        int mid = (lx + rx) / 2;
        Build(Left[node] , lx , mid);
        Build(Right[node] , mid + 1 , rx);
        int l = 0 , r = 0;
        while(l < elem[Left[node]].size() || r < elem[Right[node]].size()) {
            if(l == elem[Left[node]].size()) {
                elem[node].push_back(elem[Right[node]][r]);
                ++r;
            }
            else if(r == elem[Right[node]].size()) {
                elem[node].push_back(elem[Left[node]][l]);
                ++l;
            }
            else if(elem[Left[node]][l] < elem[Right[node]][r]) {
                elem[node].push_back(elem[Left[node]][l]);
                ++l;
            }
            else {
                elem[node].push_back(elem[Right[node]][r]);
                ++r;
            }
        }
    }

    inline ll GetAfter(int i , int k , int node = 1 , int lx = 1 , int rx = Size) {
        if(rx < k || node == 0) return 1e9;
        if(lx >= k) {
            auto it = lower_bound(elem[node].begin() , elem[node].end() , i);
            if(it == elem[node].end()) return 1e9;
            return *it;
        }
        int mid = (lx + rx) / 2;
        return min(GetAfter(i , k , Left[node] , lx , mid) , GetAfter(i , k , Right[node] , mid + 1 , rx));
    }

    inline ll GetBefore(int i , int k , int node = 1 , int lx = 1 , int rx = Size) {
        if(rx < k || node == 0) return 0;
        if(lx >= k) {
            auto it = upper_bound(elem[node].begin() , elem[node].end() , i);
            if(it == elem[node].begin()) return 0;
            return *prev(it);
        }
        int mid = (lx + rx) / 2;
        return max(GetBefore(i , k , Left[node] , lx , mid) , GetBefore(i , k , Right[node] , mid + 1 , rx));
    }

    inline ll GetCount(int l , int r , int k , int node = 1 , int lx = 1 , int rx = Size) {
        if(rx < k || node == 0) return 0;
        if(lx >= k) {
            auto it1 = lower_bound(elem[node].begin() , elem[node].end() , l);
            auto it2 = upper_bound(elem[node].begin() , elem[node].end() , r);
            return it2 - it1;
        }
        int mid = (lx + rx) / 2;
        return GetCount(l , r , k , Left[node] , lx , mid) + GetCount(l , r , k , Right[node] , mid + 1 , rx);
    }
} Tree1 , Tree2 , Tree3;

inline ll GetMax(int l , int r) {
    if(r < l) return 0;
    int Lg = log2(r - l + 1);
    return max(sparse[l][Lg] , sparse[r - (1 << Lg) + 1][Lg]);
}

void init(int N, vector<ll> H) {
    n = N;
    Tree1.Init();
    Tree2.Init();
    Tree3.Init();
    for(int i = 1 ; i <= n ; ++i) s[i] = H[i - 1];
    for(int i = 1 ; i <= n ; ++i) sparse[i][0] = s[i];
    for(int j = 1 ; j <= lg ; ++j) 
     for(int i = 1 ; i <= n ; ++i) {
        int After = min(n , i + (1 << (j - 1)));
        sparse[i][j] = max(sparse[i][j - 1] , sparse[After][j - 1]);
     }

    stack<ll>st;
    for(int i = 1 ; i <= n ; ++i) {
        while(st.size() && s[i] < s[st.top()]) {
            Right[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }
    while(st.size()) {
        Right[st.top()] = n + 1;
        st.pop(); 
    }

    for(int i = n ; i >= 1 ; --i) {
        while(st.size() && s[i] < s[st.top()]) {
            Left[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }
    while(st.size()) {
        Left[st.top()] = 0;
        st.pop();
    }

    //for(int i = 1 ; i <= n ; ++i) cout << Left[i] << " " << Right[i] << endl;

    for(int i = 1 ; i <= n ; ++i) {
        int max1 = GetMax(Left[i] + 1 , i - 1);
        int max2 = GetMax(i + 1 , Right[i] - 1);
        if(max1 > s[i]) {
            Tree2.Update(max1 - s[i] , i);
        }
        if(max2 > s[i]) {
            Tree1.Update(max2 - s[i] , i);
        }
        if(max1 > s[i] && max2 > s[i]) {
            Tree3.Update(min(max1 , max2) - s[i] , i);
        }
    }
    Tree1.Build();
    Tree2.Build();
    Tree3.Build();
}

int max_towers(int L, int R, int D) {
    int k = D;
    ++L , ++R;
    int l = Tree1.GetAfter(L , k);
    int r = Tree2.GetBefore(R , k);
    if(r < l) return 1;
    int cnt =  Tree3.GetCount(l + 1 , r - 1 , k);
    return cnt + 2;
}

Compilation message

towers.cpp: In member function 'void sgtree::Build(int, int, int)':
towers.cpp:38:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         while(l < elem[Left[node]].size() || r < elem[Right[node]].size()) {
      |               ~~^~~~~~~~~~~~~~~~~~~~~~~~~
towers.cpp:38:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         while(l < elem[Left[node]].size() || r < elem[Right[node]].size()) {
      |                                              ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
towers.cpp:39:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |             if(l == elem[Left[node]].size()) {
      |                ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
towers.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             else if(r == elem[Right[node]].size()) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 622432 KB Output is correct
2 Correct 1119 ms 646128 KB Output is correct
3 Correct 1295 ms 645880 KB Output is correct
4 Correct 1133 ms 645472 KB Output is correct
5 Correct 1192 ms 645556 KB Output is correct
6 Correct 934 ms 645248 KB Output is correct
7 Correct 1093 ms 645484 KB Output is correct
8 Correct 226 ms 582672 KB Output is correct
9 Correct 222 ms 584272 KB Output is correct
10 Correct 222 ms 584188 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 583172 KB Output is correct
2 Correct 227 ms 584788 KB Output is correct
3 Correct 231 ms 584708 KB Output is correct
4 Correct 235 ms 584968 KB Output is correct
5 Correct 225 ms 585016 KB Output is correct
6 Correct 226 ms 584908 KB Output is correct
7 Correct 230 ms 585048 KB Output is correct
8 Correct 227 ms 584292 KB Output is correct
9 Correct 224 ms 584280 KB Output is correct
10 Correct 227 ms 584268 KB Output is correct
11 Correct 222 ms 584128 KB Output is correct
12 Correct 223 ms 582608 KB Output is correct
13 Correct 225 ms 584312 KB Output is correct
14 Correct 225 ms 584256 KB Output is correct
15 Correct 229 ms 584736 KB Output is correct
16 Correct 225 ms 585032 KB Output is correct
17 Correct 228 ms 584924 KB Output is correct
18 Correct 225 ms 584256 KB Output is correct
19 Correct 228 ms 584288 KB Output is correct
20 Correct 233 ms 584748 KB Output is correct
21 Correct 226 ms 584908 KB Output is correct
22 Correct 232 ms 584980 KB Output is correct
23 Correct 227 ms 584288 KB Output is correct
24 Correct 225 ms 584252 KB Output is correct
25 Correct 222 ms 583684 KB Output is correct
26 Correct 224 ms 584692 KB Output is correct
27 Correct 227 ms 584792 KB Output is correct
28 Correct 232 ms 585008 KB Output is correct
29 Correct 225 ms 584948 KB Output is correct
30 Correct 226 ms 585004 KB Output is correct
31 Correct 228 ms 584908 KB Output is correct
32 Correct 248 ms 584236 KB Output is correct
33 Correct 226 ms 584260 KB Output is correct
34 Correct 226 ms 584160 KB Output is correct
35 Correct 226 ms 584204 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 583172 KB Output is correct
2 Correct 227 ms 584788 KB Output is correct
3 Correct 231 ms 584708 KB Output is correct
4 Correct 235 ms 584968 KB Output is correct
5 Correct 225 ms 585016 KB Output is correct
6 Correct 226 ms 584908 KB Output is correct
7 Correct 230 ms 585048 KB Output is correct
8 Correct 227 ms 584292 KB Output is correct
9 Correct 224 ms 584280 KB Output is correct
10 Correct 227 ms 584268 KB Output is correct
11 Correct 222 ms 584128 KB Output is correct
12 Correct 223 ms 582608 KB Output is correct
13 Correct 225 ms 584312 KB Output is correct
14 Correct 225 ms 584256 KB Output is correct
15 Correct 229 ms 584736 KB Output is correct
16 Correct 225 ms 585032 KB Output is correct
17 Correct 228 ms 584924 KB Output is correct
18 Correct 225 ms 584256 KB Output is correct
19 Correct 228 ms 584288 KB Output is correct
20 Correct 233 ms 584748 KB Output is correct
21 Correct 226 ms 584908 KB Output is correct
22 Correct 232 ms 584980 KB Output is correct
23 Correct 227 ms 584288 KB Output is correct
24 Correct 225 ms 584252 KB Output is correct
25 Correct 222 ms 583684 KB Output is correct
26 Correct 224 ms 584692 KB Output is correct
27 Correct 227 ms 584792 KB Output is correct
28 Correct 232 ms 585008 KB Output is correct
29 Correct 225 ms 584948 KB Output is correct
30 Correct 226 ms 585004 KB Output is correct
31 Correct 228 ms 584908 KB Output is correct
32 Correct 248 ms 584236 KB Output is correct
33 Correct 226 ms 584260 KB Output is correct
34 Correct 226 ms 584160 KB Output is correct
35 Correct 226 ms 584204 KB Output is correct
36 Correct 430 ms 639548 KB Output is correct
37 Correct 560 ms 667232 KB Output is correct
38 Correct 558 ms 667112 KB Output is correct
39 Correct 624 ms 675672 KB Output is correct
40 Correct 611 ms 675732 KB Output is correct
41 Correct 606 ms 675636 KB Output is correct
42 Correct 621 ms 675652 KB Output is correct
43 Correct 364 ms 645464 KB Output is correct
44 Correct 382 ms 645348 KB Output is correct
45 Correct 378 ms 643656 KB Output is correct
46 Correct 386 ms 643848 KB Output is correct
47 Correct 575 ms 667096 KB Output is correct
48 Correct 616 ms 675688 KB Output is correct
49 Correct 599 ms 675652 KB Output is correct
50 Correct 392 ms 645372 KB Output is correct
51 Correct 364 ms 645324 KB Output is correct
52 Correct 562 ms 667132 KB Output is correct
53 Correct 614 ms 675704 KB Output is correct
54 Correct 613 ms 675612 KB Output is correct
55 Correct 386 ms 645456 KB Output is correct
56 Correct 374 ms 642936 KB Output is correct
57 Correct 550 ms 664440 KB Output is correct
58 Correct 569 ms 667104 KB Output is correct
59 Correct 562 ms 667308 KB Output is correct
60 Correct 621 ms 675672 KB Output is correct
61 Correct 596 ms 675632 KB Output is correct
62 Correct 618 ms 675620 KB Output is correct
63 Correct 606 ms 675652 KB Output is correct
64 Correct 363 ms 645380 KB Output is correct
65 Correct 388 ms 645452 KB Output is correct
66 Correct 374 ms 643516 KB Output is correct
67 Correct 383 ms 645164 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1123 ms 666500 KB Output is correct
2 Correct 1230 ms 667160 KB Output is correct
3 Correct 1351 ms 667212 KB Output is correct
4 Correct 1361 ms 675724 KB Output is correct
5 Correct 1224 ms 675672 KB Output is correct
6 Correct 1166 ms 675724 KB Output is correct
7 Correct 1275 ms 675588 KB Output is correct
8 Correct 1139 ms 645488 KB Output is correct
9 Correct 881 ms 645488 KB Output is correct
10 Correct 1114 ms 643940 KB Output is correct
11 Correct 1193 ms 643968 KB Output is correct
12 Correct 1010 ms 645244 KB Output is correct
13 Correct 1004 ms 645392 KB Output is correct
14 Correct 228 ms 582616 KB Output is correct
15 Correct 234 ms 584244 KB Output is correct
16 Correct 228 ms 584492 KB Output is correct
17 Correct 564 ms 667152 KB Output is correct
18 Correct 615 ms 675720 KB Output is correct
19 Correct 611 ms 675748 KB Output is correct
20 Correct 384 ms 645540 KB Output is correct
21 Correct 364 ms 645368 KB Output is correct
22 Correct 575 ms 667016 KB Output is correct
23 Correct 774 ms 675624 KB Output is correct
24 Correct 610 ms 675576 KB Output is correct
25 Correct 385 ms 645560 KB Output is correct
26 Correct 374 ms 642900 KB Output is correct
27 Correct 234 ms 584792 KB Output is correct
28 Correct 233 ms 584924 KB Output is correct
29 Correct 227 ms 584992 KB Output is correct
30 Correct 230 ms 584264 KB Output is correct
31 Correct 229 ms 584276 KB Output is correct
32 Correct 227 ms 584776 KB Output is correct
33 Correct 229 ms 584920 KB Output is correct
34 Correct 230 ms 584904 KB Output is correct
35 Correct 229 ms 584224 KB Output is correct
36 Correct 228 ms 584200 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 609 ms 604592 KB Output is correct
2 Correct 1617 ms 667064 KB Output is correct
3 Correct 1510 ms 667136 KB Output is correct
4 Correct 1660 ms 675608 KB Output is correct
5 Correct 1585 ms 675692 KB Output is correct
6 Correct 1637 ms 675632 KB Output is correct
7 Correct 1639 ms 675724 KB Output is correct
8 Correct 1077 ms 645476 KB Output is correct
9 Correct 1192 ms 645492 KB Output is correct
10 Correct 1155 ms 644104 KB Output is correct
11 Correct 1039 ms 644536 KB Output is correct
12 Correct 748 ms 667228 KB Output is correct
13 Correct 599 ms 675688 KB Output is correct
14 Correct 637 ms 675572 KB Output is correct
15 Correct 385 ms 645396 KB Output is correct
16 Correct 376 ms 642988 KB Output is correct
17 Correct 552 ms 664348 KB Output is correct
18 Correct 568 ms 667204 KB Output is correct
19 Correct 570 ms 667148 KB Output is correct
20 Correct 621 ms 675656 KB Output is correct
21 Correct 617 ms 675652 KB Output is correct
22 Correct 609 ms 675688 KB Output is correct
23 Correct 600 ms 675636 KB Output is correct
24 Correct 366 ms 645504 KB Output is correct
25 Correct 381 ms 645412 KB Output is correct
26 Correct 370 ms 643464 KB Output is correct
27 Correct 379 ms 645188 KB Output is correct
28 Correct 231 ms 584708 KB Output is correct
29 Correct 230 ms 585192 KB Output is correct
30 Correct 231 ms 584924 KB Output is correct
31 Correct 226 ms 584296 KB Output is correct
32 Correct 227 ms 584216 KB Output is correct
33 Correct 235 ms 583644 KB Output is correct
34 Correct 231 ms 584756 KB Output is correct
35 Correct 239 ms 585000 KB Output is correct
36 Correct 229 ms 584904 KB Output is correct
37 Correct 228 ms 584960 KB Output is correct
38 Correct 231 ms 585016 KB Output is correct
39 Correct 229 ms 584936 KB Output is correct
40 Correct 225 ms 584244 KB Output is correct
41 Correct 229 ms 584288 KB Output is correct
42 Correct 224 ms 584244 KB Output is correct
43 Correct 228 ms 584160 KB Output is correct

Subtask #6
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 583172 KB Output is correct
2 Correct 227 ms 584788 KB Output is correct
3 Correct 231 ms 584708 KB Output is correct
4 Correct 235 ms 584968 KB Output is correct
5 Correct 225 ms 585016 KB Output is correct
6 Correct 226 ms 584908 KB Output is correct
7 Correct 230 ms 585048 KB Output is correct
8 Correct 227 ms 584292 KB Output is correct
9 Correct 224 ms 584280 KB Output is correct
10 Correct 227 ms 584268 KB Output is correct
11 Correct 222 ms 584128 KB Output is correct
12 Correct 223 ms 582608 KB Output is correct
13 Correct 225 ms 584312 KB Output is correct
14 Correct 225 ms 584256 KB Output is correct
15 Correct 229 ms 584736 KB Output is correct
16 Correct 225 ms 585032 KB Output is correct
17 Correct 228 ms 584924 KB Output is correct
18 Correct 225 ms 584256 KB Output is correct
19 Correct 228 ms 584288 KB Output is correct
20 Correct 233 ms 584748 KB Output is correct
21 Correct 226 ms 584908 KB Output is correct
22 Correct 232 ms 584980 KB Output is correct
23 Correct 227 ms 584288 KB Output is correct
24 Correct 225 ms 584252 KB Output is correct
25 Correct 222 ms 583684 KB Output is correct
26 Correct 224 ms 584692 KB Output is correct
27 Correct 227 ms 584792 KB Output is correct
28 Correct 232 ms 585008 KB Output is correct
29 Correct 225 ms 584948 KB Output is correct
30 Correct 226 ms 585004 KB Output is correct
31 Correct 228 ms 584908 KB Output is correct
32 Correct 248 ms 584236 KB Output is correct
33 Correct 226 ms 584260 KB Output is correct
34 Correct 226 ms 584160 KB Output is correct
35 Correct 226 ms 584204 KB Output is correct
36 Correct 430 ms 639548 KB Output is correct
37 Correct 560 ms 667232 KB Output is correct
38 Correct 558 ms 667112 KB Output is correct
39 Correct 624 ms 675672 KB Output is correct
40 Correct 611 ms 675732 KB Output is correct
41 Correct 606 ms 675636 KB Output is correct
42 Correct 621 ms 675652 KB Output is correct
43 Correct 364 ms 645464 KB Output is correct
44 Correct 382 ms 645348 KB Output is correct
45 Correct 378 ms 643656 KB Output is correct
46 Correct 386 ms 643848 KB Output is correct
47 Correct 575 ms 667096 KB Output is correct
48 Correct 616 ms 675688 KB Output is correct
49 Correct 599 ms 675652 KB Output is correct
50 Correct 392 ms 645372 KB Output is correct
51 Correct 364 ms 645324 KB Output is correct
52 Correct 562 ms 667132 KB Output is correct
53 Correct 614 ms 675704 KB Output is correct
54 Correct 613 ms 675612 KB Output is correct
55 Correct 386 ms 645456 KB Output is correct
56 Correct 374 ms 642936 KB Output is correct
57 Correct 550 ms 664440 KB Output is correct
58 Correct 569 ms 667104 KB Output is correct
59 Correct 562 ms 667308 KB Output is correct
60 Correct 621 ms 675672 KB Output is correct
61 Correct 596 ms 675632 KB Output is correct
62 Correct 618 ms 675620 KB Output is correct
63 Correct 606 ms 675652 KB Output is correct
64 Correct 363 ms 645380 KB Output is correct
65 Correct 388 ms 645452 KB Output is correct
66 Correct 374 ms 643516 KB Output is correct
67 Correct 383 ms 645164 KB Output is correct
68 Correct 1123 ms 666500 KB Output is correct
69 Correct 1230 ms 667160 KB Output is correct
70 Correct 1351 ms 667212 KB Output is correct
71 Correct 1361 ms 675724 KB Output is correct
72 Correct 1224 ms 675672 KB Output is correct
73 Correct 1166 ms 675724 KB Output is correct
74 Correct 1275 ms 675588 KB Output is correct
75 Correct 1139 ms 645488 KB Output is correct
76 Correct 881 ms 645488 KB Output is correct
77 Correct 1114 ms 643940 KB Output is correct
78 Correct 1193 ms 643968 KB Output is correct
79 Correct 1010 ms 645244 KB Output is correct
80 Correct 1004 ms 645392 KB Output is correct
81 Correct 228 ms 582616 KB Output is correct
82 Correct 234 ms 584244 KB Output is correct
83 Correct 228 ms 584492 KB Output is correct
84 Correct 564 ms 667152 KB Output is correct
85 Correct 615 ms 675720 KB Output is correct
86 Correct 611 ms 675748 KB Output is correct
87 Correct 384 ms 645540 KB Output is correct
88 Correct 364 ms 645368 KB Output is correct
89 Correct 575 ms 667016 KB Output is correct
90 Correct 774 ms 675624 KB Output is correct
91 Correct 610 ms 675576 KB Output is correct
92 Correct 385 ms 645560 KB Output is correct
93 Correct 374 ms 642900 KB Output is correct
94 Correct 234 ms 584792 KB Output is correct
95 Correct 233 ms 584924 KB Output is correct
96 Correct 227 ms 584992 KB Output is correct
97 Correct 230 ms 584264 KB Output is correct
98 Correct 229 ms 584276 KB Output is correct
99 Correct 227 ms 584776 KB Output is correct
100 Correct 229 ms 584920 KB Output is correct
101 Correct 230 ms 584904 KB Output is correct
102 Correct 229 ms 584224 KB Output is correct
103 Correct 228 ms 584200 KB Output is correct
104 Correct 1222 ms 658180 KB Output is correct
105 Correct 1445 ms 667076 KB Output is correct
106 Correct 1530 ms 667116 KB Output is correct
107 Correct 1413 ms 675748 KB Output is correct
108 Correct 1457 ms 675624 KB Output is correct
109 Correct 1493 ms 675652 KB Output is correct
110 Correct 1520 ms 675620 KB Output is correct
111 Correct 1093 ms 645488 KB Output is correct
112 Correct 1037 ms 645404 KB Output is correct
113 Correct 1067 ms 643356 KB Output is correct
114 Correct 1029 ms 645028 KB Output is correct

Subtask #7
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 622432 KB Output is correct
2 Correct 1119 ms 646128 KB Output is correct
3 Correct 1295 ms 645880 KB Output is correct
4 Correct 1133 ms 645472 KB Output is correct
5 Correct 1192 ms 645556 KB Output is correct
6 Correct 934 ms 645248 KB Output is correct
7 Correct 1093 ms 645484 KB Output is correct
8 Correct 226 ms 582672 KB Output is correct
9 Correct 222 ms 584272 KB Output is correct
10 Correct 222 ms 584188 KB Output is correct
11 Correct 231 ms 583172 KB Output is correct
12 Correct 227 ms 584788 KB Output is correct
13 Correct 231 ms 584708 KB Output is correct
14 Correct 235 ms 584968 KB Output is correct
15 Correct 225 ms 585016 KB Output is correct
16 Correct 226 ms 584908 KB Output is correct
17 Correct 230 ms 585048 KB Output is correct
18 Correct 227 ms 584292 KB Output is correct
19 Correct 224 ms 584280 KB Output is correct
20 Correct 227 ms 584268 KB Output is correct
21 Correct 222 ms 584128 KB Output is correct
22 Correct 223 ms 582608 KB Output is correct
23 Correct 225 ms 584312 KB Output is correct
24 Correct 225 ms 584256 KB Output is correct
25 Correct 229 ms 584736 KB Output is correct
26 Correct 225 ms 585032 KB Output is correct
27 Correct 228 ms 584924 KB Output is correct
28 Correct 225 ms 584256 KB Output is correct
29 Correct 228 ms 584288 KB Output is correct
30 Correct 233 ms 584748 KB Output is correct
31 Correct 226 ms 584908 KB Output is correct
32 Correct 232 ms 584980 KB Output is correct
33 Correct 227 ms 584288 KB Output is correct
34 Correct 225 ms 584252 KB Output is correct
35 Correct 222 ms 583684 KB Output is correct
36 Correct 224 ms 584692 KB Output is correct
37 Correct 227 ms 584792 KB Output is correct
38 Correct 232 ms 585008 KB Output is correct
39 Correct 225 ms 584948 KB Output is correct
40 Correct 226 ms 585004 KB Output is correct
41 Correct 228 ms 584908 KB Output is correct
42 Correct 248 ms 584236 KB Output is correct
43 Correct 226 ms 584260 KB Output is correct
44 Correct 226 ms 584160 KB Output is correct
45 Correct 226 ms 584204 KB Output is correct
46 Correct 430 ms 639548 KB Output is correct
47 Correct 560 ms 667232 KB Output is correct
48 Correct 558 ms 667112 KB Output is correct
49 Correct 624 ms 675672 KB Output is correct
50 Correct 611 ms 675732 KB Output is correct
51 Correct 606 ms 675636 KB Output is correct
52 Correct 621 ms 675652 KB Output is correct
53 Correct 364 ms 645464 KB Output is correct
54 Correct 382 ms 645348 KB Output is correct
55 Correct 378 ms 643656 KB Output is correct
56 Correct 386 ms 643848 KB Output is correct
57 Correct 575 ms 667096 KB Output is correct
58 Correct 616 ms 675688 KB Output is correct
59 Correct 599 ms 675652 KB Output is correct
60 Correct 392 ms 645372 KB Output is correct
61 Correct 364 ms 645324 KB Output is correct
62 Correct 562 ms 667132 KB Output is correct
63 Correct 614 ms 675704 KB Output is correct
64 Correct 613 ms 675612 KB Output is correct
65 Correct 386 ms 645456 KB Output is correct
66 Correct 374 ms 642936 KB Output is correct
67 Correct 550 ms 664440 KB Output is correct
68 Correct 569 ms 667104 KB Output is correct
69 Correct 562 ms 667308 KB Output is correct
70 Correct 621 ms 675672 KB Output is correct
71 Correct 596 ms 675632 KB Output is correct
72 Correct 618 ms 675620 KB Output is correct
73 Correct 606 ms 675652 KB Output is correct
74 Correct 363 ms 645380 KB Output is correct
75 Correct 388 ms 645452 KB Output is correct
76 Correct 374 ms 643516 KB Output is correct
77 Correct 383 ms 645164 KB Output is correct
78 Correct 1123 ms 666500 KB Output is correct
79 Correct 1230 ms 667160 KB Output is correct
80 Correct 1351 ms 667212 KB Output is correct
81 Correct 1361 ms 675724 KB Output is correct
82 Correct 1224 ms 675672 KB Output is correct
83 Correct 1166 ms 675724 KB Output is correct
84 Correct 1275 ms 675588 KB Output is correct
85 Correct 1139 ms 645488 KB Output is correct
86 Correct 881 ms 645488 KB Output is correct
87 Correct 1114 ms 643940 KB Output is correct
88 Correct 1193 ms 643968 KB Output is correct
89 Correct 1010 ms 645244 KB Output is correct
90 Correct 1004 ms 645392 KB Output is correct
91 Correct 228 ms 582616 KB Output is correct
92 Correct 234 ms 584244 KB Output is correct
93 Correct 228 ms 584492 KB Output is correct
94 Correct 564 ms 667152 KB Output is correct
95 Correct 615 ms 675720 KB Output is correct
96 Correct 611 ms 675748 KB Output is correct
97 Correct 384 ms 645540 KB Output is correct
98 Correct 364 ms 645368 KB Output is correct
99 Correct 575 ms 667016 KB Output is correct
100 Correct 774 ms 675624 KB Output is correct
101 Correct 610 ms 675576 KB Output is correct
102 Correct 385 ms 645560 KB Output is correct
103 Correct 374 ms 642900 KB Output is correct
104 Correct 234 ms 584792 KB Output is correct
105 Correct 233 ms 584924 KB Output is correct
106 Correct 227 ms 584992 KB Output is correct
107 Correct 230 ms 584264 KB Output is correct
108 Correct 229 ms 584276 KB Output is correct
109 Correct 227 ms 584776 KB Output is correct
110 Correct 229 ms 584920 KB Output is correct
111 Correct 230 ms 584904 KB Output is correct
112 Correct 229 ms 584224 KB Output is correct
113 Correct 228 ms 584200 KB Output is correct
114 Correct 609 ms 604592 KB Output is correct
115 Correct 1617 ms 667064 KB Output is correct
116 Correct 1510 ms 667136 KB Output is correct
117 Correct 1660 ms 675608 KB Output is correct
118 Correct 1585 ms 675692 KB Output is correct
119 Correct 1637 ms 675632 KB Output is correct
120 Correct 1639 ms 675724 KB Output is correct
121 Correct 1077 ms 645476 KB Output is correct
122 Correct 1192 ms 645492 KB Output is correct
123 Correct 1155 ms 644104 KB Output is correct
124 Correct 1039 ms 644536 KB Output is correct
125 Correct 748 ms 667228 KB Output is correct
126 Correct 599 ms 675688 KB Output is correct
127 Correct 637 ms 675572 KB Output is correct
128 Correct 385 ms 645396 KB Output is correct
129 Correct 376 ms 642988 KB Output is correct
130 Correct 552 ms 664348 KB Output is correct
131 Correct 568 ms 667204 KB Output is correct
132 Correct 570 ms 667148 KB Output is correct
133 Correct 621 ms 675656 KB Output is correct
134 Correct 617 ms 675652 KB Output is correct
135 Correct 609 ms 675688 KB Output is correct
136 Correct 600 ms 675636 KB Output is correct
137 Correct 366 ms 645504 KB Output is correct
138 Correct 381 ms 645412 KB Output is correct
139 Correct 370 ms 643464 KB Output is correct
140 Correct 379 ms 645188 KB Output is correct
141 Correct 231 ms 584708 KB Output is correct
142 Correct 230 ms 585192 KB Output is correct
143 Correct 231 ms 584924 KB Output is correct
144 Correct 226 ms 584296 KB Output is correct
145 Correct 227 ms 584216 KB Output is correct
146 Correct 235 ms 583644 KB Output is correct
147 Correct 231 ms 584756 KB Output is correct
148 Correct 239 ms 585000 KB Output is correct
149 Correct 229 ms 584904 KB Output is correct
150 Correct 228 ms 584960 KB Output is correct
151 Correct 231 ms 585016 KB Output is correct
152 Correct 229 ms 584936 KB Output is correct
153 Correct 225 ms 584244 KB Output is correct
154 Correct 229 ms 584288 KB Output is correct
155 Correct 224 ms 584244 KB Output is correct
156 Correct 228 ms 584160 KB Output is correct
157 Correct 1222 ms 658180 KB Output is correct
158 Correct 1445 ms 667076 KB Output is correct
159 Correct 1530 ms 667116 KB Output is correct
160 Correct 1413 ms 675748 KB Output is correct
161 Correct 1457 ms 675624 KB Output is correct
162 Correct 1493 ms 675652 KB Output is correct
163 Correct 1520 ms 675620 KB Output is correct
164 Correct 1093 ms 645488 KB Output is correct
165 Correct 1037 ms 645404 KB Output is correct
166 Correct 1067 ms 643356 KB Output is correct
167 Correct 1029 ms 645028 KB Output is correct
168 Correct 225 ms 582712 KB Output is correct
169 Correct 911 ms 614304 KB Output is correct
170 Correct 1817 ms 666996 KB Output is correct
171 Correct 1718 ms 667056 KB Output is correct
172 Correct 1818 ms 675716 KB Output is correct
173 Correct 1785 ms 675660 KB Output is correct
174 Correct 1740 ms 675672 KB Output is correct
175 Correct 1830 ms 675736 KB Output is correct
176 Correct 1104 ms 645460 KB Output is correct
177 Correct 1191 ms 645440 KB Output is correct
178 Correct 1324 ms 644932 KB Output is correct
179 Correct 1159 ms 642676 KB Output is correct