oj.uz

답안 #635190

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
635190 2022-08-25T15:35:54 Z phathnv 송신탑 (IOI22_towers) C++17
100 / 100
 1902 ms 96144 KB 
#include "towers.h"

#include <bits/stdc++.h>
using namespace std;

struct Node {
    Node* nLeft;
    Node* nRight;
    int l, r, sum, minPos, maxPos, minVal;
    Node(int _l, int _r, int val) {
        nLeft = nRight = nullptr;
        l = _l;
        r = _r;
        sum = 0;
        minPos = 1e9;
        maxPos = -1e9;
        minVal = val;
        assert(l <= r);
    }
};

Node* mergeNode(Node* a, Node* b) {
    assert(a->r + 1 == b->l);
    Node* res = new Node(a->l, b->r, 1e9);
    res->nLeft = a;
    res->nRight = b;
    res->sum = a->sum + b->sum;
    res->minPos = min(a->minPos, b->minPos);
    res->maxPos = max(a->maxPos, b->maxPos);
    res->minVal = min(a->minVal, b->minVal);
    return res;
}

Node* build(int l, int r, const vector<int>& h, const vector<bool>& mark) {
    if (l == r) {
        Node* n = new Node(l, r, h[l]);
        if (mark[l]) {
            n->sum = 1;
            n->minPos = n->maxPos = l;
        }
        return n;
    }
    int mid = (l + r) >> 1;
    return mergeNode(build(l, mid, h, mark), build(mid + 1, r, h, mark));
}

Node* update(Node* n, int pos) {
    if (pos < n->l || n->r < pos) {
        return n;
    }
    if (n->l == n->r) {
        assert(n->sum == 1);
        return new Node(n->l, n->r, n->minVal);
    }
    return mergeNode(update(n->nLeft, pos), update(n->nRight, pos));
}

int getMin(Node*n, int l, int r) {
    if (r < n->l || n->r < l) {
        return 1e9;
    }
    if (l <= n->l && n->r <= r) {
        return n->minVal;
    }
    return min(getMin(n->nLeft, l, r), getMin(n->nRight, l, r));
}

void get(Node*n, int l, int r, int &x, int &y, int &sum) {
    if (r < n->l || n->r < l) {
        return;
    }
    if (l <= n->l && n->r <= r) {
        sum += n->sum;
        x = min(x, n->minPos);
        y = max(y, n->maxPos);
        return;
    }
    get(n->nLeft, l, r, x, y, sum);
    get(n->nRight, l, r, x, y, sum);
}

int n;
vector<int> h;
vector<int> type, changingPoint;
vector<Node*> roots;

