oj.uz

Submission #876518

# Submission time Handle Problem Language Result Execution time Memory
876518 2023-11-21T21:18:27 Z danikoynov Fish 2 (JOI22_fish2) C++14
100 / 100
 3733 ms 94116 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));
}

int walk_right_fin(int root, int left, int right, int qleft, int qright, ll val)
{
    if (left > qright || right < qleft || fin_tree[root] < val)
        return 0;

    if (left == right)
        return left;

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

    return max(walk_right_fin(root * 2, left, mid, qleft, qright, val),
            walk_right_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 = walk_right_fin(1, 0, n + 1, 0, cur.first - 1, a[cur.first]);
            /**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

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31068 KB Output is correct
2 Correct 5 ms 31068 KB Output is correct
3 Correct 7 ms 31068 KB Output is correct
4 Correct 6 ms 31080 KB Output is correct
5 Correct 14 ms 31496 KB Output is correct
6 Correct 8 ms 31320 KB Output is correct
7 Correct 13 ms 31320 KB Output is correct
8 Correct 9 ms 31324 KB Output is correct
9 Correct 9 ms 31324 KB Output is correct
10 Correct 9 ms 31324 KB Output is correct
11 Correct 7 ms 31476 KB Output is correct
12 Correct 11 ms 31324 KB Output is correct
13 Correct 8 ms 31324 KB Output is correct
14 Correct 9 ms 31324 KB Output is correct
15 Correct 12 ms 31504 KB Output is correct
16 Correct 7 ms 31320 KB Output is correct
17 Correct 10 ms 31324 KB Output is correct
18 Correct 8 ms 31484 KB Output is correct
19 Correct 9 ms 31324 KB Output is correct
20 Correct 8 ms 31320 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31068 KB Output is correct
2 Correct 210 ms 83172 KB Output is correct
3 Correct 222 ms 81980 KB Output is correct
4 Correct 211 ms 83172 KB Output is correct
5 Correct 224 ms 82112 KB Output is correct
6 Correct 191 ms 80536 KB Output is correct
7 Correct 200 ms 79624 KB Output is correct
8 Correct 192 ms 80504 KB Output is correct
9 Correct 196 ms 79616 KB Output is correct
10 Correct 207 ms 82924 KB Output is correct
11 Correct 192 ms 79840 KB Output is correct
12 Correct 214 ms 79796 KB Output is correct
13 Correct 188 ms 79716 KB Output is correct
14 Correct 179 ms 79604 KB Output is correct
15 Correct 189 ms 79812 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31068 KB Output is correct
2 Correct 5 ms 31068 KB Output is correct
3 Correct 7 ms 31068 KB Output is correct
4 Correct 6 ms 31080 KB Output is correct
5 Correct 14 ms 31496 KB Output is correct
6 Correct 8 ms 31320 KB Output is correct
7 Correct 13 ms 31320 KB Output is correct
8 Correct 9 ms 31324 KB Output is correct
9 Correct 9 ms 31324 KB Output is correct
10 Correct 9 ms 31324 KB Output is correct
11 Correct 7 ms 31476 KB Output is correct
12 Correct 11 ms 31324 KB Output is correct
13 Correct 8 ms 31324 KB Output is correct
14 Correct 9 ms 31324 KB Output is correct
15 Correct 12 ms 31504 KB Output is correct
16 Correct 7 ms 31320 KB Output is correct
17 Correct 10 ms 31324 KB Output is correct
18 Correct 8 ms 31484 KB Output is correct
19 Correct 9 ms 31324 KB Output is correct
20 Correct 8 ms 31320 KB Output is correct
21 Correct 5 ms 31068 KB Output is correct
22 Correct 210 ms 83172 KB Output is correct
23 Correct 222 ms 81980 KB Output is correct
24 Correct 211 ms 83172 KB Output is correct
25 Correct 224 ms 82112 KB Output is correct
26 Correct 191 ms 80536 KB Output is correct
27 Correct 200 ms 79624 KB Output is correct
28 Correct 192 ms 80504 KB Output is correct
29 Correct 196 ms 79616 KB Output is correct
30 Correct 207 ms 82924 KB Output is correct
31 Correct 192 ms 79840 KB Output is correct
32 Correct 214 ms 79796 KB Output is correct
33 Correct 188 ms 79716 KB Output is correct
34 Correct 179 ms 79604 KB Output is correct
35 Correct 189 ms 79812 KB Output is correct
36 Correct 235 ms 83100 KB Output is correct
37 Correct 214 ms 81904 KB Output is correct
38 Correct 201 ms 81908 KB Output is correct
39 Correct 241 ms 83212 KB Output is correct
40 Correct 202 ms 81880 KB Output is correct
41 Correct 205 ms 80576 KB Output is correct
42 Correct 209 ms 80584 KB Output is correct
43 Correct 204 ms 79984 KB Output is correct
44 Correct 195 ms 79572 KB Output is correct
45 Correct 239 ms 82656 KB Output is correct
46 Correct 232 ms 82760 KB Output is correct
47 Correct 179 ms 79896 KB Output is correct
48 Correct 206 ms 80052 KB Output is correct
49 Correct 201 ms 80304 KB Output is correct
50 Correct 191 ms 79784 KB Output is correct
51 Correct 203 ms 79908 KB Output is correct
52 Correct 187 ms 79812 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31068 KB Output is correct
2 Correct 210 ms 83172 KB Output is correct
3 Correct 222 ms 81980 KB Output is correct
4 Correct 211 ms 83172 KB Output is correct
5 Correct 224 ms 82112 KB Output is correct
6 Correct 191 ms 80536 KB Output is correct
7 Correct 200 ms 79624 KB Output is correct
8 Correct 192 ms 80504 KB Output is correct
9 Correct 196 ms 79616 KB Output is correct
10 Correct 207 ms 82924 KB Output is correct
11 Correct 192 ms 79840 KB Output is correct
12 Correct 214 ms 79796 KB Output is correct
13 Correct 188 ms 79716 KB Output is correct
14 Correct 179 ms 79604 KB Output is correct
15 Correct 189 ms 79812 KB Output is correct
16 Correct 5 ms 31064 KB Output is correct
17 Correct 370 ms 82368 KB Output is correct
18 Correct 396 ms 83456 KB Output is correct
19 Correct 362 ms 82272 KB Output is correct
20 Correct 399 ms 82228 KB Output is correct
21 Correct 360 ms 82372 KB Output is correct
22 Correct 379 ms 83328 KB Output is correct
23 Correct 348 ms 82128 KB Output is correct
24 Correct 372 ms 82348 KB Output is correct
25 Correct 365 ms 82248 KB Output is correct
26 Correct 370 ms 82116 KB Output is correct
27 Correct 350 ms 81092 KB Output is correct
28 Correct 366 ms 81084 KB Output is correct
29 Correct 331 ms 81388 KB Output is correct
30 Correct 358 ms 79764 KB Output is correct
31 Correct 341 ms 80060 KB Output is correct
32 Correct 363 ms 80068 KB Output is correct
33 Correct 397 ms 83628 KB Output is correct
34 Correct 367 ms 80064 KB Output is correct
35 Correct 339 ms 79668 KB Output is correct
36 Correct 354 ms 82672 KB Output is correct
37 Correct 346 ms 80120 KB Output is correct
38 Correct 318 ms 80176 KB Output is correct
39 Correct 331 ms 80136 KB Output is correct
40 Correct 312 ms 80320 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31068 KB Output is correct
2 Correct 210 ms 83172 KB Output is correct
3 Correct 222 ms 81980 KB Output is correct
4 Correct 211 ms 83172 KB Output is correct
5 Correct 224 ms 82112 KB Output is correct
6 Correct 191 ms 80536 KB Output is correct
7 Correct 200 ms 79624 KB Output is correct
8 Correct 192 ms 80504 KB Output is correct
9 Correct 196 ms 79616 KB Output is correct
10 Correct 207 ms 82924 KB Output is correct
11 Correct 192 ms 79840 KB Output is correct
12 Correct 214 ms 79796 KB Output is correct
13 Correct 188 ms 79716 KB Output is correct
14 Correct 179 ms 79604 KB Output is correct
15 Correct 189 ms 79812 KB Output is correct
16 Correct 5 ms 31068 KB Output is correct
17 Correct 3567 ms 87728 KB Output is correct
18 Correct 3587 ms 90492 KB Output is correct
19 Correct 2095 ms 82880 KB Output is correct
20 Correct 2556 ms 89552 KB Output is correct
21 Correct 3261 ms 88160 KB Output is correct
22 Correct 3537 ms 90424 KB Output is correct
23 Correct 2521 ms 83024 KB Output is correct
24 Correct 3140 ms 90232 KB Output is correct
25 Correct 2435 ms 82812 KB Output is correct
26 Correct 2552 ms 83828 KB Output is correct
27 Correct 3497 ms 84912 KB Output is correct
28 Correct 2549 ms 87892 KB Output is correct
29 Correct 2821 ms 86708 KB Output is correct
30 Correct 3468 ms 87272 KB Output is correct
31 Correct 3182 ms 88444 KB Output is correct
32 Correct 3733 ms 90396 KB Output is correct
33 Correct 1263 ms 82016 KB Output is correct
34 Correct 3476 ms 92276 KB Output is correct
35 Correct 1210 ms 85344 KB Output is correct
36 Correct 3012 ms 89224 KB Output is correct
37 Correct 2844 ms 86664 KB Output is correct
38 Correct 1728 ms 85024 KB Output is correct
39 Correct 1352 ms 85592 KB Output is correct
40 Correct 623 ms 83604 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31068 KB Output is correct
2 Correct 5 ms 31068 KB Output is correct
3 Correct 7 ms 31068 KB Output is correct
4 Correct 6 ms 31080 KB Output is correct
5 Correct 14 ms 31496 KB Output is correct
6 Correct 8 ms 31320 KB Output is correct
7 Correct 13 ms 31320 KB Output is correct
8 Correct 9 ms 31324 KB Output is correct
9 Correct 9 ms 31324 KB Output is correct
10 Correct 9 ms 31324 KB Output is correct
11 Correct 7 ms 31476 KB Output is correct
12 Correct 11 ms 31324 KB Output is correct
13 Correct 8 ms 31324 KB Output is correct
14 Correct 9 ms 31324 KB Output is correct
15 Correct 12 ms 31504 KB Output is correct
16 Correct 7 ms 31320 KB Output is correct
17 Correct 10 ms 31324 KB Output is correct
18 Correct 8 ms 31484 KB Output is correct
19 Correct 9 ms 31324 KB Output is correct
20 Correct 8 ms 31320 KB Output is correct
21 Correct 5 ms 31068 KB Output is correct
22 Correct 210 ms 83172 KB Output is correct
23 Correct 222 ms 81980 KB Output is correct
24 Correct 211 ms 83172 KB Output is correct
25 Correct 224 ms 82112 KB Output is correct
26 Correct 191 ms 80536 KB Output is correct
27 Correct 200 ms 79624 KB Output is correct
28 Correct 192 ms 80504 KB Output is correct
29 Correct 196 ms 79616 KB Output is correct
30 Correct 207 ms 82924 KB Output is correct
31 Correct 192 ms 79840 KB Output is correct
32 Correct 214 ms 79796 KB Output is correct
33 Correct 188 ms 79716 KB Output is correct
34 Correct 179 ms 79604 KB Output is correct
35 Correct 189 ms 79812 KB Output is correct
36 Correct 235 ms 83100 KB Output is correct
37 Correct 214 ms 81904 KB Output is correct
38 Correct 201 ms 81908 KB Output is correct
39 Correct 241 ms 83212 KB Output is correct
40 Correct 202 ms 81880 KB Output is correct
41 Correct 205 ms 80576 KB Output is correct
42 Correct 209 ms 80584 KB Output is correct
43 Correct 204 ms 79984 KB Output is correct
44 Correct 195 ms 79572 KB Output is correct
45 Correct 239 ms 82656 KB Output is correct
46 Correct 232 ms 82760 KB Output is correct
47 Correct 179 ms 79896 KB Output is correct
48 Correct 206 ms 80052 KB Output is correct
49 Correct 201 ms 80304 KB Output is correct
50 Correct 191 ms 79784 KB Output is correct
51 Correct 203 ms 79908 KB Output is correct
52 Correct 187 ms 79812 KB Output is correct
53 Correct 5 ms 31064 KB Output is correct
54 Correct 370 ms 82368 KB Output is correct
55 Correct 396 ms 83456 KB Output is correct
56 Correct 362 ms 82272 KB Output is correct
57 Correct 399 ms 82228 KB Output is correct
58 Correct 360 ms 82372 KB Output is correct
59 Correct 379 ms 83328 KB Output is correct
60 Correct 348 ms 82128 KB Output is correct
61 Correct 372 ms 82348 KB Output is correct
62 Correct 365 ms 82248 KB Output is correct
63 Correct 370 ms 82116 KB Output is correct
64 Correct 350 ms 81092 KB Output is correct
65 Correct 366 ms 81084 KB Output is correct
66 Correct 331 ms 81388 KB Output is correct
67 Correct 358 ms 79764 KB Output is correct
68 Correct 341 ms 80060 KB Output is correct
69 Correct 363 ms 80068 KB Output is correct
70 Correct 397 ms 83628 KB Output is correct
71 Correct 367 ms 80064 KB Output is correct
72 Correct 339 ms 79668 KB Output is correct
73 Correct 354 ms 82672 KB Output is correct
74 Correct 346 ms 80120 KB Output is correct
75 Correct 318 ms 80176 KB Output is correct
76 Correct 331 ms 80136 KB Output is correct
77 Correct 312 ms 80320 KB Output is correct
78 Correct 5 ms 31068 KB Output is correct
79 Correct 3567 ms 87728 KB Output is correct
80 Correct 3587 ms 90492 KB Output is correct
81 Correct 2095 ms 82880 KB Output is correct
82 Correct 2556 ms 89552 KB Output is correct
83 Correct 3261 ms 88160 KB Output is correct
84 Correct 3537 ms 90424 KB Output is correct
85 Correct 2521 ms 83024 KB Output is correct
86 Correct 3140 ms 90232 KB Output is correct
87 Correct 2435 ms 82812 KB Output is correct
88 Correct 2552 ms 83828 KB Output is correct
89 Correct 3497 ms 84912 KB Output is correct
90 Correct 2549 ms 87892 KB Output is correct
91 Correct 2821 ms 86708 KB Output is correct
92 Correct 3468 ms 87272 KB Output is correct
93 Correct 3182 ms 88444 KB Output is correct
94 Correct 3733 ms 90396 KB Output is correct
95 Correct 1263 ms 82016 KB Output is correct
96 Correct 3476 ms 92276 KB Output is correct
97 Correct 1210 ms 85344 KB Output is correct
98 Correct 3012 ms 89224 KB Output is correct
99 Correct 2844 ms 86664 KB Output is correct
100 Correct 1728 ms 85024 KB Output is correct
101 Correct 1352 ms 85592 KB Output is correct
102 Correct 623 ms 83604 KB Output is correct
103 Correct 2729 ms 84428 KB Output is correct
104 Correct 3540 ms 93732 KB Output is correct
105 Correct 700 ms 84432 KB Output is correct
106 Correct 883 ms 87464 KB Output is correct
107 Correct 2904 ms 84316 KB Output is correct
108 Correct 3423 ms 94116 KB Output is correct
109 Correct 1150 ms 84932 KB Output is correct
110 Correct 1538 ms 89608 KB Output is correct
111 Correct 695 ms 84688 KB Output is correct
112 Correct 831 ms 87348 KB Output is correct
113 Correct 2883 ms 86584 KB Output is correct
114 Correct 727 ms 83908 KB Output is correct
115 Correct 3330 ms 88420 KB Output is correct
116 Correct 1851 ms 86896 KB Output is correct
117 Correct 1111 ms 84624 KB Output is correct
118 Correct 750 ms 83908 KB Output is correct
119 Correct 3467 ms 87320 KB Output is correct
120 Correct 2916 ms 88412 KB Output is correct
121 Correct 1505 ms 86160 KB Output is correct
122 Correct 3672 ms 89924 KB Output is correct
123 Correct 958 ms 82332 KB Output is correct
124 Correct 1214 ms 85840 KB Output is correct
125 Correct 457 ms 81292 KB Output is correct
126 Correct 885 ms 84796 KB Output is correct
127 Correct 3094 ms 86624 KB Output is correct
128 Correct 687 ms 83200 KB Output is correct
129 Correct 1362 ms 85488 KB Output is correct
130 Correct 658 ms 84040 KB Output is correct