oj.uz

Submission #976449

# Submission time Handle Problem Language Result Execution time Memory
976449 2024-05-06T14:59:50 Z underwaterkillerwhale Food Court (JOI21_foodcourt) C++17
100 / 100
 777 ms 129816 KB 
#include <bits/stdc++.h>
#define se              second
#define fs              first
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N = 3e5 + 7;
const ll Mod = 1e9 + 7;
const int szBL = 916;
const ll INF = 1e18 + 7;
const int BASE = 137;

struct Data3 {
    ll idx, pos, id;
};

int n, m, Q;
int color[N];
vector<pair<ll,int>> q1[N];
vector<Data3> q3[N];

struct Segment_Tree_Beats {
    int Range;
    struct Node {
        ll lz, mn1, mn2, mnc, sum;
        Node (ll lz = 0, ll mn1 = 0, ll mn2 = INF, ll mnc = 0, ll sum = 0) : lz(lz), mn1(mn1), mn2(mn2), mnc(mnc), sum(sum) {};
    };
    Node st[N << 2];

    void init (int n) {
        Range = n;
    }

    void Merge (Node &cur, Node &left, Node &right){
        cur.sum = left.sum + right.sum;
        if (left.mn1 <= right.mn1) {
            cur.mn1 = left.mn1, cur.mnc = left.mnc;
            if (left.mn1 == right.mn1) cur.mnc += right.mnc, cur.mn2 = min(left.mn2, right.mn2);
            else cur.mn2 = min(left.mn2, right.mn1);
        }
        else {
            cur.mn1 = right.mn1, cur.mnc = right.mnc;
            cur.mn2 = min(left.mn1, right.mn2);
        }
    }

    void build (int id, int l, int r) {
        if (l == r) {
            st[id].mn1 = 0;
            st[id].mn2 = INF;
            st[id].mnc = 1;
            st[id].sum = 0;
            return;
        }
        int mid = l + r >> 1;
        build (id << 1, l, mid);
        build (id << 1 | 1, mid + 1, r);
        Merge (st[id], st[id << 1], st[id << 1 | 1]);
    }
    void down (int id, int l, int r) {
        int mid = l + r >> 1;
        int left = (id << 1), right = (id << 1 | 1);
        st[left].sum += st[id].lz * (mid - l + 1);
        st[right].sum += st[id].lz * (r - mid);
        rep (i, left, right) {
            st[i].mn1 += st[id].lz;
            st[i].lz += st[id].lz;
            if (st[i].mn1 < st[id].mn1) {
                st[i].sum += 1LL * (st[id].mn1 - st[i].mn1) * st[i].mnc;
                st[i].mn1 = st[id].mn1;
            }
            if (st[i].mn2 != INF) st[i].mn2 += st[id].lz;
        }
        st[id].lz = 0;
    }

    void update1 (int id, int l, int r, int u, int v, ll val) {
        if (l > v  || r < u) return;
        if (l >= u && r <= v) {
            st[id].sum += 1LL * (r - l + 1) * val;
            st[id].lz += val;
            st[id].mn1 += val;
            if(st[id].mn2 != INF) st[id].mn2 += val;
            return;
        }
        int mid = l + r >> 1;
        down (id, l, r);
        update1 (id << 1, l, mid, u, v, val);
        update1 (id << 1 | 1, mid + 1, r, u, v, val);
        Merge (st[id], st[id << 1], st[id << 1 | 1]);
    }

    void update2 (int id, int l, int r, int u, int v, ll val) {
        if (l > v || r < u || st[id].mn1 >= val) return;
        if (l >= u && r <= v && st[id].mn2 > val) {
            st[id].sum += 1LL * (val - st[id].mn1) * st[id].mnc;
            st[id].mn1 = val;
//            cout << id <<" "<<l<<" "<<r<<" "<<st[id].sum<<" "<<st[id].mn1<<" "<<st[id].mnc<<"hihih\n";
            return;
        }
        int mid = l + r >> 1;
        down (id, l, r);
        update2 (id << 1, l, mid, u, v, val);
        update2 (id << 1 | 1, mid + 1, r, u, v, val);
        Merge (st[id], st[id << 1], st[id << 1 | 1]);
    }