void init(int _n, vector<int> _h) {
    n = _n;
    h = _h;

    set<int> s;
    s.insert(0);
    for (int i = 1; i < n; ++i) {
        if (s.size() & 1) {
            if (h[i] > h[*s.rbegin()]) {
                s.insert(i);
            } else {
                s.erase(*s.rbegin());
                s.insert(i);
            }
        } else {
            if (h[i] < h[*s.rbegin()]) {
                s.insert(i);
            } else {
                s.erase(*s.rbegin());
                s.insert(i);
            }
        }
    }
    if (s.size() % 2 == 0) {
        s.erase(*s.rbegin());
    }

    //for (auto x : s) {
        //cerr << x << ' ';
    //}
    //cerr << endl;

    vector<bool> mark(n, false);
    for (auto x : s) {
        mark[x] = true;
    }
    changingPoint.push_back(0);
    roots.push_back(build(0, n - 1, h, mark));

    priority_queue<array<int, 3>> pq;
    type.assign(n, -1);
    int pre = -1, t = 0;
    for (int cur : s) {
        type[cur] = t;
        t ^= 1;
        if (pre != -1) {
            pq.push({-abs(h[pre] - h[cur]), pre, cur});
        }
        pre = cur;
    }

    int last = 0;
    while (!pq.empty()) {
        auto [d, l, r] = pq.top();
        pq.pop();
        if (!mark[l] || !mark[r]) {
            continue;
        }

        d = -d;
        if (d != last) {
            changingPoint.push_back(d);
            roots.push_back(roots.back());
            last = d;
        }

        int a[5] = {-1, -1, -1, -1, -1};

        if (h[l] > h[r]) {
            a[1] = l;
            a[2] = r;
            auto it = s.lower_bound(l);
            if (it != s.begin()) {
                a[0] = *(--it);
            }
            it = s.lower_bound(r);
            ++it;
            if (it != s.end()) {
                a[3] = *it;
                ++it;
            }
            if (it != s.end()) {
                a[4] = *it;
                ++it;
            }
        } else {
            a[2] = l;
            a[3] = r;
            auto it = s.lower_bound(l);
            if (it != s.begin()) {
                a[1] = *(--it);
            }
            if (it != s.begin()) {
                a[0] = *(--it);
            }
            it = s.lower_bound(r);
            ++it;
            if (it != s.end()) {
                a[4] = *it;
                ++it;
            }
        }

        roots.back() = update(roots.back(), a[2]);
        mark[a[2]] = false;
        s.erase(a[2]);
        if (a[1] == -1 || a[3] == -1) {
            if (a[1] != -1) {
                roots.back() = update(roots.back(), a[1]);
                mark[a[1]] = false;
                s.erase(a[1]);
            }
            if (a[3] != -1) {
                roots.back() = update(roots.back(), a[3]);
                mark[a[3]] = false;
                s.erase(a[3]);
            }
        } else {
            if (h[a[1]] > h[a[3]]) {
                roots.back() = update(roots.back(), a[3]);
                mark[a[3]] = false;
                s.erase(a[3]);
                pq.push({-abs(h[a[1]] - h[a[4]]), a[1], a[4]});
            } else {
                roots.back() = update(roots.back(), a[1]);
                mark[a[1]] = false;
                s.erase(a[1]);
                pq.push({-abs(h[a[0]] - h[a[3]]), a[0], a[3]});
            }
        }

        //cerr << "change " << d << ' ' << l << ' ' << r << endl;
        for (int i = 0; i < 5; ++i) {
            //cerr << a[i] << ' ';
        }
        //cerr << endl;
    }
}

