oj.uz

답안 #876517

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
876517 2023-11-21T21:17:25 Z danikoynov Fish 2 (JOI22_fish2) C++14
48 / 100
 4000 ms 90384 KB 
#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

typedef long long ll;

const int maxn = 1e5 + 10;


int n, q;
ll a[maxn], pref[maxn];
void input()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    cin >> q;
    a[0] = 1e9 + 10;
    a[n + 1] = 1e9 + 10;

}

struct interval
{
    int left, right, pivot;

    interval(int _left = 0, int _right = 0, int _pivot = 0)
    {
        left = _left;
        right = _right;
        pivot = _pivot;
    }
    bool operator < (const interval &it) const
    {
        if (left != it.left)
            return left < it.left;
        if (right != it.right)
            return right < it.right;
        ///assert(pivot != it.pivot);
        return pivot < it.pivot;
    }
};

set < interval > ranges;
vector < interval > act[4 * maxn];

void add_range(int root, int left, int right, int qleft, int qright, interval cur)
{
    if (left > qright || right < qleft)
        return;

    if (left >= qleft && right <= qright)
    {
        //cout << "ROOT " << root << endl;
        act[root].push_back(cur);

        return;
    }

    int mid = (left + right) / 2;
    add_range(root * 2, left, mid, qleft, qright, cur);
    add_range(root * 2 + 1, mid + 1, right, qleft, qright, cur);
}

void rem_range(int root, int left, int right, int qleft, int qright)
{
    if (left > qright || right < qleft)
        return;

    if (left >= qleft && right <= qright)
    {
        act[root].pop_back();
        return;
    }

    int mid = (left + right) / 2;
    rem_range(root * 2, left, mid, qleft, qright);
    rem_range(root * 2 + 1, mid + 1, right, qleft, qright);
}

bool cmp_interval(const interval &it1, const interval &it2)
{
    if ((it1.right - it1.left) != (it2.right - it2.left))
        return (it1.right - it1.left) < (it2.right - it2.left);
    if (it1.left != it2.left)
        return it1.left < it2.left;

    /**if (it1.pivot == it2.pivot)
    {
        cout << "here" << endl;
        cout << it1.left << " " << it1.right << " " << it1.pivot << endl;
        cout << it2.left << " " << it2.right << " " << it2.pivot << endl;
        cout << "FUCK" << endl;
        exit(0);
    }*/
    return (it1.pivot < it2.pivot);
}

set < interval > pact[maxn];
void get_ranges()
{
    ranges.clear();
    stack < int > st;
    st.push(0);
    vector < interval > vec;
    for (int i = 1; i <= n; i ++)
    {
        while(!st.empty() && a[st.top()] < a[i])
            st.pop();

        ranges.insert(interval(st.top(), i, i));
        vec.push_back(interval(st.top(), i, i));


        st.push(i);
    }

    while(!st.empty())
        st.pop();
    st.push(n + 1);
    for (int i = n; i > 0; i --)
    {
        while(!st.empty() && a[st.top()] < a[i])
            st.pop();

        ranges.insert(interval(i, st.top(), i));
        vec.push_back(interval(i, st.top(), i));

        st.push(i);
    }

    sort(vec.begin(), vec.end(), cmp_interval);
    ///reverse(vec.begin(), vec.end());
    for (interval cur : vec)
    {
        //cout << "added " << cur.left << " " << cur.right << endl;
        pact[cur.left].insert(cur);
        pact[cur.right].insert(cur);
        add_range(1, 0, n + 1, cur.left + 1, cur.right - 1, cur);
    }
}

int b[maxn];

struct node
{
    int cnt, mx;

    node(int _cnt = 0, int _mx = 1e9 + 10)
    {
        cnt = _cnt;
        mx = _mx;
    }
};

node tree[4 * maxn];
int lazy[4 * maxn];

node merge_node(node lf, node rf)
{
    if (lf.cnt == -1 || rf.mx < lf.mx)
        return rf;
    if (rf.cnt == -1 || lf.mx < rf.mx)
        return lf;

    return node(lf.cnt + rf.cnt, lf.mx);
}