    ll get (int id, int l, int r, int u, int v) {
        if (l > v || r < u) return 0;
        if (l >= u && r <= v)
            return st[id].sum;
        int mid = l + r >> 1;
        down(id, l, r);
        return get (id << 1, l, mid, u, v) + get (id << 1 | 1, mid + 1, r, u, v);
    }

    void update1 (int u, int v, ll val) {
        update1 (1, 1, Range, u, v, val);
    }
    void update2 (int u, int v, ll val) {
        update2 (1, 1, Range, u, v, val);
    }
    ll get (int u, int v) {
        return get (1, 1, Range, u, v);
    }
}ST, Tot;

struct Fenwick_Tree {
    int Range;
    ll fen[N];
    void init (int n) { Range = n; }
    void update (int pos, ll val) {
        for (; pos <= Range; pos += pos & -pos) fen[pos] += val;
    }
    ll get (int pos) {
        ll res = 0;
        for (; pos > 0; pos -= pos & -pos) res += fen[pos];
        return res;
    }
}BIT;

void solution() {
    cin >> n >> m >> Q;
    ST.init(n);
    ST.build(1, 1, n);
    Tot.init(n);
    int numq3 = 0;
    rep (i, 1, Q) {
        int typ;
        cin >> typ;
        if (typ == 1) {
            ll L, R, C, K;
            cin >> L >> R >> C >> K;
            color[i] = C;
            q1[L].push_back({K, i});
            q1[R + 1].push_back({-K, i});
            ST.update1 (L, R, K);
            Tot.update1 (L, R, K);
        }
        else if (typ == 2) {
            ll L, R, K;
            cin >> L >> R >> K;
            ST.update1 (L, R, -K);
            ST.update2 (L, R, 0);
//            cout <<i<<" typ2 :"<<ST.get(3, 3)<<"\n";
        }
        else {
            ll pos, X;
            cin >> pos >> X;
            ll idx = Tot.get (pos, pos) - ST.get (pos, pos) + X;
//            cout << i<<": "<<idx<<" "<<Tot.get (pos, pos)<<" "<<ST.get (pos, pos) <<"\n";
            q3[pos].push_back({idx, numq3++, i});
        }
    }
    vector<int> Ans(numq3);
    BIT.init(Q + 1);
    rep (i, 1, n) {
        iter (&id, q1[i]) {
            BIT.update (id.se, id.fs);
        }
        iter (&id, q3[i]) {
            int pos; {
                int lf = 1, rt = id.id;
                while (lf < rt) {
                    int mid = lf + rt >> 1;
                    if (BIT.get(mid) >= id.idx) rt = mid;
                    else lf = mid + 1;
                }
                pos = lf;
            }
//            cout << id.id<<":"<<pos<<" "<<BIT.get(pos) <<"\n";
            if (BIT.get (pos) >= id.idx) Ans[id.pos] = color[pos];
            else Ans[id.pos] = 0;
        }
    }
    iter (&id, Ans) cout << id <<"\n";
}



#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);

int main () {
//    file("c");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll num_Test = 1;
//    cin >> num_Test;
    while(num_Test--)
        solution();
}
/*
18 3
2 5
6 21
13 19
9 17
14 17
19 20
2 16
2 10
9 14
19 20
14 16
1 3
17 19
14 21
18 19
4 7
5 12
1 13

*/

Compilation message

foodcourt.cpp: In member function 'void Segment_Tree_Beats::build(int, int, int)':
foodcourt.cpp:68:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |         int mid = l + r >> 1;
      |                   ~~^~~
foodcourt.cpp: In member function 'void Segment_Tree_Beats::down(int, int, int)':
foodcourt.cpp:74:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |         int mid = l + r >> 1;
      |                   ~~^~~
