oj.uz

답안 #719697

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
719697 2023-04-06T13:50:45 Z somethingnew 송신탑 (IOI22_towers) C++17
60 / 100
 4000 ms 132780 KB 
//  ↘ ⬇ ⬇ ⬇ ⬇ ⬇ ↙
//  ➡ @roadfromroi ⬅
//  ↗ ⬆ ⬆ ⬆ ⬆ ⬆ ↖
#include <iostream>
#include "vector"
#include "algorithm"
#include "numeric"
#include "climits"
#include "iomanip"
#include "bitset"
#include "cmath"
#include "map"
#include "deque"
#include "array"
#include "set"
#include "queue"
//#include "towers.h"
#define all(x) x.begin(), x.end()
using namespace std;

vector<int> h;
int dd;
struct node {
    int lval;
    int rval;
    int cnt;
    int lstenka;
    int rstenka;
    node() {}
    node(int x) {
        lval = rval = x;
        cnt = 1;
        lstenka = 0;
        rstenka = 0;
    }
};

void merge(node &a, node b) {
    if (a.rval <= b.lval) {
        if (max(a.rstenka, b.lstenka) - dd >= max(a.rval, b.lval)) {
            a.cnt = a.cnt + b.cnt;
            a.rstenka = b.rstenka;
            a.rval = b.rval;
            return;
        } else {
            a.cnt = a.cnt + b.cnt - 1;
            if (b.cnt != 1) {
                a.rstenka = b.rstenka;
                a.rval = b.rval;
            } else {
                //  cout << c.rstenka << ' ';
                a.rstenka = max(a.rstenka, max(b.rstenka, max(b.lstenka, b.rval)));
                //  cout << c.rstenka << '\n';
            }
            return;
        }
    } else {
        if (max(a.rstenka, b.lstenka) - dd >= max(a.rval, b.lval)) {
            b.cnt = a.cnt + b.cnt;
            b.lstenka = a.lstenka;
            b.lval = a.lval;
            swap(a, b);
            return;
        } else {
            b.cnt = a.cnt + b.cnt - 1;
            if (a.cnt != 1) {
                b.lstenka = a.lstenka;
                b.lval = a.lval;
            } else {
                //  cout << c.rstenka << ' ';
                b.lstenka = max(b.lstenka, max(a.lstenka, max(a.rstenka, a.lval)));
                //  cout << c.rstenka << '\n';
            }
            swap(a, b);
            return;
        }
    }
}
struct kornihunka{
    vector<int> elems;
    node nd;
    void push(int x) {
        elems.push_back(x);
    }
    node get(int l, int r) {
        r = min(r, (int)elems.size() - 1);
        node nres(elems[l]);
        for (int i = l + 1; i <= r; ++i) {
            merge(nres, node(elems[i]));
        }
        return nres;
    }
    int calc() {
        int incdd = -1;
        nd = node(elems[0]);
        int cc = 1;
        int pr3 = 2e9;
        for (int i = 1; i < elems.size(); ++i) {
            int pr = nd.rval, pr2 = nd.rstenka;
            merge(nd, elems[i]);
            if (nd.cnt != cc) {
                cc = nd.cnt;
                if (incdd == -1)
                    incdd = min(pr2 - dd - pr, pr3 - dd - pr);
                incdd = min(incdd, min(pr2 - dd - pr, pr3 - dd - pr));
                pr3 = pr2;
            }
        }
        incdd = min(incdd, pr3 - dd - nd.rval);
        if (nd.cnt == 1)
            return 0;
        return incdd + 1;
    }
    node getnode() {
        return nd;
    }
};
const int K = 330;
const int N = 100000;
vector<vector<kornihunka>> vecnode;
vector<vector<int>> detki;
int realdetki[N / K + 1][N];
vector<int> alex;
int calcedd = 0;
void init(int n, vector<int> hh) {
    h = hh;
    vecnode.assign((n + K - 1) / K, vector<kornihunka>(K));
    detki.assign((n + K - 1) / K, {});
    for (int i = 0; i < n; ++i) {
        vecnode[i/K][0].push(h[i]);
    }
    for (int i = 0; i < vecnode.size(); ++i) {
        int j = 0;
        int inc = 1;
        dd = 0;
        do {
            dd += inc;
            detki[i].push_back(dd);
            alex.push_back(dd);
            vecnode[i][j + 1] = vecnode[i][j];
            inc = vecnode[i][j].calc();
            j++;
        } while (inc != 0);
    }
    sort(all(alex));
    alex.erase(unique(all(alex)), alex.end());
    for (int i = 0; i < vecnode.size(); ++i) {
        int j = 0;
        for (int pvl = 0; pvl < alex.size(); ++pvl) {
            while (j + 1 != detki[i].size() and detki[i][j + 1] <= alex[pvl]) {
                j++;
            }
            realdetki[i][pvl] = j;
        }
    }
}
int max_towers(int L, int R, int D) {
    node res(2e9);
    dd = D;
    int dvl = upper_bound(all(alex), dd) - alex.begin()-1;
    if (L / K == R / K) {
        //cout << upper_bound(all(detki[L/K]), dd) - detki[L/K].begin()-1 << '\n';
        //     cout << res.rval << ' ' << res.rstenka << ' ' << res.cnt << '\n';
        merge(res, vecnode[L/K][realdetki[L/K][dvl]].get(L % K, R % K));
        return res.cnt;
    }
    if (L % K != 0) {
        //  cout << res.rval << ' ' << res.rstenka << ' ' << res.cnt << '\n';
        merge(res, vecnode[L/K][realdetki[L/K][dvl]].get(L % K, K - 1));
        L = L / K * K + K;
    }
    while (L + K <= R + 1) {
        //cout << "TT " << res.rval << ' ' << res.rstenka << ' ' << res.cnt << '\n';
        node res2 = vecnode[L/K][0].getnode();
        //cout << "TT2 " << res2.lval << ' ' << res2.lstenka << ' ' << res2.cnt << '\n';
        merge(res, vecnode[L/K][realdetki[L/K][dvl]].getnode());
        //cout << "TT3 " << res.rval << ' ' << res.rstenka << ' ' << res.cnt << '\n';

        L += K;
    }
    if (L <= R) {
        // cout << res.rval << ' ' << res.rstenka << ' ' << res.cnt << '\n';
        merge(res, vecnode[L/K][realdetki[L/K][dvl]].get(L % K, R % K));
    }
    // cout << res.rval << ' ' << res.rstenka << ' ' << res.cnt << '\n';
    return res.cnt;
}
/*
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    init(n, a);
    for (int i = 0; i < m; ++i) {
        int q1, q2, q3;
        cin >> q1 >> q2 >> q3;
        cout << max_towers(q1,q2,q3) << '\n';
    }
}*/
/*
7 1
10 20 60 40 50 30 70
0 6 17
 */