void push_lazy(int root, int left, int right)
{
    tree[root].mx += lazy[root];
    if (left != right)
    {
        lazy[root * 2] += lazy[root];
        lazy[root * 2 + 1] += lazy[root];
    }
    lazy[root] = 0;
}

void build_tree(int root, int left, int right)
{
    lazy[root] = 0;
    if (left == right)
    {
        tree[root].mx = b[left];
        tree[root].cnt = 1;
        return;
    }

    int mid = (left + right) / 2;
    build_tree(root * 2, left, mid);
    build_tree(root * 2 + 1, mid + 1, right);

    tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}

void update_range(int root, int left, int right, int qleft, int qright, int val)
{
    push_lazy(root, left, right);
    if (left > qright || right < qleft)
        return;

    if (left >= qleft && right <= qright)
    {
        lazy[root] = val;
        push_lazy(root, left, right);
        return;
    }

    int mid = (left + right) / 2;
    update_range(root * 2, left, mid, qleft, qright, val);
    update_range(root * 2 + 1, mid + 1, right, qleft, qright, val);

    tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}
node query(int root, int left, int right, int qleft, int qright)
{
    push_lazy(root, left, right);
    if (left > qright || right < qleft)
        return node(-1, 1e9 + 10);

    if (left >= qleft && right <= qright)
        return tree[root];

    int mid = (left + right) / 2;

    return merge_node(query(root * 2, left, mid, qleft, qright),
            query(root * 2 + 1, mid + 1, right, qleft, qright));
}

ll values[maxn];

struct segment_tree
{
    ll tree[4 * maxn], lazy[4 * maxn];


    void build_tree(int root, int left, int right)
    {
        lazy[root] = 0;
        if (left == right)
        {
            tree[root] = values[left];
            return;
        }

        int mid = (left + right) / 2;
        build_tree(root * 2, left, mid);
        build_tree(root * 2 + 1, mid + 1, right);

        tree[root] = max(tree[root * 2], tree[root * 2 + 1]);
    }

    void push_lazy(int root, int left, int right)
    {
        tree[root] += lazy[root];
        if (left != right)
        {
            lazy[root * 2] += lazy[root];
            lazy[root * 2 + 1] += lazy[root];
        }

        lazy[root] = 0;
    }

    void update_range(int root, int left, int right, int qleft, int qright, ll val)
    {
        push_lazy(root, left, right);
        if (left > qright || right < qleft)
            return;

        if (left >= qleft && right <= qright)
        {
            lazy[root] += val;
            push_lazy(root, left, right);
            return;
        }

        int mid = (left + right) / 2;
        update_range(root * 2, left, mid, qleft, qright, val);
        update_range(root * 2 + 1, mid + 1, right, qleft, qright, val);

        tree[root] = max(tree[root * 2], tree[root * 2 + 1]);
    }

    ll walk_left(int root, int left, int right, int qleft, int qright, ll val)
    {
        push_lazy(root, left, right);
        if (left > qright || right < qleft || tree[root] <= val)
            return n + 1;

        if (left == right)
            return left;

        int mid = (left + right) / 2;
        if (left >= qleft && right <= qright)
        {
            push_lazy(root * 2, left, mid);
            push_lazy(root * 2 + 1, mid + 1, right);
            if (tree[root * 2] > val)
                return walk_left(root * 2, left, mid, qleft, qright, val);
            return walk_left(root * 2 + 1, mid + 1, right, qleft, qright, val);
        }

        return min(walk_left(root * 2, left, mid, qleft, qright, val),
                walk_left(root * 2 + 1, mid + 1, right, qleft, qright, val));
    }

    ll walk_right(int root, int left, int right, int qleft, int qright, ll val)
    {
        push_lazy(root, left, right);
        if (left > qright || right < qleft || tree[root] <= val)
            return 0;

        if (left == right)
            return left;

        int mid = (left + right) / 2;
        if (left >= qleft && right <= qright)
        {
            push_lazy(root * 2, left, mid);
            push_lazy(root * 2 + 1, mid + 1, right);
            if (tree[root * 2 + 1] > val)
                    return walk_right(root * 2 + 1, mid + 1, right, qleft, qright, val);
            return walk_right(root * 2, left, mid, qleft, qright, val);
        }

        return max(walk_right(root * 2, left, mid, qleft, qright, val),
                walk_right(root * 2 + 1, mid + 1, right, qleft, qright, val));
    }
};