int max_towers(int l, int r, int d) {
    Node* root = roots[lower_bound(changingPoint.begin(), changingPoint.end(), d) - changingPoint.begin() - 1];

    int x = 1e9, y = -1e9, res = 0;
    get(root, l, r, x, y, res);

    if (x > y) {
        return 1;
    }

    assert(type[x] != -1 && type[y] != -1);

    if (type[x] == 1) {
        int minVal = 1e9;
        for (int i = l; i <= x - 1; ++i) {
            if (minVal > h[i]) {
                minVal = h[i];
            }
        }

        if (h[x] - d >= getMin(root, l, x - 1)) {
            ++res;
        } else {
            --res;
        }
    }
    if (type[y] == 1) {
        if (h[y] - d >= getMin(root, y + 1, r)) {
            ++res;
        } else {
            --res;
        }
    }
    return max(1, (res + 1) / 2);
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 513 ms 6840 KB Output is correct
2 Correct 1227 ms 11172 KB Output is correct
3 Correct 1228 ms 11192 KB Output is correct
4 Correct 976 ms 11240 KB Output is correct
5 Correct 1281 ms 11200 KB Output is correct
6 Correct 1144 ms 11192 KB Output is correct
7 Correct 1080 ms 11240 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 2 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 4 ms 1280 KB Output is correct
3 Correct 4 ms 1232 KB Output is correct
4 Correct 5 ms 1616 KB Output is correct
5 Correct 5 ms 1616 KB Output is correct
6 Correct 3 ms 1616 KB Output is correct
7 Correct 3 ms 1616 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Correct 2 ms 464 KB Output is correct
11 Correct 1 ms 464 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 1 ms 464 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 4 ms 1232 KB Output is correct
16 Correct 4 ms 1616 KB Output is correct
17 Correct 3 ms 1616 KB Output is correct
18 Correct 1 ms 464 KB Output is correct
19 Correct 1 ms 464 KB Output is correct
20 Correct 3 ms 1260 KB Output is correct
21 Correct 3 ms 1616 KB Output is correct
22 Correct 3 ms 1616 KB Output is correct
23 Correct 2 ms 464 KB Output is correct
24 Correct 1 ms 464 KB Output is correct
25 Correct 1 ms 592 KB Output is correct
26 Correct 3 ms 1232 KB Output is correct
27 Correct 2 ms 1232 KB Output is correct
28 Correct 3 ms 1588 KB Output is correct
29 Correct 4 ms 1616 KB Output is correct
30 Correct 4 ms 1556 KB Output is correct
31 Correct 5 ms 1616 KB Output is correct
32 Correct 1 ms 464 KB Output is correct
33 Correct 2 ms 464 KB Output is correct
34 Correct 1 ms 464 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 4 ms 1280 KB Output is correct
3 Correct 4 ms 1232 KB Output is correct
4 Correct 5 ms 1616 KB Output is correct
5 Correct 5 ms 1616 KB Output is correct
6 Correct 3 ms 1616 KB Output is correct
7 Correct 3 ms 1616 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Correct 2 ms 464 KB Output is correct
11 Correct 1 ms 464 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 1 ms 464 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 4 ms 1232 KB Output is correct
16 Correct 4 ms 1616 KB Output is correct
17 Correct 3 ms 1616 KB Output is correct
18 Correct 1 ms 464 KB Output is correct
19 Correct 1 ms 464 KB Output is correct
20 Correct 3 ms 1260 KB Output is correct
21 Correct 3 ms 1616 KB Output is correct
22 Correct 3 ms 1616 KB Output is correct
23 Correct 2 ms 464 KB Output is correct
24 Correct 1 ms 464 KB Output is correct
25 Correct 1 ms 592 KB Output is correct
26 Correct 3 ms 1232 KB Output is correct
27 Correct 2 ms 1232 KB Output is correct
28 Correct 3 ms 1588 KB Output is correct
29 Correct 4 ms 1616 KB Output is correct
30 Correct 4 ms 1556 KB Output is correct
31 Correct 5 ms 1616 KB Output is correct
32 Correct 1 ms 464 KB Output is correct
33 Correct 2 ms 464 KB Output is correct
34 Correct 1 ms 464 KB Output is correct
35 Correct 1 ms 464 KB Output is correct
36 Correct 169 ms 42640 KB Output is correct
37 Correct 230 ms 67972 KB Output is correct
38 Correct 267 ms 67604 KB Output is correct
39 Correct 381 ms 96008 KB Output is correct
40 Correct 303 ms 96028 KB Output is correct
41 Correct 344 ms 96064 KB Output is correct
42 Correct 327 ms 96024 KB Output is correct
43 Correct 37 ms 11168 KB Output is correct
44 Correct 28 ms 11216 KB Output is correct
45 Correct 31 ms 11168 KB Output is correct
46 Correct 44 ms 11160 KB Output is correct
47 Correct 195 ms 67648 KB Output is correct
48 Correct 321 ms 96052 KB Output is correct
49 Correct 366 ms 96012 KB Output is correct
50 Correct 36 ms 11208 KB Output is correct
51 Correct 37 ms 11300 KB Output is correct
52 Correct 206 ms 67740 KB Output is correct
53 Correct 288 ms 96092 KB Output is correct
54 Correct 283 ms 96100 KB Output is correct
55 Correct 40 ms 11184 KB Output is correct
56 Correct 28 ms 11148 KB Output is correct
57 Correct 185 ms 65384 KB Output is correct
58 Correct 222 ms 67828 KB Output is correct
59 Correct 245 ms 67992 KB Output is correct
60 Correct 288 ms 96028 KB Output is correct
61 Correct 305 ms 96144 KB Output is correct
62 Correct 297 ms 96032 KB Output is correct
63 Correct 295 ms 96000 KB Output is correct
64 Correct 29 ms 11168 KB Output is correct
65 Correct 26 ms 11180 KB Output is correct
66 Correct 42 ms 11164 KB Output is correct
67 Correct 29 ms 11164 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 966 ms 67152 KB Output is correct
2 Correct 1361 ms 67724 KB Output is correct
3 Correct 1727 ms 67716 KB Output is correct
4 Correct 1572 ms 96060 KB Output is correct
5 Correct 1902 ms 96088 KB Output is correct
6 Correct 1440 ms 96024 KB Output is correct
7 Correct 1564 ms 96088 KB Output is correct
8 Correct 1214 ms 11296 KB Output is correct
9 Correct 1042 ms 11168 KB Output is correct
10 Correct 1069 ms 11208 KB Output is correct
11 Correct 1071 ms 11212 KB Output is correct
12 Correct 941 ms 11232 KB Output is correct
13 Correct 1002 ms 11160 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 1 ms 512 KB Output is correct
16 Correct 2 ms 512 KB Output is correct
17 Correct 199 ms 67712 KB Output is correct
18 Correct 290 ms 96036 KB Output is correct
19 Correct 394 ms 96076 KB Output is correct
20 Correct 36 ms 11212 KB Output is correct
21 Correct 28 ms 11192 KB Output is correct
22 Correct 200 ms 67716 KB Output is correct
23 Correct 334 ms 96044 KB Output is correct
24 Correct 294 ms 96116 KB Output is correct
25 Correct 35 ms 11180 KB Output is correct
26 Correct 41 ms 11180 KB Output is correct
27 Correct 3 ms 1280 KB Output is correct
28 Correct 3 ms 1616 KB Output is correct
29 Correct 5 ms 1616 KB Output is correct
30 Correct 2 ms 464 KB Output is correct
31 Correct 1 ms 464 KB Output is correct
32 Correct 3 ms 1232 KB Output is correct
33 Correct 4 ms 1644 KB Output is correct
34 Correct 6 ms 1664 KB Output is correct
35 Correct 1 ms 512 KB Output is correct
36 Correct 1 ms 512 KB Output is correct

Subtask #5
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 394 ms 14916 KB Output is correct
2 Correct 1122 ms 67888 KB Output is correct
3 Correct 1048 ms 67748 KB Output is correct
4 Correct 1305 ms 96092 KB Output is correct
5 Correct 1442 ms 96100 KB Output is correct
6 Correct 1339 ms 96024 KB Output is correct
7 Correct 1212 ms 96064 KB Output is correct
8 Correct 733 ms 11172 KB Output is correct
9 Correct 986 ms 11216 KB Output is correct
10 Correct 940 ms 11196 KB Output is correct
11 Correct 839 ms 11176 KB Output is correct
12 Correct 244 ms 67680 KB Output is correct
13 Correct 378 ms 96092 KB Output is correct
14 Correct 338 ms 96020 KB Output is correct
15 Correct 26 ms 11176 KB Output is correct
16 Correct 28 ms 11256 KB Output is correct
17 Correct 191 ms 65360 KB Output is correct
18 Correct 225 ms 67796 KB Output is correct
19 Correct 254 ms 67896 KB Output is correct
20 Correct 331 ms 95992 KB Output is correct
21 Correct 307 ms 96104 KB Output is correct
22 Correct 355 ms 96044 KB Output is correct
23 Correct 316 ms 96016 KB Output is correct
24 Correct 34 ms 11200 KB Output is correct
25 Correct 36 ms 11172 KB Output is correct
26 Correct 39 ms 11204 KB Output is correct
27 Correct 40 ms 11168 KB Output is correct
28 Correct 4 ms 1232 KB Output is correct
29 Correct 5 ms 1664 KB Output is correct
30 Correct 5 ms 1616 KB Output is correct
31 Correct 1 ms 464 KB Output is correct
32 Correct 1 ms 464 KB Output is correct
33 Correct 1 ms 592 KB Output is correct
34 Correct 4 ms 1236 KB Output is correct
35 Correct 3 ms 1232 KB Output is correct
36 Correct 4 ms 1616 KB Output is correct
37 Correct 4 ms 1616 KB Output is correct
38 Correct 5 ms 1616 KB Output is correct
39 Correct 4 ms 1636 KB Output is correct
40 Correct 1 ms 464 KB Output is correct
41 Correct 2 ms 512 KB Output is correct
42 Correct 2 ms 464 KB Output is correct
43 Correct 2 ms 464 KB Output is correct

Subtask #6
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 4 ms 1280 KB Output is correct
3 Correct 4 ms 1232 KB Output is correct
4 Correct 5 ms 1616 KB Output is correct
5 Correct 5 ms 1616 KB Output is correct
6 Correct 3 ms 1616 KB Output is correct
7 Correct 3 ms 1616 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Correct 2 ms 464 KB Output is correct
11 Correct 1 ms 464 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 1 ms 464 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 4 ms 1232 KB Output is correct
16 Correct 4 ms 1616 KB Output is correct
17 Correct 3 ms 1616 KB Output is correct
18 Correct 1 ms 464 KB Output is correct
19 Correct 1 ms 464 KB Output is correct
20 Correct 3 ms 1260 KB Output is correct
21 Correct 3 ms 1616 KB Output is correct
22 Correct 3 ms 1616 KB Output is correct
23 Correct 2 ms 464 KB Output is correct
24 Correct 1 ms 464 KB Output is correct
25 Correct 1 ms 592 KB Output is correct
26 Correct 3 ms 1232 KB Output is correct
27 Correct 2 ms 1232 KB Output is correct
28 Correct 3 ms 1588 KB Output is correct
29 Correct 4 ms 1616 KB Output is correct
30 Correct 4 ms 1556 KB Output is correct
31 Correct 5 ms 1616 KB Output is correct
32 Correct 1 ms 464 KB Output is correct
33 Correct 2 ms 464 KB Output is correct
34 Correct 1 ms 464 KB Output is correct
35 Correct 1 ms 464 KB Output is correct
36 Correct 169 ms 42640 KB Output is correct
37 Correct 230 ms 67972 KB Output is correct
38 Correct 267 ms 67604 KB Output is correct
39 Correct 381 ms 96008 KB Output is correct
40 Correct 303 ms 96028 KB Output is correct
41 Correct 344 ms 96064 KB Output is correct
42 Correct 327 ms 96024 KB Output is correct
43 Correct 37 ms 11168 KB Output is correct
44 Correct 28 ms 11216 KB Output is correct
45 Correct 31 ms 11168 KB Output is correct
46 Correct 44 ms 11160 KB Output is correct
47 Correct 195 ms 67648 KB Output is correct
48 Correct 321 ms 96052 KB Output is correct
49 Correct 366 ms 96012 KB Output is correct
50 Correct 36 ms 11208 KB Output is correct
51 Correct 37 ms 11300 KB Output is correct
52 Correct 206 ms 67740 KB Output is correct
53 Correct 288 ms 96092 KB Output is correct
54 Correct 283 ms 96100 KB Output is correct
55 Correct 40 ms 11184 KB Output is correct
56 Correct 28 ms 11148 KB Output is correct
57 Correct 185 ms 65384 KB Output is correct
58 Correct 222 ms 67828 KB Output is correct
59 Correct 245 ms 67992 KB Output is correct
60 Correct 288 ms 96028 KB Output is correct
61 Correct 305 ms 96144 KB Output is correct
62 Correct 297 ms 96032 KB Output is correct
63 Correct 295 ms 96000 KB Output is correct
64 Correct 29 ms 11168 KB Output is correct
65 Correct 26 ms 11180 KB Output is correct
66 Correct 42 ms 11164 KB Output is correct
67 Correct 29 ms 11164 KB Output is correct
68 Correct 966 ms 67152 KB Output is correct
69 Correct 1361 ms 67724 KB Output is correct
70 Correct 1727 ms 67716 KB Output is correct
71 Correct 1572 ms 96060 KB Output is correct
72 Correct 1902 ms 96088 KB Output is correct
73 Correct 1440 ms 96024 KB Output is correct
74 Correct 1564 ms 96088 KB Output is correct
75 Correct 1214 ms 11296 KB Output is correct
76 Correct 1042 ms 11168 KB Output is correct
77 Correct 1069 ms 11208 KB Output is correct
78 Correct 1071 ms 11212 KB Output is correct
79 Correct 941 ms 11232 KB Output is correct
80 Correct 1002 ms 11160 KB Output is correct
81 Correct 0 ms 256 KB Output is correct
82 Correct 1 ms 512 KB Output is correct
83 Correct 2 ms 512 KB Output is correct
84 Correct 199 ms 67712 KB Output is correct
85 Correct 290 ms 96036 KB Output is correct
86 Correct 394 ms 96076 KB Output is correct
87 Correct 36 ms 11212 KB Output is correct
88 Correct 28 ms 11192 KB Output is correct
89 Correct 200 ms 67716 KB Output is correct
90 Correct 334 ms 96044 KB Output is correct
91 Correct 294 ms 96116 KB Output is correct
92 Correct 35 ms 11180 KB Output is correct
93 Correct 41 ms 11180 KB Output is correct
94 Correct 3 ms 1280 KB Output is correct
95 Correct 3 ms 1616 KB Output is correct
96 Correct 5 ms 1616 KB Output is correct
97 Correct 2 ms 464 KB Output is correct
98 Correct 1 ms 464 KB Output is correct
99 Correct 3 ms 1232 KB Output is correct
100 Correct 4 ms 1644 KB Output is correct
101 Correct 6 ms 1664 KB Output is correct
102 Correct 1 ms 512 KB Output is correct
103 Correct 1 ms 512 KB Output is correct
104 Correct 1284 ms 59936 KB Output is correct
105 Correct 1335 ms 67564 KB Output is correct
106 Correct 1500 ms 67988 KB Output is correct
107 Correct 1478 ms 96020 KB Output is correct
108 Correct 1782 ms 96016 KB Output is correct
109 Correct 1354 ms 96108 KB Output is correct
110 Correct 1306 ms 96012 KB Output is correct
111 Correct 1082 ms 11160 KB Output is correct
112 Correct 1231 ms 11184 KB Output is correct
113 Correct 1251 ms 11228 KB Output is correct
114 Correct 1088 ms 11192 KB Output is correct

Subtask #7
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 513 ms 6840 KB Output is correct
2 Correct 1227 ms 11172 KB Output is correct
3 Correct 1228 ms 11192 KB Output is correct
4 Correct 976 ms 11240 KB Output is correct
5 Correct 1281 ms 11200 KB Output is correct
6 Correct 1144 ms 11192 KB Output is correct
7 Correct 1080 ms 11240 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 2 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 4 ms 1280 KB Output is correct
13 Correct 4 ms 1232 KB Output is correct
14 Correct 5 ms 1616 KB Output is correct
15 Correct 5 ms 1616 KB Output is correct
16 Correct 3 ms 1616 KB Output is correct
17 Correct 3 ms 1616 KB Output is correct
18 Correct 1 ms 512 KB Output is correct
19 Correct 1 ms 464 KB Output is correct
20 Correct 2 ms 464 KB Output is correct
21 Correct 1 ms 464 KB Output is correct
22 Correct 1 ms 208 KB Output is correct
23 Correct 1 ms 464 KB Output is correct
24 Correct 1 ms 512 KB Output is correct
25 Correct 4 ms 1232 KB Output is correct
26 Correct 4 ms 1616 KB Output is correct
27 Correct 3 ms 1616 KB Output is correct
28 Correct 1 ms 464 KB Output is correct
29 Correct 1 ms 464 KB Output is correct
30 Correct 3 ms 1260 KB Output is correct
31 Correct 3 ms 1616 KB Output is correct
32 Correct 3 ms 1616 KB Output is correct
33 Correct 2 ms 464 KB Output is correct
34 Correct 1 ms 464 KB Output is correct
35 Correct 1 ms 592 KB Output is correct
36 Correct 3 ms 1232 KB Output is correct
37 Correct 2 ms 1232 KB Output is correct
38 Correct 3 ms 1588 KB Output is correct
39 Correct 4 ms 1616 KB Output is correct
40 Correct 4 ms 1556 KB Output is correct
41 Correct 5 ms 1616 KB Output is correct
42 Correct 1 ms 464 KB Output is correct
43 Correct 2 ms 464 KB Output is correct
44 Correct 1 ms 464 KB Output is correct
45 Correct 1 ms 464 KB Output is correct
46 Correct 169 ms 42640 KB Output is correct
47 Correct 230 ms 67972 KB Output is correct
48 Correct 267 ms 67604 KB Output is correct
49 Correct 381 ms 96008 KB Output is correct
50 Correct 303 ms 96028 KB Output is correct
51 Correct 344 ms 96064 KB Output is correct
52 Correct 327 ms 96024 KB Output is correct
53 Correct 37 ms 11168 KB Output is correct
54 Correct 28 ms 11216 KB Output is correct
55 Correct 31 ms 11168 KB Output is correct
56 Correct 44 ms 11160 KB Output is correct
57 Correct 195 ms 67648 KB Output is correct
58 Correct 321 ms 96052 KB Output is correct
59 Correct 366 ms 96012 KB Output is correct
60 Correct 36 ms 11208 KB Output is correct
61 Correct 37 ms 11300 KB Output is correct
62 Correct 206 ms 67740 KB Output is correct
63 Correct 288 ms 96092 KB Output is correct
64 Correct 283 ms 96100 KB Output is correct
65 Correct 40 ms 11184 KB Output is correct
66 Correct 28 ms 11148 KB Output is correct
67 Correct 185 ms 65384 KB Output is correct
68 Correct 222 ms 67828 KB Output is correct
69 Correct 245 ms 67992 KB Output is correct
70 Correct 288 ms 96028 KB Output is correct
71 Correct 305 ms 96144 KB Output is correct
72 Correct 297 ms 96032 KB Output is correct
73 Correct 295 ms 96000 KB Output is correct
74 Correct 29 ms 11168 KB Output is correct
75 Correct 26 ms 11180 KB Output is correct
76 Correct 42 ms 11164 KB Output is correct
77 Correct 29 ms 11164 KB Output is correct
78 Correct 966 ms 67152 KB Output is correct
79 Correct 1361 ms 67724 KB Output is correct
80 Correct 1727 ms 67716 KB Output is correct
81 Correct 1572 ms 96060 KB Output is correct
82 Correct 1902 ms 96088 KB Output is correct
83 Correct 1440 ms 96024 KB Output is correct
84 Correct 1564 ms 96088 KB Output is correct
85 Correct 1214 ms 11296 KB Output is correct
86 Correct 1042 ms 11168 KB Output is correct
87 Correct 1069 ms 11208 KB Output is correct
88 Correct 1071 ms 11212 KB Output is correct
89 Correct 941 ms 11232 KB Output is correct
90 Correct 1002 ms 11160 KB Output is correct
91 Correct 0 ms 256 KB Output is correct
92 Correct 1 ms 512 KB Output is correct
93 Correct 2 ms 512 KB Output is correct
94 Correct 199 ms 67712 KB Output is correct
95 Correct 290 ms 96036 KB Output is correct
96 Correct 394 ms 96076 KB Output is correct
97 Correct 36 ms 11212 KB Output is correct
98 Correct 28 ms 11192 KB Output is correct
99 Correct 200 ms 67716 KB Output is correct
100 Correct 334 ms 96044 KB Output is correct
101 Correct 294 ms 96116 KB Output is correct
102 Correct 35 ms 11180 KB Output is correct
103 Correct 41 ms 11180 KB Output is correct
104 Correct 3 ms 1280 KB Output is correct
105 Correct 3 ms 1616 KB Output is correct
106 Correct 5 ms 1616 KB Output is correct
107 Correct 2 ms 464 KB Output is correct
108 Correct 1 ms 464 KB Output is correct
109 Correct 3 ms 1232 KB Output is correct
110 Correct 4 ms 1644 KB Output is correct
111 Correct 6 ms 1664 KB Output is correct
112 Correct 1 ms 512 KB Output is correct
113 Correct 1 ms 512 KB Output is correct
114 Correct 394 ms 14916 KB Output is correct
115 Correct 1122 ms 67888 KB Output is correct
116 Correct 1048 ms 67748 KB Output is correct
117 Correct 1305 ms 96092 KB Output is correct
118 Correct 1442 ms 96100 KB Output is correct
119 Correct 1339 ms 96024 KB Output is correct
120 Correct 1212 ms 96064 KB Output is correct
121 Correct 733 ms 11172 KB Output is correct
122 Correct 986 ms 11216 KB Output is correct
123 Correct 940 ms 11196 KB Output is correct
124 Correct 839 ms 11176 KB Output is correct
125 Correct 244 ms 67680 KB Output is correct
126 Correct 378 ms 96092 KB Output is correct
127 Correct 338 ms 96020 KB Output is correct
128 Correct 26 ms 11176 KB Output is correct
129 Correct 28 ms 11256 KB Output is correct
130 Correct 191 ms 65360 KB Output is correct
131 Correct 225 ms 67796 KB Output is correct
132 Correct 254 ms 67896 KB Output is correct
133 Correct 331 ms 95992 KB Output is correct
134 Correct 307 ms 96104 KB Output is correct
135 Correct 355 ms 96044 KB Output is correct
136 Correct 316 ms 96016 KB Output is correct
137 Correct 34 ms 11200 KB Output is correct
138 Correct 36 ms 11172 KB Output is correct
139 Correct 39 ms 11204 KB Output is correct
140 Correct 40 ms 11168 KB Output is correct
141 Correct 4 ms 1232 KB Output is correct
142 Correct 5 ms 1664 KB Output is correct
143 Correct 5 ms 1616 KB Output is correct
144 Correct 1 ms 464 KB Output is correct
145 Correct 1 ms 464 KB Output is correct
146 Correct 1 ms 592 KB Output is correct
147 Correct 4 ms 1236 KB Output is correct
148 Correct 3 ms 1232 KB Output is correct
149 Correct 4 ms 1616 KB Output is correct
150 Correct 4 ms 1616 KB Output is correct
151 Correct 5 ms 1616 KB Output is correct
152 Correct 4 ms 1636 KB Output is correct
153 Correct 1 ms 464 KB Output is correct
154 Correct 2 ms 512 KB Output is correct
155 Correct 2 ms 464 KB Output is correct
156 Correct 2 ms 464 KB Output is correct
157 Correct 1284 ms 59936 KB Output is correct
158 Correct 1335 ms 67564 KB Output is correct
159 Correct 1500 ms 67988 KB Output is correct
160 Correct 1478 ms 96020 KB Output is correct
161 Correct 1782 ms 96016 KB Output is correct
162 Correct 1354 ms 96108 KB Output is correct
163 Correct 1306 ms 96012 KB Output is correct
164 Correct 1082 ms 11160 KB Output is correct
165 Correct 1231 ms 11184 KB Output is correct
166 Correct 1251 ms 11228 KB Output is correct
167 Correct 1088 ms 11192 KB Output is correct
168 Correct 1 ms 256 KB Output is correct
169 Correct 1063 ms 22024 KB Output is correct
170 Correct 1582 ms 67392 KB Output is correct
171 Correct 1661 ms 67604 KB Output is correct
172 Correct 1752 ms 96092 KB Output is correct
173 Correct 1607 ms 96008 KB Output is correct
174 Correct 1578 ms 96024 KB Output is correct
175 Correct 1626 ms 96004 KB Output is correct
176 Correct 1098 ms 11156 KB Output is correct
177 Correct 1112 ms 11168 KB Output is correct
178 Correct 1117 ms 11168 KB Output is correct
179 Correct 1139 ms 11176 KB Output is correct