Compilation message

towers.cpp: In member function 'int kornihunka::calc()':
towers.cpp:98:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         for (int i = 1; i < elems.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~
towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:132:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<kornihunka> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |     for (int i = 0; i < vecnode.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~~
towers.cpp:147:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<kornihunka> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |     for (int i = 0; i < vecnode.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~~
towers.cpp:149:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |         for (int pvl = 0; pvl < alex.size(); ++pvl) {
      |                           ~~~~^~~~~~~~~~~~~
towers.cpp:150:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |             while (j + 1 != detki[i].size() and detki[i][j + 1] <= alex[pvl]) {
      |                    ~~~~~~^~~~~~~~~~~~~~~~~~
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:174:14: warning: variable 'res2' set but not used [-Wunused-but-set-variable]
  174 |         node res2 = vecnode[L/K][0].getnode();
      |              ^~~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 783 ms 5284 KB Output is correct
2 Correct 1683 ms 8616 KB Output is correct
3 Correct 1475 ms 8740 KB Output is correct
4 Correct 1638 ms 8640 KB Output is correct
5 Correct 2001 ms 8696 KB Output is correct
6 Correct 1509 ms 8664 KB Output is correct
7 Correct 1693 ms 8644 KB Output is correct
8 Correct 0 ms 336 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Correct 1 ms 464 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 5 ms 1284 KB Output is correct
3 Correct 7 ms 1284 KB Output is correct
4 Correct 9 ms 1688 KB Output is correct
5 Correct 8 ms 1792 KB Output is correct
6 Correct 9 ms 1796 KB Output is correct
7 Correct 8 ms 1720 KB Output is correct
8 Correct 1 ms 464 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 1 ms 464 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 464 KB Output is correct
14 Correct 1 ms 464 KB Output is correct
15 Correct 5 ms 1360 KB Output is correct
16 Correct 8 ms 1744 KB Output is correct
17 Correct 10 ms 1744 KB Output is correct
18 Correct 1 ms 464 KB Output is correct
19 Correct 1 ms 464 KB Output is correct
20 Correct 6 ms 1360 KB Output is correct
21 Correct 11 ms 1728 KB Output is correct
22 Correct 8 ms 1744 KB Output is correct
23 Correct 1 ms 464 KB Output is correct
24 Correct 1 ms 464 KB Output is correct
25 Correct 2 ms 720 KB Output is correct
26 Correct 5 ms 1360 KB Output is correct
27 Correct 6 ms 1232 KB Output is correct
28 Correct 7 ms 1744 KB Output is correct
29 Correct 8 ms 1744 KB Output is correct
30 Correct 10 ms 1744 KB Output is correct
31 Correct 8 ms 1744 KB Output is correct
32 Correct 1 ms 464 KB Output is correct
33 Correct 1 ms 464 KB Output is correct
34 Correct 1 ms 496 KB Output is correct
35 Correct 1 ms 464 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 5 ms 1284 KB Output is correct
3 Correct 7 ms 1284 KB Output is correct
4 Correct 9 ms 1688 KB Output is correct
5 Correct 8 ms 1792 KB Output is correct
6 Correct 9 ms 1796 KB Output is correct
7 Correct 8 ms 1720 KB Output is correct
8 Correct 1 ms 464 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 1 ms 464 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 464 KB Output is correct
14 Correct 1 ms 464 KB Output is correct
15 Correct 5 ms 1360 KB Output is correct
16 Correct 8 ms 1744 KB Output is correct
17 Correct 10 ms 1744 KB Output is correct
18 Correct 1 ms 464 KB Output is correct
19 Correct 1 ms 464 KB Output is correct
20 Correct 6 ms 1360 KB Output is correct
21 Correct 11 ms 1728 KB Output is correct
22 Correct 8 ms 1744 KB Output is correct
23 Correct 1 ms 464 KB Output is correct
24 Correct 1 ms 464 KB Output is correct
25 Correct 2 ms 720 KB Output is correct
26 Correct 5 ms 1360 KB Output is correct
27 Correct 6 ms 1232 KB Output is correct
28 Correct 7 ms 1744 KB Output is correct
29 Correct 8 ms 1744 KB Output is correct
30 Correct 10 ms 1744 KB Output is correct
31 Correct 8 ms 1744 KB Output is correct
32 Correct 1 ms 464 KB Output is correct
33 Correct 1 ms 464 KB Output is correct
34 Correct 1 ms 496 KB Output is correct
35 Correct 1 ms 464 KB Output is correct
36 Correct 181 ms 50424 KB Output is correct
37 Correct 337 ms 91524 KB Output is correct
38 Correct 295 ms 91104 KB Output is correct
39 Correct 416 ms 132664 KB Output is correct
40 Correct 428 ms 132652 KB Output is correct
41 Correct 454 ms 132712 KB Output is correct
42 Correct 476 ms 132688 KB Output is correct
43 Correct 25 ms 8636 KB Output is correct
44 Correct 19 ms 8616 KB Output is correct
45 Correct 18 ms 8620 KB Output is correct
46 Correct 29 ms 8760 KB Output is correct
47 Correct 303 ms 91116 KB Output is correct
48 Correct 419 ms 132676 KB Output is correct
49 Correct 457 ms 132704 KB Output is correct
50 Correct 23 ms 8660 KB Output is correct
51 Correct 24 ms 8624 KB Output is correct
52 Correct 301 ms 91208 KB Output is correct
53 Correct 424 ms 132664 KB Output is correct
54 Correct 474 ms 132644 KB Output is correct
55 Correct 28 ms 8668 KB Output is correct
56 Correct 22 ms 8648 KB Output is correct
57 Correct 278 ms 86900 KB Output is correct
58 Correct 310 ms 91264 KB Output is correct
59 Correct 290 ms 91516 KB Output is correct
60 Correct 427 ms 132704 KB Output is correct
61 Correct 438 ms 132732 KB Output is correct
62 Correct 427 ms 132680 KB Output is correct
63 Correct 456 ms 132660 KB Output is correct
64 Correct 23 ms 8656 KB Output is correct
65 Correct 26 ms 8628 KB Output is correct
66 Correct 25 ms 8636 KB Output is correct
67 Correct 18 ms 8620 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1804 ms 90040 KB Output is correct
2 Correct 2416 ms 91284 KB Output is correct
3 Correct 2152 ms 91172 KB Output is correct
4 Correct 1962 ms 132656 KB Output is correct
5 Correct 2590 ms 132712 KB Output is correct
6 Correct 2220 ms 132692 KB Output is correct
7 Correct 2281 ms 132644 KB Output is correct
8 Correct 1893 ms 8624 KB Output is correct
9 Correct 2282 ms 8620 KB Output is correct
10 Correct 1959 ms 8620 KB Output is correct
11 Correct 2106 ms 8616 KB Output is correct
12 Correct 1767 ms 8640 KB Output is correct
13 Correct 1779 ms 8580 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 464 KB Output is correct
16 Correct 1 ms 464 KB Output is correct
17 Correct 279 ms 91048 KB Output is correct
18 Correct 474 ms 132700 KB Output is correct
19 Correct 461 ms 132676 KB Output is correct
20 Correct 26 ms 8636 KB Output is correct
21 Correct 29 ms 8632 KB Output is correct
22 Correct 301 ms 91156 KB Output is correct
23 Correct 462 ms 132668 KB Output is correct
24 Correct 467 ms 132616 KB Output is correct
25 Correct 20 ms 8616 KB Output is correct
26 Correct 25 ms 8604 KB Output is correct
27 Correct 6 ms 1360 KB Output is correct
28 Correct 8 ms 1744 KB Output is correct
29 Correct 9 ms 1744 KB Output is correct
30 Correct 1 ms 496 KB Output is correct
31 Correct 2 ms 464 KB Output is correct
32 Correct 6 ms 1360 KB Output is correct
33 Correct 9 ms 1744 KB Output is correct
34 Correct 8 ms 1724 KB Output is correct
35 Correct 2 ms 464 KB Output is correct
36 Correct 1 ms 464 KB Output is correct

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 558 ms 14920 KB Output is correct
2 Correct 3093 ms 91304 KB Output is correct
3 Correct 3808 ms 91288 KB Output is correct
4 Correct 3637 ms 132780 KB Output is correct
5 Execution timed out 4050 ms 132704 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 5 ms 1284 KB Output is correct
3 Correct 7 ms 1284 KB Output is correct
4 Correct 9 ms 1688 KB Output is correct
5 Correct 8 ms 1792 KB Output is correct
6 Correct 9 ms 1796 KB Output is correct
7 Correct 8 ms 1720 KB Output is correct
8 Correct 1 ms 464 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 1 ms 464 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 464 KB Output is correct
14 Correct 1 ms 464 KB Output is correct
15 Correct 5 ms 1360 KB Output is correct
16 Correct 8 ms 1744 KB Output is correct
17 Correct 10 ms 1744 KB Output is correct
18 Correct 1 ms 464 KB Output is correct
19 Correct 1 ms 464 KB Output is correct
20 Correct 6 ms 1360 KB Output is correct
21 Correct 11 ms 1728 KB Output is correct
22 Correct 8 ms 1744 KB Output is correct
23 Correct 1 ms 464 KB Output is correct
24 Correct 1 ms 464 KB Output is correct
25 Correct 2 ms 720 KB Output is correct
26 Correct 5 ms 1360 KB Output is correct
27 Correct 6 ms 1232 KB Output is correct
28 Correct 7 ms 1744 KB Output is correct
29 Correct 8 ms 1744 KB Output is correct
30 Correct 10 ms 1744 KB Output is correct
31 Correct 8 ms 1744 KB Output is correct
32 Correct 1 ms 464 KB Output is correct
33 Correct 1 ms 464 KB Output is correct
34 Correct 1 ms 496 KB Output is correct
35 Correct 1 ms 464 KB Output is correct
36 Correct 181 ms 50424 KB Output is correct
37 Correct 337 ms 91524 KB Output is correct
38 Correct 295 ms 91104 KB Output is correct
39 Correct 416 ms 132664 KB Output is correct
40 Correct 428 ms 132652 KB Output is correct
41 Correct 454 ms 132712 KB Output is correct
42 Correct 476 ms 132688 KB Output is correct
43 Correct 25 ms 8636 KB Output is correct
44 Correct 19 ms 8616 KB Output is correct
45 Correct 18 ms 8620 KB Output is correct
46 Correct 29 ms 8760 KB Output is correct
47 Correct 303 ms 91116 KB Output is correct
48 Correct 419 ms 132676 KB Output is correct
49 Correct 457 ms 132704 KB Output is correct
50 Correct 23 ms 8660 KB Output is correct
51 Correct 24 ms 8624 KB Output is correct
52 Correct 301 ms 91208 KB Output is correct
53 Correct 424 ms 132664 KB Output is correct
54 Correct 474 ms 132644 KB Output is correct
55 Correct 28 ms 8668 KB Output is correct
56 Correct 22 ms 8648 KB Output is correct
57 Correct 278 ms 86900 KB Output is correct
58 Correct 310 ms 91264 KB Output is correct
59 Correct 290 ms 91516 KB Output is correct
60 Correct 427 ms 132704 KB Output is correct
61 Correct 438 ms 132732 KB Output is correct
62 Correct 427 ms 132680 KB Output is correct
63 Correct 456 ms 132660 KB Output is correct
64 Correct 23 ms 8656 KB Output is correct
65 Correct 26 ms 8628 KB Output is correct
66 Correct 25 ms 8636 KB Output is correct
67 Correct 18 ms 8620 KB Output is correct
68 Correct 1804 ms 90040 KB Output is correct
69 Correct 2416 ms 91284 KB Output is correct
70 Correct 2152 ms 91172 KB Output is correct
71 Correct 1962 ms 132656 KB Output is correct
72 Correct 2590 ms 132712 KB Output is correct
73 Correct 2220 ms 132692 KB Output is correct
74 Correct 2281 ms 132644 KB Output is correct
75 Correct 1893 ms 8624 KB Output is correct
76 Correct 2282 ms 8620 KB Output is correct
77 Correct 1959 ms 8620 KB Output is correct
78 Correct 2106 ms 8616 KB Output is correct
79 Correct 1767 ms 8640 KB Output is correct
80 Correct 1779 ms 8580 KB Output is correct
81 Correct 1 ms 364 KB Output is correct
82 Correct 1 ms 464 KB Output is correct
83 Correct 1 ms 464 KB Output is correct
84 Correct 279 ms 91048 KB Output is correct
85 Correct 474 ms 132700 KB Output is correct
86 Correct 461 ms 132676 KB Output is correct
87 Correct 26 ms 8636 KB Output is correct
88 Correct 29 ms 8632 KB Output is correct
89 Correct 301 ms 91156 KB Output is correct
90 Correct 462 ms 132668 KB Output is correct
91 Correct 467 ms 132616 KB Output is correct
92 Correct 20 ms 8616 KB Output is correct
93 Correct 25 ms 8604 KB Output is correct
94 Correct 6 ms 1360 KB Output is correct
95 Correct 8 ms 1744 KB Output is correct
96 Correct 9 ms 1744 KB Output is correct
97 Correct 1 ms 496 KB Output is correct
98 Correct 2 ms 464 KB Output is correct
99 Correct 6 ms 1360 KB Output is correct
100 Correct 9 ms 1744 KB Output is correct
101 Correct 8 ms 1724 KB Output is correct
102 Correct 2 ms 464 KB Output is correct
103 Correct 1 ms 464 KB Output is correct
104 Correct 2063 ms 77204 KB Output is correct
105 Correct 2122 ms 91028 KB Output is correct
106 Correct 1720 ms 91428 KB Output is correct
107 Correct 2117 ms 132640 KB Output is correct
108 Correct 1974 ms 132696 KB Output is correct
109 Correct 2385 ms 132620 KB Output is correct
110 Correct 2463 ms 132680 KB Output is correct
111 Correct 1611 ms 8580 KB Output is correct
112 Correct 1782 ms 8604 KB Output is correct
113 Correct 1531 ms 8652 KB Output is correct
114 Correct 1604 ms 8656 KB Output is correct

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 783 ms 5284 KB Output is correct
2 Correct 1683 ms 8616 KB Output is correct
3 Correct 1475 ms 8740 KB Output is correct
4 Correct 1638 ms 8640 KB Output is correct
5 Correct 2001 ms 8696 KB Output is correct
6 Correct 1509 ms 8664 KB Output is correct
7 Correct 1693 ms 8644 KB Output is correct
8 Correct 0 ms 336 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 1 ms 464 KB Output is correct
12 Correct 5 ms 1284 KB Output is correct
13 Correct 7 ms 1284 KB Output is correct
14 Correct 9 ms 1688 KB Output is correct
15 Correct 8 ms 1792 KB Output is correct
16 Correct 9 ms 1796 KB Output is correct
17 Correct 8 ms 1720 KB Output is correct
18 Correct 1 ms 464 KB Output is correct
19 Correct 1 ms 464 KB Output is correct
20 Correct 1 ms 464 KB Output is correct
21 Correct 1 ms 464 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 464 KB Output is correct
24 Correct 1 ms 464 KB Output is correct
25 Correct 5 ms 1360 KB Output is correct
26 Correct 8 ms 1744 KB Output is correct
27 Correct 10 ms 1744 KB Output is correct
28 Correct 1 ms 464 KB Output is correct
29 Correct 1 ms 464 KB Output is correct
30 Correct 6 ms 1360 KB Output is correct
31 Correct 11 ms 1728 KB Output is correct
32 Correct 8 ms 1744 KB Output is correct
33 Correct 1 ms 464 KB Output is correct
34 Correct 1 ms 464 KB Output is correct
35 Correct 2 ms 720 KB Output is correct
36 Correct 5 ms 1360 KB Output is correct
37 Correct 6 ms 1232 KB Output is correct
38 Correct 7 ms 1744 KB Output is correct
39 Correct 8 ms 1744 KB Output is correct
40 Correct 10 ms 1744 KB Output is correct
41 Correct 8 ms 1744 KB Output is correct
42 Correct 1 ms 464 KB Output is correct
43 Correct 1 ms 464 KB Output is correct
44 Correct 1 ms 496 KB Output is correct
45 Correct 1 ms 464 KB Output is correct
46 Correct 181 ms 50424 KB Output is correct
47 Correct 337 ms 91524 KB Output is correct
48 Correct 295 ms 91104 KB Output is correct
49 Correct 416 ms 132664 KB Output is correct
50 Correct 428 ms 132652 KB Output is correct
51 Correct 454 ms 132712 KB Output is correct
52 Correct 476 ms 132688 KB Output is correct
53 Correct 25 ms 8636 KB Output is correct
54 Correct 19 ms 8616 KB Output is correct
55 Correct 18 ms 8620 KB Output is correct
56 Correct 29 ms 8760 KB Output is correct
57 Correct 303 ms 91116 KB Output is correct
58 Correct 419 ms 132676 KB Output is correct
59 Correct 457 ms 132704 KB Output is correct
60 Correct 23 ms 8660 KB Output is correct
61 Correct 24 ms 8624 KB Output is correct
62 Correct 301 ms 91208 KB Output is correct
63 Correct 424 ms 132664 KB Output is correct
64 Correct 474 ms 132644 KB Output is correct
65 Correct 28 ms 8668 KB Output is correct
66 Correct 22 ms 8648 KB Output is correct
67 Correct 278 ms 86900 KB Output is correct
68 Correct 310 ms 91264 KB Output is correct
69 Correct 290 ms 91516 KB Output is correct
70 Correct 427 ms 132704 KB Output is correct
71 Correct 438 ms 132732 KB Output is correct
72 Correct 427 ms 132680 KB Output is correct
73 Correct 456 ms 132660 KB Output is correct
74 Correct 23 ms 8656 KB Output is correct
75 Correct 26 ms 8628 KB Output is correct
76 Correct 25 ms 8636 KB Output is correct
77 Correct 18 ms 8620 KB Output is correct
78 Correct 1804 ms 90040 KB Output is correct
79 Correct 2416 ms 91284 KB Output is correct
80 Correct 2152 ms 91172 KB Output is correct
81 Correct 1962 ms 132656 KB Output is correct
82 Correct 2590 ms 132712 KB Output is correct
83 Correct 2220 ms 132692 KB Output is correct
84 Correct 2281 ms 132644 KB Output is correct
85 Correct 1893 ms 8624 KB Output is correct
86 Correct 2282 ms 8620 KB Output is correct
87 Correct 1959 ms 8620 KB Output is correct
88 Correct 2106 ms 8616 KB Output is correct
89 Correct 1767 ms 8640 KB Output is correct
90 Correct 1779 ms 8580 KB Output is correct
91 Correct 1 ms 364 KB Output is correct
92 Correct 1 ms 464 KB Output is correct
93 Correct 1 ms 464 KB Output is correct
94 Correct 279 ms 91048 KB Output is correct
95 Correct 474 ms 132700 KB Output is correct
96 Correct 461 ms 132676 KB Output is correct
97 Correct 26 ms 8636 KB Output is correct
98 Correct 29 ms 8632 KB Output is correct
99 Correct 301 ms 91156 KB Output is correct
100 Correct 462 ms 132668 KB Output is correct
101 Correct 467 ms 132616 KB Output is correct
102 Correct 20 ms 8616 KB Output is correct
103 Correct 25 ms 8604 KB Output is correct
104 Correct 6 ms 1360 KB Output is correct
105 Correct 8 ms 1744 KB Output is correct
106 Correct 9 ms 1744 KB Output is correct
107 Correct 1 ms 496 KB Output is correct
108 Correct 2 ms 464 KB Output is correct
109 Correct 6 ms 1360 KB Output is correct
110 Correct 9 ms 1744 KB Output is correct
111 Correct 8 ms 1724 KB Output is correct
112 Correct 2 ms 464 KB Output is correct
113 Correct 1 ms 464 KB Output is correct
114 Correct 558 ms 14920 KB Output is correct
115 Correct 3093 ms 91304 KB Output is correct
116 Correct 3808 ms 91288 KB Output is correct
117 Correct 3637 ms 132780 KB Output is correct
118 Execution timed out 4050 ms 132704 KB Time limit exceeded
119 Halted 0 ms 0 KB -