segment_tree left_tree, right_tree;

ll fen[maxn];

void update_fen(int pos, ll val)
{
    for (int i = pos; i <= n; i += (i & -i))
        fen[i] += val;
}

ll query_fen(int pos)
{
    ll s = 0;
    for (int i = pos; i > 0; i -= (i & -i))
        s += fen[i];
    return s;
}

ll range_sum(int left, int right)
{
    return query_fen(right) - query_fen(left - 1);
}

void solve_query(int left, int right)
{
    int lb = left_tree.walk_right(1, 1, n, left, right, - query_fen(left - 1));
    int rb = right_tree.walk_left(1, 1, n, left, right, query_fen(right));


    cout << query(1, 1, n, lb, rb).cnt << endl;
}

void restructure()
{
    ///cout << "-------------" << endl;

    build_tree(1, 1, n);
    for (interval cur : ranges)
    {
        ll mx = min(a[cur.left], a[cur.right]);
        if (range_sum(cur.left + 1, cur.right - 1) < mx)
        {
            update_range(1, 1, n, cur.left + 1, cur.right - 1, 1);
            ///cout << cur.left << " " << cur.right << endl;
            //for (int i = cur.left + 1; i < cur.right; i ++)
              //  b[i] ++;
        }
    }
}


    vector < interval > to_add;
        vector < pair < int, int > > to_fix;
void fix_point(int pos)
{

    to_fix.clear();
    int root = 1, left = 0, right = n + 1;
    vector < interval > to_rem;
    while(true)
    {
        for (interval cur : act[root])
        {
            to_rem.push_back(cur);
            if (cur.pivot == cur.left)
                to_fix.push_back({cur.pivot, 0});
            else
                to_fix.push_back({cur.pivot, 1});
        }
        if (left == right)
            break;
        int mid = (left + right) / 2;
        if (pos <= mid)
            right = mid, root *= 2;
        else
            left = mid + 1, root = (root * 2) + 1;
    }
    for (interval cur : pact[pos])
    {
        to_rem.push_back(cur);
        if (cur.pivot == cur.left)
            to_fix.push_back({cur.pivot, 0});
        else
            to_fix.push_back({cur.pivot, 1});
    }
    ///sort(to_rem.begin(), to_rem.end(), cmp_interval);
    reverse(to_rem.begin(), to_rem.end());
    for (interval cur : to_rem)
    {
        //cout << "remove " << cur.left << " " << cur.right << endl;
       // if (ranges.find(cur) == ranges.end())
          //  cout << "yep" << endl;
        pact[cur.left].erase(cur);
        pact[cur.right].erase(cur);
        if (range_sum(cur.left + 1, cur.right - 1) < min(a[cur.left], a[cur.right]))
            update_range(1, 1, n, cur.left + 1, cur.right - 1, -1);
        rem_range(1, 0, n + 1, cur.left + 1, cur.right -1);
    }





}

ll fin_tree[4 * maxn];

void build_fin_tree(int root, int left, int right)
{
    if (left == right)
    {
        fin_tree[root] = a[left];
        return;
    }

    int mid = (left + right) / 2;
    build_fin_tree(root * 2, left, mid);
    build_fin_tree(root * 2 + 1, mid + 1, right);
    fin_tree[root] = max(fin_tree[root * 2], fin_tree[root * 2 + 1]);
}

void update_fin(int root, int left, int right, int pos)
{
    if (left == right)
    {
        fin_tree[root] = a[left];
        return;
    }

    int mid = (left + right) / 2;
    if (pos <= mid)
        update_fin(root * 2, left, mid, pos);
    else
        update_fin(root * 2 + 1, mid + 1, right, pos);

    fin_tree[root] = max(fin_tree[root * 2], fin_tree[root * 2 + 1]);
}