foodcourt.cpp: In member function 'void Segment_Tree_Beats::update1(int, int, int, int, int, long long int)':
foodcourt.cpp:99:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |         int mid = l + r >> 1;
      |                   ~~^~~
foodcourt.cpp: In member function 'void Segment_Tree_Beats::update2(int, int, int, int, int, long long int)':
foodcourt.cpp:114:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |         int mid = l + r >> 1;
      |                   ~~^~~
foodcourt.cpp: In member function 'long long int Segment_Tree_Beats::get(int, int, int, int, int)':
foodcourt.cpp:125:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  125 |         int mid = l + r >> 1;
      |                   ~~^~~
foodcourt.cpp: In function 'void solution()':
foodcourt.cpp:198:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  198 |                     int mid = lf + rt >> 1;
      |                               ~~~^~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 109148 KB Output is correct
2 Correct 20 ms 109180 KB Output is correct
3 Correct 20 ms 109148 KB Output is correct
4 Correct 20 ms 109144 KB Output is correct
5 Correct 18 ms 109100 KB Output is correct
6 Correct 18 ms 109400 KB Output is correct
7 Correct 20 ms 109148 KB Output is correct
8 Correct 21 ms 109140 KB Output is correct
9 Correct 20 ms 109148 KB Output is correct
10 Correct 22 ms 109168 KB Output is correct
11 Correct 19 ms 109136 KB Output is correct
12 Correct 20 ms 109148 KB Output is correct
13 Correct 21 ms 109148 KB Output is correct
14 Correct 19 ms 109104 KB Output is correct
15 Correct 19 ms 109188 KB Output is correct
16 Correct 19 ms 109280 KB Output is correct
17 Correct 20 ms 109144 KB Output is correct
18 Correct 21 ms 109172 KB Output is correct
19 Correct 22 ms 109144 KB Output is correct
20 Correct 22 ms 109148 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 109148 KB Output is correct
2 Correct 20 ms 109180 KB Output is correct
3 Correct 20 ms 109148 KB Output is correct
4 Correct 20 ms 109144 KB Output is correct
5 Correct 18 ms 109100 KB Output is correct
6 Correct 18 ms 109400 KB Output is correct
7 Correct 20 ms 109148 KB Output is correct
8 Correct 21 ms 109140 KB Output is correct
9 Correct 20 ms 109148 KB Output is correct
10 Correct 22 ms 109168 KB Output is correct
11 Correct 19 ms 109136 KB Output is correct
12 Correct 20 ms 109148 KB Output is correct
13 Correct 21 ms 109148 KB Output is correct
14 Correct 19 ms 109104 KB Output is correct
15 Correct 19 ms 109188 KB Output is correct
16 Correct 19 ms 109280 KB Output is correct
17 Correct 20 ms 109144 KB Output is correct
18 Correct 21 ms 109172 KB Output is correct
19 Correct 22 ms 109144 KB Output is correct
20 Correct 22 ms 109148 KB Output is correct
21 Correct 21 ms 109148 KB Output is correct
22 Correct 20 ms 109148 KB Output is correct
23 Correct 19 ms 109400 KB Output is correct
24 Correct 21 ms 109148 KB Output is correct
25 Correct 18 ms 109148 KB Output is correct
26 Correct 20 ms 109296 KB Output is correct
27 Correct 20 ms 109148 KB Output is correct
28 Correct 20 ms 109144 KB Output is correct
29 Correct 21 ms 109144 KB Output is correct
30 Correct 21 ms 109148 KB Output is correct
31 Correct 20 ms 109148 KB Output is correct
32 Correct 20 ms 109144 KB Output is correct
33 Correct 21 ms 109148 KB Output is correct
34 Correct 19 ms 109148 KB Output is correct
35 Correct 22 ms 109148 KB Output is correct
36 Correct 19 ms 109148 KB Output is correct
37 Correct 20 ms 109152 KB Output is correct
38 Correct 20 ms 109144 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 113240 KB Output is correct
2 Correct 124 ms 113636 KB Output is correct
3 Correct 124 ms 111696 KB Output is correct
4 Correct 123 ms 113204 KB Output is correct
5 Correct 135 ms 113612 KB Output is correct
6 Correct 130 ms 113692 KB Output is correct
7 Correct 36 ms 112740 KB Output is correct
8 Correct 36 ms 112584 KB Output is correct
9 Correct 117 ms 113236 KB Output is correct
10 Correct 121 ms 113232 KB Output is correct
11 Correct 116 ms 113232 KB Output is correct
12 Correct 123 ms 113308 KB Output is correct
13 Correct 106 ms 113744 KB Output is correct
14 Correct 125 ms 113868 KB Output is correct
15 Correct 127 ms 114432 KB Output is correct
16 Correct 128 ms 114516 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 124376 KB Output is correct
2 Correct 449 ms 121592 KB Output is correct
3 Correct 579 ms 125524 KB Output is correct
4 Correct 421 ms 122452 KB Output is correct
5 Correct 475 ms 122768 KB Output is correct
6 Correct 611 ms 126800 KB Output is correct
7 Correct 103 ms 121756 KB Output is correct
8 Correct 114 ms 120844 KB Output is correct
9 Correct 613 ms 128852 KB Output is correct
10 Correct 777 ms 128816 KB Output is correct
11 Correct 539 ms 125180 KB Output is correct
12 Correct 578 ms 125236 KB Output is correct
13 Correct 555 ms 125048 KB Output is correct
14 Correct 587 ms 125520 KB Output is correct
15 Correct 599 ms 125052 KB Output is correct
16 Correct 596 ms 125012 KB Output is correct
17 Correct 735 ms 125080 KB Output is correct
18 Correct 587 ms 125020 KB Output is correct
19 Correct 606 ms 125188 KB Output is correct
20 Correct 639 ms 125236 KB Output is correct
21 Correct 582 ms 125268 KB Output is correct
22 Correct 636 ms 125480 KB Output is correct
23 Correct 616 ms 125084 KB Output is correct
24 Correct 621 ms 125020 KB Output is correct
25 Correct 466 ms 124648 KB Output is correct
26 Correct 424 ms 124860 KB Output is correct
27 Correct 475 ms 127812 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 109148 KB Output is correct
2 Correct 20 ms 109180 KB Output is correct
3 Correct 20 ms 109148 KB Output is correct
4 Correct 20 ms 109144 KB Output is correct
5 Correct 18 ms 109100 KB Output is correct
6 Correct 18 ms 109400 KB Output is correct
7 Correct 20 ms 109148 KB Output is correct
8 Correct 21 ms 109140 KB Output is correct
9 Correct 20 ms 109148 KB Output is correct
10 Correct 22 ms 109168 KB Output is correct
11 Correct 19 ms 109136 KB Output is correct
12 Correct 20 ms 109148 KB Output is correct
13 Correct 21 ms 109148 KB Output is correct
14 Correct 19 ms 109104 KB Output is correct
15 Correct 19 ms 109188 KB Output is correct
16 Correct 19 ms 109280 KB Output is correct
17 Correct 20 ms 109144 KB Output is correct
18 Correct 21 ms 109172 KB Output is correct
19 Correct 22 ms 109144 KB Output is correct
20 Correct 22 ms 109148 KB Output is correct
21 Correct 121 ms 113240 KB Output is correct
22 Correct 124 ms 113636 KB Output is correct
23 Correct 124 ms 111696 KB Output is correct
24 Correct 123 ms 113204 KB Output is correct
25 Correct 135 ms 113612 KB Output is correct
26 Correct 130 ms 113692 KB Output is correct
27 Correct 36 ms 112740 KB Output is correct
28 Correct 36 ms 112584 KB Output is correct
29 Correct 117 ms 113236 KB Output is correct
30 Correct 121 ms 113232 KB Output is correct
31 Correct 116 ms 113232 KB Output is correct
32 Correct 123 ms 113308 KB Output is correct
33 Correct 106 ms 113744 KB Output is correct
34 Correct 125 ms 113868 KB Output is correct
35 Correct 127 ms 114432 KB Output is correct
36 Correct 128 ms 114516 KB Output is correct
37 Correct 124 ms 113236 KB Output is correct
38 Correct 101 ms 113232 KB Output is correct
39 Correct 33 ms 112508 KB Output is correct
40 Correct 36 ms 112708 KB Output is correct
41 Correct 129 ms 113492 KB Output is correct
42 Correct 120 ms 113232 KB Output is correct
43 Correct 126 ms 113160 KB Output is correct
44 Correct 120 ms 113236 KB Output is correct
45 Correct 114 ms 113348 KB Output is correct
46 Correct 132 ms 113180 KB Output is correct
47 Correct 55 ms 112796 KB Output is correct
48 Correct 99 ms 113560 KB Output is correct
49 Correct 99 ms 112724 KB Output is correct
50 Correct 133 ms 113060 KB Output is correct
51 Correct 142 ms 113232 KB Output is correct
52 Correct 176 ms 113128 KB Output is correct
53 Correct 107 ms 113868 KB Output is correct
54 Correct 130 ms 114516 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 112192 KB Output is correct
2 Correct 145 ms 114376 KB Output is correct
3 Correct 131 ms 112764 KB Output is correct
4 Correct 100 ms 113476 KB Output is correct
5 Correct 116 ms 114000 KB Output is correct
6 Correct 148 ms 114272 KB Output is correct
7 Correct 41 ms 113472 KB Output is correct
8 Correct 40 ms 113160 KB Output is correct
9 Correct 102 ms 113700 KB Output is correct
10 Correct 81 ms 113432 KB Output is correct
11 Correct 108 ms 114004 KB Output is correct
12 Correct 111 ms 113956 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 109148 KB Output is correct
2 Correct 20 ms 109180 KB Output is correct
3 Correct 20 ms 109148 KB Output is correct
4 Correct 20 ms 109144 KB Output is correct
5 Correct 18 ms 109100 KB Output is correct
6 Correct 18 ms 109400 KB Output is correct
7 Correct 20 ms 109148 KB Output is correct
8 Correct 21 ms 109140 KB Output is correct
9 Correct 20 ms 109148 KB Output is correct
10 Correct 22 ms 109168 KB Output is correct
11 Correct 19 ms 109136 KB Output is correct
12 Correct 20 ms 109148 KB Output is correct
13 Correct 21 ms 109148 KB Output is correct
14 Correct 19 ms 109104 KB Output is correct
15 Correct 19 ms 109188 KB Output is correct
16 Correct 19 ms 109280 KB Output is correct
17 Correct 20 ms 109144 KB Output is correct
18 Correct 21 ms 109172 KB Output is correct
19 Correct 22 ms 109144 KB Output is correct
20 Correct 22 ms 109148 KB Output is correct
21 Correct 21 ms 109148 KB Output is correct
22 Correct 20 ms 109148 KB Output is correct
23 Correct 19 ms 109400 KB Output is correct
24 Correct 21 ms 109148 KB Output is correct
25 Correct 18 ms 109148 KB Output is correct
26 Correct 20 ms 109296 KB Output is correct
27 Correct 20 ms 109148 KB Output is correct
28 Correct 20 ms 109144 KB Output is correct
29 Correct 21 ms 109144 KB Output is correct
30 Correct 21 ms 109148 KB Output is correct
31 Correct 20 ms 109148 KB Output is correct
32 Correct 20 ms 109144 KB Output is correct
33 Correct 21 ms 109148 KB Output is correct
34 Correct 19 ms 109148 KB Output is correct
35 Correct 22 ms 109148 KB Output is correct
36 Correct 19 ms 109148 KB Output is correct
37 Correct 20 ms 109152 KB Output is correct
38 Correct 20 ms 109144 KB Output is correct
39 Correct 121 ms 113240 KB Output is correct
40 Correct 124 ms 113636 KB Output is correct
41 Correct 124 ms 111696 KB Output is correct
42 Correct 123 ms 113204 KB Output is correct
43 Correct 135 ms 113612 KB Output is correct
44 Correct 130 ms 113692 KB Output is correct
45 Correct 36 ms 112740 KB Output is correct
46 Correct 36 ms 112584 KB Output is correct
47 Correct 117 ms 113236 KB Output is correct
48 Correct 121 ms 113232 KB Output is correct
49 Correct 116 ms 113232 KB Output is correct
50 Correct 123 ms 113308 KB Output is correct
51 Correct 106 ms 113744 KB Output is correct
52 Correct 125 ms 113868 KB Output is correct
53 Correct 127 ms 114432 KB Output is correct
54 Correct 128 ms 114516 KB Output is correct
55 Correct 124 ms 113236 KB Output is correct
56 Correct 101 ms 113232 KB Output is correct
57 Correct 33 ms 112508 KB Output is correct
58 Correct 36 ms 112708 KB Output is correct
59 Correct 129 ms 113492 KB Output is correct
60 Correct 120 ms 113232 KB Output is correct
61 Correct 126 ms 113160 KB Output is correct
62 Correct 120 ms 113236 KB Output is correct
63 Correct 114 ms 113348 KB Output is correct
64 Correct 132 ms 113180 KB Output is correct
65 Correct 55 ms 112796 KB Output is correct
66 Correct 99 ms 113560 KB Output is correct
67 Correct 99 ms 112724 KB Output is correct
68 Correct 133 ms 113060 KB Output is correct
69 Correct 142 ms 113232 KB Output is correct
70 Correct 176 ms 113128 KB Output is correct
71 Correct 107 ms 113868 KB Output is correct
72 Correct 130 ms 114516 KB Output is correct
73 Correct 125 ms 112192 KB Output is correct
74 Correct 145 ms 114376 KB Output is correct
75 Correct 131 ms 112764 KB Output is correct
76 Correct 100 ms 113476 KB Output is correct
77 Correct 116 ms 114000 KB Output is correct
78 Correct 148 ms 114272 KB Output is correct
79 Correct 41 ms 113472 KB Output is correct
80 Correct 40 ms 113160 KB Output is correct
81 Correct 102 ms 113700 KB Output is correct
82 Correct 81 ms 113432 KB Output is correct
83 Correct 108 ms 114004 KB Output is correct
84 Correct 111 ms 113956 KB Output is correct
85 Correct 135 ms 113244 KB Output is correct
86 Correct 120 ms 113488 KB Output is correct
87 Correct 126 ms 113392 KB Output is correct
88 Correct 133 ms 113728 KB Output is correct
89 Correct 93 ms 112720 KB Output is correct
90 Correct 148 ms 113324 KB Output is correct
91 Correct 107 ms 113000 KB Output is correct
92 Correct 105 ms 112724 KB Output is correct
93 Correct 128 ms 113400 KB Output is correct
94 Correct 156 ms 113328 KB Output is correct
95 Correct 125 ms 113232 KB Output is correct
96 Correct 124 ms 113360 KB Output is correct
97 Correct 178 ms 113152 KB Output is correct
98 Correct 105 ms 113096 KB Output is correct
99 Correct 69 ms 113084 KB Output is correct
100 Correct 89 ms 112980 KB Output is correct
101 Correct 102 ms 113320 KB Output is correct
102 Correct 111 ms 114100 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 109148 KB Output is correct
2 Correct 20 ms 109180 KB Output is correct
3 Correct 20 ms 109148 KB Output is correct
4 Correct 20 ms 109144 KB Output is correct
5 Correct 18 ms 109100 KB Output is correct
6 Correct 18 ms 109400 KB Output is correct
7 Correct 20 ms 109148 KB Output is correct
8 Correct 21 ms 109140 KB Output is correct
9 Correct 20 ms 109148 KB Output is correct
10 Correct 22 ms 109168 KB Output is correct
11 Correct 19 ms 109136 KB Output is correct
12 Correct 20 ms 109148 KB Output is correct
13 Correct 21 ms 109148 KB Output is correct
14 Correct 19 ms 109104 KB Output is correct
15 Correct 19 ms 109188 KB Output is correct
16 Correct 19 ms 109280 KB Output is correct
17 Correct 20 ms 109144 KB Output is correct
18 Correct 21 ms 109172 KB Output is correct
19 Correct 22 ms 109144 KB Output is correct
20 Correct 22 ms 109148 KB Output is correct
21 Correct 21 ms 109148 KB Output is correct
22 Correct 20 ms 109148 KB Output is correct
23 Correct 19 ms 109400 KB Output is correct
24 Correct 21 ms 109148 KB Output is correct
25 Correct 18 ms 109148 KB Output is correct
26 Correct 20 ms 109296 KB Output is correct
27 Correct 20 ms 109148 KB Output is correct
28 Correct 20 ms 109144 KB Output is correct
29 Correct 21 ms 109144 KB Output is correct
30 Correct 21 ms 109148 KB Output is correct
31 Correct 20 ms 109148 KB Output is correct
32 Correct 20 ms 109144 KB Output is correct
33 Correct 21 ms 109148 KB Output is correct
34 Correct 19 ms 109148 KB Output is correct
35 Correct 22 ms 109148 KB Output is correct
36 Correct 19 ms 109148 KB Output is correct
37 Correct 20 ms 109152 KB Output is correct
38 Correct 20 ms 109144 KB Output is correct
39 Correct 121 ms 113240 KB Output is correct
40 Correct 124 ms 113636 KB Output is correct
41 Correct 124 ms 111696 KB Output is correct
42 Correct 123 ms 113204 KB Output is correct
43 Correct 135 ms 113612 KB Output is correct
44 Correct 130 ms 113692 KB Output is correct
45 Correct 36 ms 112740 KB Output is correct
46 Correct 36 ms 112584 KB Output is correct
47 Correct 117 ms 113236 KB Output is correct
48 Correct 121 ms 113232 KB Output is correct
49 Correct 116 ms 113232 KB Output is correct
50 Correct 123 ms 113308 KB Output is correct
51 Correct 106 ms 113744 KB Output is correct
52 Correct 125 ms 113868 KB Output is correct
53 Correct 127 ms 114432 KB Output is correct
54 Correct 128 ms 114516 KB Output is correct
55 Correct 555 ms 124376 KB Output is correct
56 Correct 449 ms 121592 KB Output is correct
57 Correct 579 ms 125524 KB Output is correct
58 Correct 421 ms 122452 KB Output is correct
59 Correct 475 ms 122768 KB Output is correct
60 Correct 611 ms 126800 KB Output is correct
61 Correct 103 ms 121756 KB Output is correct
62 Correct 114 ms 120844 KB Output is correct
63 Correct 613 ms 128852 KB Output is correct
64 Correct 777 ms 128816 KB Output is correct
65 Correct 539 ms 125180 KB Output is correct
66 Correct 578 ms 125236 KB Output is correct
67 Correct 555 ms 125048 KB Output is correct
68 Correct 587 ms 125520 KB Output is correct
69 Correct 599 ms 125052 KB Output is correct
70 Correct 596 ms 125012 KB Output is correct
71 Correct 735 ms 125080 KB Output is correct
72 Correct 587 ms 125020 KB Output is correct
73 Correct 606 ms 125188 KB Output is correct
74 Correct 639 ms 125236 KB Output is correct
75 Correct 582 ms 125268 KB Output is correct
76 Correct 636 ms 125480 KB Output is correct
77 Correct 616 ms 125084 KB Output is correct
78 Correct 621 ms 125020 KB Output is correct
79 Correct 466 ms 124648 KB Output is correct
80 Correct 424 ms 124860 KB Output is correct
81 Correct 475 ms 127812 KB Output is correct
82 Correct 124 ms 113236 KB Output is correct
83 Correct 101 ms 113232 KB Output is correct
84 Correct 33 ms 112508 KB Output is correct
85 Correct 36 ms 112708 KB Output is correct
86 Correct 129 ms 113492 KB Output is correct
87 Correct 120 ms 113232 KB Output is correct
88 Correct 126 ms 113160 KB Output is correct
89 Correct 120 ms 113236 KB Output is correct
90 Correct 114 ms 113348 KB Output is correct
91 Correct 132 ms 113180 KB Output is correct
92 Correct 55 ms 112796 KB Output is correct
93 Correct 99 ms 113560 KB Output is correct
94 Correct 99 ms 112724 KB Output is correct
95 Correct 133 ms 113060 KB Output is correct
96 Correct 142 ms 113232 KB Output is correct
97 Correct 176 ms 113128 KB Output is correct
98 Correct 107 ms 113868 KB Output is correct
99 Correct 130 ms 114516 KB Output is correct
100 Correct 125 ms 112192 KB Output is correct
101 Correct 145 ms 114376 KB Output is correct
102 Correct 131 ms 112764 KB Output is correct
103 Correct 100 ms 113476 KB Output is correct
104 Correct 116 ms 114000 KB Output is correct
105 Correct 148 ms 114272 KB Output is correct
106 Correct 41 ms 113472 KB Output is correct
107 Correct 40 ms 113160 KB Output is correct
108 Correct 102 ms 113700 KB Output is correct
109 Correct 81 ms 113432 KB Output is correct
110 Correct 108 ms 114004 KB Output is correct
111 Correct 111 ms 113956 KB Output is correct
112 Correct 135 ms 113244 KB Output is correct
113 Correct 120 ms 113488 KB Output is correct
114 Correct 126 ms 113392 KB Output is correct
115 Correct 133 ms 113728 KB Output is correct
116 Correct 93 ms 112720 KB Output is correct
117 Correct 148 ms 113324 KB Output is correct
118 Correct 107 ms 113000 KB Output is correct
119 Correct 105 ms 112724 KB Output is correct
120 Correct 128 ms 113400 KB Output is correct
121 Correct 156 ms 113328 KB Output is correct
122 Correct 125 ms 113232 KB Output is correct
123 Correct 124 ms 113360 KB Output is correct
124 Correct 178 ms 113152 KB Output is correct
125 Correct 105 ms 113096 KB Output is correct
126 Correct 69 ms 113084 KB Output is correct
127 Correct 89 ms 112980 KB Output is correct
128 Correct 102 ms 113320 KB Output is correct
129 Correct 111 ms 114100 KB Output is correct
130 Correct 592 ms 126032 KB Output is correct
131 Correct 431 ms 121768 KB Output is correct
132 Correct 647 ms 126028 KB Output is correct
133 Correct 575 ms 126748 KB Output is correct
134 Correct 500 ms 125196 KB Output is correct
135 Correct 674 ms 127592 KB Output is correct
136 Correct 695 ms 129816 KB Output is correct
137 Correct 738 ms 129812 KB Output is correct
138 Correct 595 ms 125380 KB Output is correct
139 Correct 635 ms 125824 KB Output is correct
140 Correct 652 ms 125612 KB Output is correct
141 Correct 626 ms 125812 KB Output is correct
142 Correct 615 ms 125688 KB Output is correct
143 Correct 675 ms 125796 KB Output is correct
144 Correct 607 ms 125636 KB Output is correct
145 Correct 659 ms 125924 KB Output is correct
146 Correct 660 ms 125820 KB Output is correct
147 Correct 651 ms 125688 KB Output is correct
148 Correct 651 ms 125820 KB Output is correct
149 Correct 612 ms 125856 KB Output is correct
150 Correct 231 ms 123300 KB Output is correct
151 Correct 442 ms 125360 KB Output is correct
152 Correct 439 ms 125480 KB Output is correct
153 Correct 492 ms 128592 KB Output is correct