int walk_left_fin(int root, int left, int right, int qleft, int qright, ll val)
{
    if (left > qright || right < qleft || fin_tree[root] < val)
        return n + 1;

    if (left == right)
        return left;

    int mid = (left + right) / 2;
    if (left >= qleft && right <= qright)
    {
        if (fin_tree[root * 2] >= val)
            return walk_left_fin(root * 2, left, mid, qleft, qright, val);
        return walk_left_fin(root * 2 + 1, mid + 1, right, qleft, qright, val);
    }

    return min(walk_left_fin(root * 2, left, mid, qleft, qright, val),
            walk_left_fin(root * 2 + 1, mid + 1, right, qleft, qright, val));
}

void addition()
{

    to_add.clear();
    for (pair < int, int > cur : to_fix)
    {
        if (cur.second == 0)
        {
            int df = walk_left_fin(1, 0, n + 1, cur.first + 1, n + 1, a[cur.first]); ///cur.first + 1;
            //while(a[df] < a[cur.first])
              //  df ++;
            to_add.push_back(interval(cur.first, df, cur.first));
        }
        else
        {
            int df = cur.first - 1;
            while(a[df] < a[cur.first])
                df --;
            to_add.push_back(interval(df, cur.first, cur.first));
        }
    }
    sort(to_add.begin(), to_add.end(), cmp_interval);
    ///reverse(to_add.begin(), to_add.end());
    for (interval cur : to_add)
    {
        pact[cur.left].insert(cur);
        pact[cur.right].insert(cur);
        if (range_sum(cur.left + 1, cur.right - 1) < min(a[cur.left], a[cur.right]))
            update_range(1, 1, n, cur.left + 1, cur.right - 1, 1);
        ///cout << "added " << cur.left << " : " << cur.right << endl;
        add_range(1, 0, n + 1, cur.left + 1, cur.right - 1, cur);
    }
}
void simulate()
{

    for (int i = 1; i <= n; i ++)
        update_fen(i, a[i]);
    get_ranges();

    restructure();

    for (int i = 1; i <= n; i ++)
    {
        values[i] = a[i] - query_fen(i - 1);
    }
    left_tree.build_tree(1, 1, n);

    for (int i = 1; i <= n; i ++)
    {
        values[i] = a[i] + query_fen(i);
    }
    right_tree.build_tree(1, 1, n);

    build_fin_tree(1, 0, n + 1);
    for (int i = 1; i <= q; i ++)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int idx;
            ll x;
            cin >> idx >> x;
            fix_point(idx);
            update_fen(idx, x - a[idx]);
            left_tree.update_range(1, 1, n, idx + 1, n, - (x - a[idx]));
            left_tree.update_range(1, 1, n, idx, idx, (x - a[idx]));
            right_tree.update_range(1, 1, n, idx, n, (x - a[idx]));
            right_tree.update_range(1, 1, n, idx, idx, (x - a[idx]));
            a[idx] = x;
            update_fin(1, 0, n + 1, idx);
            addition();
        }
        else
        {
            int l, r;
            cin >> l >> r;
            solve_query(l, r);
        }
    }
}
void solve()
{
    input();
    simulate();
}

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int main()
{
    ///freopen("test.txt", "r", stdin);
    speed();
    solve();
    return 0;
}
/*
12
32 32 4 1 1 1 1 4 4 16 32 128
1
2 8 10


*/

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 31064 KB Output is correct
2 Correct 5 ms 31220 KB Output is correct
3 Correct 5 ms 31240 KB Output is correct
4 Correct 6 ms 31240 KB Output is correct
5 Correct 13 ms 31444 KB Output is correct
6 Correct 8 ms 31324 KB Output is correct
7 Correct 12 ms 31748 KB Output is correct
8 Correct 8 ms 31324 KB Output is correct
9 Correct 8 ms 31324 KB Output is correct
10 Correct 9 ms 31324 KB Output is correct
11 Correct 7 ms 31304 KB Output is correct
12 Correct 10 ms 31324 KB Output is correct
13 Correct 8 ms 31324 KB Output is correct
14 Correct 8 ms 31440 KB Output is correct
15 Correct 10 ms 31320 KB Output is correct
16 Correct 7 ms 31324 KB Output is correct
17 Correct 11 ms 31324 KB Output is correct
18 Correct 7 ms 31320 KB Output is correct
19 Correct 8 ms 31320 KB Output is correct
20 Correct 7 ms 31320 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 31068 KB Output is correct
2 Correct 241 ms 83100 KB Output is correct
3 Correct 212 ms 82040 KB Output is correct
4 Correct 208 ms 83040 KB Output is correct
5 Correct 203 ms 81952 KB Output is correct
6 Correct 208 ms 80368 KB Output is correct
7 Correct 214 ms 79556 KB Output is correct
8 Correct 194 ms 80372 KB Output is correct
9 Correct 194 ms 79752 KB Output is correct
10 Correct 200 ms 82860 KB Output is correct
11 Correct 194 ms 79844 KB Output is correct
12 Correct 203 ms 79828 KB Output is correct
13 Correct 191 ms 79856 KB Output is correct
14 Correct 183 ms 79556 KB Output is correct
15 Correct 201 ms 80332 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 31064 KB Output is correct
2 Correct 5 ms 31220 KB Output is correct
3 Correct 5 ms 31240 KB Output is correct
4 Correct 6 ms 31240 KB Output is correct
5 Correct 13 ms 31444 KB Output is correct
6 Correct 8 ms 31324 KB Output is correct
7 Correct 12 ms 31748 KB Output is correct
8 Correct 8 ms 31324 KB Output is correct
9 Correct 8 ms 31324 KB Output is correct
10 Correct 9 ms 31324 KB Output is correct
11 Correct 7 ms 31304 KB Output is correct
12 Correct 10 ms 31324 KB Output is correct
13 Correct 8 ms 31324 KB Output is correct
14 Correct 8 ms 31440 KB Output is correct
15 Correct 10 ms 31320 KB Output is correct
16 Correct 7 ms 31324 KB Output is correct
17 Correct 11 ms 31324 KB Output is correct
18 Correct 7 ms 31320 KB Output is correct
19 Correct 8 ms 31320 KB Output is correct
20 Correct 7 ms 31320 KB Output is correct
21 Correct 5 ms 31068 KB Output is correct
22 Correct 241 ms 83100 KB Output is correct
23 Correct 212 ms 82040 KB Output is correct
24 Correct 208 ms 83040 KB Output is correct
25 Correct 203 ms 81952 KB Output is correct
26 Correct 208 ms 80368 KB Output is correct
27 Correct 214 ms 79556 KB Output is correct
28 Correct 194 ms 80372 KB Output is correct
29 Correct 194 ms 79752 KB Output is correct
30 Correct 200 ms 82860 KB Output is correct
31 Correct 194 ms 79844 KB Output is correct
32 Correct 203 ms 79828 KB Output is correct
33 Correct 191 ms 79856 KB Output is correct
34 Correct 183 ms 79556 KB Output is correct
35 Correct 201 ms 80332 KB Output is correct
36 Correct 253 ms 83096 KB Output is correct
37 Correct 227 ms 82108 KB Output is correct
38 Correct 204 ms 82144 KB Output is correct
39 Correct 258 ms 83256 KB Output is correct
40 Correct 202 ms 81860 KB Output is correct
41 Correct 208 ms 80608 KB Output is correct
42 Correct 204 ms 80376 KB Output is correct
43 Correct 229 ms 80096 KB Output is correct
44 Correct 193 ms 79552 KB Output is correct
45 Correct 285 ms 82740 KB Output is correct
46 Correct 224 ms 82628 KB Output is correct
47 Correct 186 ms 79900 KB Output is correct
48 Correct 232 ms 80064 KB Output is correct
49 Correct 199 ms 79904 KB Output is correct
50 Correct 186 ms 79676 KB Output is correct
51 Correct 200 ms 79860 KB Output is correct
52 Correct 187 ms 79636 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 31068 KB Output is correct
2 Correct 241 ms 83100 KB Output is correct
3 Correct 212 ms 82040 KB Output is correct
4 Correct 208 ms 83040 KB Output is correct
5 Correct 203 ms 81952 KB Output is correct
6 Correct 208 ms 80368 KB Output is correct
7 Correct 214 ms 79556 KB Output is correct
8 Correct 194 ms 80372 KB Output is correct
9 Correct 194 ms 79752 KB Output is correct
10 Correct 200 ms 82860 KB Output is correct
11 Correct 194 ms 79844 KB Output is correct
12 Correct 203 ms 79828 KB Output is correct
13 Correct 191 ms 79856 KB Output is correct
14 Correct 183 ms 79556 KB Output is correct
15 Correct 201 ms 80332 KB Output is correct
16 Correct 6 ms 31068 KB Output is correct
17 Correct 361 ms 82296 KB Output is correct
18 Correct 370 ms 83492 KB Output is correct
19 Correct 397 ms 82368 KB Output is correct
20 Correct 368 ms 82368 KB Output is correct
21 Correct 350 ms 82428 KB Output is correct
22 Correct 351 ms 83476 KB Output is correct
23 Correct 353 ms 82112 KB Output is correct
24 Correct 388 ms 82436 KB Output is correct
25 Correct 360 ms 82252 KB Output is correct
26 Correct 365 ms 82336 KB Output is correct
27 Correct 343 ms 81040 KB Output is correct
28 Correct 327 ms 81088 KB Output is correct
29 Correct 337 ms 81400 KB Output is correct
30 Correct 339 ms 79692 KB Output is correct
31 Correct 339 ms 79636 KB Output is correct
32 Correct 406 ms 80036 KB Output is correct
33 Correct 378 ms 83908 KB Output is correct
34 Correct 354 ms 79812 KB Output is correct
35 Correct 348 ms 80052 KB Output is correct
36 Correct 369 ms 82696 KB Output is correct
37 Correct 320 ms 80512 KB Output is correct
38 Correct 331 ms 79948 KB Output is correct
39 Correct 332 ms 80292 KB Output is correct
40 Correct 311 ms 80456 KB Output is correct

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 31068 KB Output is correct
2 Correct 241 ms 83100 KB Output is correct
3 Correct 212 ms 82040 KB Output is correct
4 Correct 208 ms 83040 KB Output is correct
5 Correct 203 ms 81952 KB Output is correct
6 Correct 208 ms 80368 KB Output is correct
7 Correct 214 ms 79556 KB Output is correct
8 Correct 194 ms 80372 KB Output is correct
9 Correct 194 ms 79752 KB Output is correct
10 Correct 200 ms 82860 KB Output is correct
11 Correct 194 ms 79844 KB Output is correct
12 Correct 203 ms 79828 KB Output is correct
13 Correct 191 ms 79856 KB Output is correct
14 Correct 183 ms 79556 KB Output is correct
15 Correct 201 ms 80332 KB Output is correct
16 Correct 5 ms 31068 KB Output is correct
17 Correct 3116 ms 87964 KB Output is correct
18 Correct 3719 ms 90384 KB Output is correct
19 Correct 2051 ms 82660 KB Output is correct
20 Correct 2790 ms 89456 KB Output is correct
21 Correct 2968 ms 88292 KB Output is correct
22 Correct 3706 ms 90180 KB Output is correct
23 Correct 2464 ms 82948 KB Output is correct
24 Correct 3285 ms 90060 KB Output is correct
25 Correct 2183 ms 83264 KB Output is correct
26 Correct 3723 ms 83736 KB Output is correct
27 Execution timed out 4057 ms 85128 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 31064 KB Output is correct
2 Correct 5 ms 31220 KB Output is correct
3 Correct 5 ms 31240 KB Output is correct
4 Correct 6 ms 31240 KB Output is correct
5 Correct 13 ms 31444 KB Output is correct
6 Correct 8 ms 31324 KB Output is correct
7 Correct 12 ms 31748 KB Output is correct
8 Correct 8 ms 31324 KB Output is correct
9 Correct 8 ms 31324 KB Output is correct
10 Correct 9 ms 31324 KB Output is correct
11 Correct 7 ms 31304 KB Output is correct
12 Correct 10 ms 31324 KB Output is correct
13 Correct 8 ms 31324 KB Output is correct
14 Correct 8 ms 31440 KB Output is correct
15 Correct 10 ms 31320 KB Output is correct
16 Correct 7 ms 31324 KB Output is correct
17 Correct 11 ms 31324 KB Output is correct
18 Correct 7 ms 31320 KB Output is correct
19 Correct 8 ms 31320 KB Output is correct
20 Correct 7 ms 31320 KB Output is correct
21 Correct 5 ms 31068 KB Output is correct
22 Correct 241 ms 83100 KB Output is correct
23 Correct 212 ms 82040 KB Output is correct
24 Correct 208 ms 83040 KB Output is correct
25 Correct 203 ms 81952 KB Output is correct
26 Correct 208 ms 80368 KB Output is correct
27 Correct 214 ms 79556 KB Output is correct
28 Correct 194 ms 80372 KB Output is correct
29 Correct 194 ms 79752 KB Output is correct
30 Correct 200 ms 82860 KB Output is correct
31 Correct 194 ms 79844 KB Output is correct
32 Correct 203 ms 79828 KB Output is correct
33 Correct 191 ms 79856 KB Output is correct
34 Correct 183 ms 79556 KB Output is correct
35 Correct 201 ms 80332 KB Output is correct
36 Correct 253 ms 83096 KB Output is correct
37 Correct 227 ms 82108 KB Output is correct
38 Correct 204 ms 82144 KB Output is correct
39 Correct 258 ms 83256 KB Output is correct
40 Correct 202 ms 81860 KB Output is correct
41 Correct 208 ms 80608 KB Output is correct
42 Correct 204 ms 80376 KB Output is correct
43 Correct 229 ms 80096 KB Output is correct
44 Correct 193 ms 79552 KB Output is correct
45 Correct 285 ms 82740 KB Output is correct
46 Correct 224 ms 82628 KB Output is correct
47 Correct 186 ms 79900 KB Output is correct
48 Correct 232 ms 80064 KB Output is correct
49 Correct 199 ms 79904 KB Output is correct
50 Correct 186 ms 79676 KB Output is correct
51 Correct 200 ms 79860 KB Output is correct
52 Correct 187 ms 79636 KB Output is correct
53 Correct 6 ms 31068 KB Output is correct
54 Correct 361 ms 82296 KB Output is correct
55 Correct 370 ms 83492 KB Output is correct
56 Correct 397 ms 82368 KB Output is correct
57 Correct 368 ms 82368 KB Output is correct
58 Correct 350 ms 82428 KB Output is correct
59 Correct 351 ms 83476 KB Output is correct
60 Correct 353 ms 82112 KB Output is correct
61 Correct 388 ms 82436 KB Output is correct
62 Correct 360 ms 82252 KB Output is correct
63 Correct 365 ms 82336 KB Output is correct
64 Correct 343 ms 81040 KB Output is correct
65 Correct 327 ms 81088 KB Output is correct
66 Correct 337 ms 81400 KB Output is correct
67 Correct 339 ms 79692 KB Output is correct
68 Correct 339 ms 79636 KB Output is correct
69 Correct 406 ms 80036 KB Output is correct
70 Correct 378 ms 83908 KB Output is correct
71 Correct 354 ms 79812 KB Output is correct
72 Correct 348 ms 80052 KB Output is correct
73 Correct 369 ms 82696 KB Output is correct
74 Correct 320 ms 80512 KB Output is correct
75 Correct 331 ms 79948 KB Output is correct
76 Correct 332 ms 80292 KB Output is correct
77 Correct 311 ms 80456 KB Output is correct
78 Correct 5 ms 31068 KB Output is correct
79 Correct 3116 ms 87964 KB Output is correct
80 Correct 3719 ms 90384 KB Output is correct
81 Correct 2051 ms 82660 KB Output is correct
82 Correct 2790 ms 89456 KB Output is correct
83 Correct 2968 ms 88292 KB Output is correct
84 Correct 3706 ms 90180 KB Output is correct
85 Correct 2464 ms 82948 KB Output is correct
86 Correct 3285 ms 90060 KB Output is correct
87 Correct 2183 ms 83264 KB Output is correct
88 Correct 3723 ms 83736 KB Output is correct
89 Execution timed out 4057 ms 85128 KB Time limit exceeded
90 Halted 0 ms 0 KB -