oj.uz

Submission #503158

# Submission time Handle Problem Language Result Execution time Memory
503158 2022-01-07T11:52:54 Z cig32 Food Court (JOI21_foodcourt) C++17
68 / 100
 1000 ms 210088 KB 
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
#define int long long
 
const int MAXN = 2.5e5 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
    int u = uniform_int_distribution<int>(x, y)(rng);
    return u;
}
int bm(int b, int p) { // bigmod
    if(p==0) return 1;
    int r = bm(b, p/2);
    if(p&1) return (((r*r) % MOD) * b) % MOD;
    return (r*r) % MOD;
}
int N, M, Q;
 
struct segtree_beats {
    bool cmp(__int128 x, __int128 y) { return x > y; }
    int stok;
    const __int128 extr = 2e18;
    struct node {
        __int128 max1, max2, maxc;
        __int128 min1, min2, minc;
        __int128 lazy, sum;
        __int128 l, r;
    };
    vector<node> a;
    void pushtag_max(int idx, __int128 val) {
        if(val >= a[idx].max1) return;
        a[idx].sum -= (a[idx].max1 - val) * a[idx].maxc;
        a[idx].max1 = val;
        if(a[idx].l == a[idx].r) {
            a[idx].min1 = val;
        }
        else {
            if(a[idx].min1 >= val) {
                a[idx].min1 = val;
                a[idx].min2 = extr;
                a[idx].minc = a[idx].r - a[idx].l + 1;
            }
            else if(a[idx].min2 > val && a[idx].min2 != extr) {
                a[idx].min2 = val;
            }
        }
    }
    void pushtag_min(int idx, __int128 val) {
        if(val <= a[idx].min1) return;
        a[idx].sum += (val - a[idx].min1) * a[idx].minc;
        a[idx].min1 = val;
        if(a[idx].l == a[idx].r) {
            a[idx].max1 = val;
        }
        else {
            if(a[idx].max1 <= val) {
                a[idx].max1 = val;
                a[idx].max2 = -extr;
                a[idx].maxc = a[idx].r - a[idx].l + 1;
            }
            else if(a[idx].max2 < val && a[idx].max2 != -extr) {
                a[idx].max2 = val;
            }
        }
    }
    void pushtag_add(int idx, __int128 val) {
        a[idx].max1 += val;
        if(a[idx].max2 != -extr) a[idx].max2 += val;
        a[idx].min1 += val;
        if(a[idx].min2 != extr) a[idx].min2 += val;
        a[idx].lazy += val;
        a[idx].sum += val * (a[idx].r - a[idx].l + 1);
    }
    void pushdown(int idx) {
        pushtag_add(2*idx+1, a[idx].lazy);
        pushtag_add(2*idx+2, a[idx].lazy);
        a[idx].lazy = 0;
        pushtag_max(2*idx+1, a[idx].max1);
        pushtag_max(2*idx+2, a[idx].max1);
        pushtag_min(2*idx+1, a[idx].min1);
        pushtag_min(2*idx+2, a[idx].min1);
    }
    void pushup(int idx) {
        __int128 max1, max2, maxc;
        __int128 min1, min2, minc;
        __int128 lazy, sum;
        __int128 l, r;
        a[idx].max1 = max(a[2*idx+1].max1, a[2*idx+2].max1);
        a[idx].max2 = (a[2*idx+1].max1 == a[2*idx+2].max1 ?
                       max(a[2*idx+1].max2, a[2*idx+2].max2) :
                       (a[2*idx+1].max1 < a[2*idx+2].max1 ?
                        max(a[2*idx+1].max1, a[2*idx+2].max2) : 
                        max(a[2*idx+1].max2, a[2*idx+2].max1)
                        ));
        a[idx].maxc = (a[2*idx+1].max1 == a[2*idx+2].max1 ? 
                       a[2*idx+1].maxc + a[2*idx+2].maxc :
                       (a[2*idx+1].max1 < a[2*idx+2].max1 ? 
                        a[2*idx+2].maxc :
                        a[2*idx+1].maxc)
                       );
        a[idx].min1 = min(a[2*idx+1].min1, a[2*idx+2].min1);
        a[idx].min2 = (a[2*idx+1].min1 == a[2*idx+2].min1 ?
                       min(a[2*idx+1].min2, a[2*idx+2].min2) :
                       (a[2*idx+1].min1 > a[2*idx+2].min1 ?
                        min(a[2*idx+1].min1, a[2*idx+2].min2) : 
                        min(a[2*idx+1].min2, a[2*idx+2].min1)
                        ));
        a[idx].minc = (a[2*idx+1].min1 == a[2*idx+2].min1 ? 
                       a[2*idx+1].minc + a[2*idx+2].minc :
                       (a[2*idx+1].min1 > a[2*idx+2].min1 ? 
                        a[2*idx+2].minc :
                        a[2*idx+1].minc)
                       );
        a[idx].sum = a[2*idx+1].sum + a[2*idx+2].sum;
    }
    void init1(int l, int r, int idx, __int128 val) {
        a[idx].l = l, a[idx].r = r;
        if(l == r) {
            a[idx].max1 = a[idx].min1 = val;
            a[idx].max2 = -extr;
            a[idx].min2 = extr;
            a[idx].maxc = a[idx].minc = 1;
            a[idx].lazy = 0;
            a[idx].sum = val;
            return;
        }
        int mid = (l+r) >> 1;
        init1(l, mid, 2*idx+1, val);
        init1(mid+1, r, 2*idx+2, val);
        pushup(idx);
    }
    void u1(int l, int r, int constl, int constr, int idx, __int128 v) {
        if(v >= a[idx].max1) return;
        if(l<=constl && constr<=r && v>a[idx].max2) {
            pushtag_max(idx, v);
            return;
        }
        pushdown(idx);
        int mid = (constl+constr) >> 1;
        if(mid < l || r < constl) u1(l, r, mid+1, constr, 2*idx+2, v);
        else if(constr < l || r < mid+1) u1(l, r, constl, mid, 2*idx+1, v);
        else {
            u1(l, r, constl, mid, 2*idx+1, v);
            u1(l, r, mid+1, constr, 2*idx+2, v);
        }
        pushup(idx);
    }
    void u2(int l, int r, int constl, int constr, int idx, __int128 v) {
        if(v <= a[idx].min1) return;
        if(l<=constl && constr<=r && v<a[idx].min2) {
            pushtag_min(idx, v);
            return;
        }
        pushdown(idx);
        int mid = (constl+constr) >> 1;
        if(mid < l || r < constl) u2(l, r, mid+1, constr, 2*idx+2, v);
        else if(constr < l || r < mid+1) u2(l, r, constl, mid, 2*idx+1, v);
        else {
            u2(l, r, constl, mid, 2*idx+1, v);
            u2(l, r, mid+1, constr, 2*idx+2, v);
        }
        pushup(idx);
    }
    void u3(int l, int r, int constl, int constr, int idx, __int128 v) {
        if(l <= constl && constr <= r) {
            pushtag_add(idx, v);
            return;
        }
        pushdown(idx);
        int mid = (constl+constr) >> 1;
        if(mid < l || r < constl) u3(l, r, mid+1, constr, 2*idx+2, v);
        else if(constr < l || r < mid+1) u3(l, r, constl, mid, 2*idx+1, v);
        else {
            u3(l, r, constl, mid, 2*idx+1, v);
            u3(l, r, mid+1, constr, 2*idx+2, v);
        }
        pushup(idx);
    }
    __int128 qu(int l, int r, int constl, int constr, int idx) {
        if(l <= constl && constr <= r) {
            return a[idx].sum;
        }
        pushdown(idx);
        int mid = (constl+constr) >> 1;
        if(mid < l || r < constl) return qu(l, r, mid+1, constr, 2*idx+2);
        else if(constr < l || r < mid+1) return qu(l, r, constl, mid, 2*idx+1);
        else {
            return qu(l, r, constl, mid, 2*idx+1) + qu(l, r, mid+1, constr, 2*idx+2);
        }
    }
    public:
    void resize(int k) {
        stok = k;
        a.resize(4*k + 10);
    }
    void init(__int128 v) { // Initialize everything to v
        init1(0, stok, 0, v);
    }
    void min_with(int l, int r, __int128 v) {
        u1(l, r, 0, stok, 0, v);
    }
    void max_with(int l, int r, __int128 v) {
        u2(l, r, 0, stok, 0, v);
    }
    void range_add(int l, int r, __int128 v) {
        u3(l, r, 0, stok, 0, v);
    }
    long long query_sum(int l, int r) {
        return (long long)qu(l, r, 0, stok, 0);
    }
};
struct _1m {
    segtree_beats a;
    public:
    void join(int l, int r, int c, int k) {
        a.range_add(l, r, k);
    }
    void leave(int l, int r, int k) {
        a.range_add(l, r, -k);
        a.max_with(l, r, 0);
    }
    int service(int shop, int b) {
        return (a.query_sum(shop, shop) >= b ? 1 : 0);
    }
};

void solve_1m() {
    _1m ar;
    ar.a.resize(N);
    ar.a.init(0);
    while(Q--) {
        int t;
        cin >> t;
        if(t == 1) {
            int l, r, c, k;
            cin >> l >> r >> c >> k;
            ar.join(l, r, c, k);
        }
        else if(t == 2) {
            int l, r, k;
            cin >> l >> r >> k;
            ar.leave(l, r, k);
        }
        else {
            int a, b;
            cin >> a >> b;
            cout << ar.service(a, b) << "\n";
        }
    }
}
segtree_beats stb;
vector<pair<int, pair<int, int> > > v[4*MAXN];
vector<int> w[4*MAXN];
int p[4*MAXN];
int ti=0;
int rp[MAXN];
void update(int l, int r, int constl, int constr, int idx, int c, int k) {
    if(l<=constl && constr<=r) {
        v[idx].push_back({ti, {c, k}});
        w[idx].push_back(w[idx].empty() ? k : w[idx][w[idx].size() - 1] + k);
        return;
    }
    int mid = (constl+constr) >> 1;
    if(mid < l || r < constl) update(l, r, mid+1, constr, 2*idx+2, c, k);
    else if(constr < l || r < mid+1) update(l, r, constl, mid, 2*idx+1, c, k);
    else {
        update(l, r, constl, mid, 2*idx+1, c, k);
        update(l, r, mid+1, constr, 2*idx+2, c, k);
    }
} 
void build(int l, int r, int idx) {
    if(l == r) {
        rp[l] = idx;
        return;
    }
    int mid = (l+r) >> 1;
    build(l, mid, 2*idx+1);
    build(mid+1, r, 2*idx+2);
    p[2*idx+1] = p[2*idx+2] = idx;
}
void join(int l, int r, int c, int k) {
    ti++;
    stb.range_add(l, r, k);
    update(l, r, 0, MAXN-1, 0, c, k);
}
void leave(int l, int r, int k) {
    stb.range_add(l, r, -k);
    stb.max_with(l, r, 0);
}
int service(int a, int b) { // log^3 n
    int cur = rp[a];
    vector<int> q;
    int sum = 0;
    while(1) {
        q.push_back(cur);
        if(w[cur].size()) sum += w[cur][w[cur].size() - 1];
        if(cur == 0) break;
        cur = p[cur];
    }
    b += sum - stb.query_sum(a, a);
    if(b > sum) return 0;
    int lb = 0, rb = ti;
    while(lb < rb) { // log n
        int mid = (lb+rb) >> 1;
        int tot = 0;
        for(int x: q) { // log n 
            if(w[x].empty()) continue;
            int lb2 = 0, rb2 = w[x].size() - 1;
            while(lb2 < rb2) { // log n
                int mid2 = (lb2 + rb2 + 1) >> 1;
                if(v[x][mid2].first <= mid) {
                    lb2 = mid2;
                }
                else {
                    rb2 = mid2 - 1;
                }
            }
            if(v[x][lb2].first <= mid) {
                tot += w[x][lb2];
            }
        }
        if(tot >= b) rb = mid;
        else lb = mid + 1;
    }
    for(int x: q) {
        if(w[x].empty()) continue;
        int lb2 = 0, rb2 = w[x].size() - 1;
        while(lb2 < rb2) { // log n
            int mid2 = (lb2 + rb2 + 1) >> 1;
            if(v[x][mid2].first <= lb) {
                lb2 = mid2;
            }
            else {
                rb2 = mid2 - 1;
            }
        }
        if(v[x][lb2].first == lb) {
            return v[x][lb2].second.first;
        }
    }
}

void solve(int tc) {
    cin >> N >> M >> Q;
    if(M == 1) { // Subtask 4
        solve_1m();
        return;
    }
    stb.resize(N);
    stb.init(0);
    build(0, MAXN-1, 0);
    while(Q--) {
        int t;
        cin >> t;
        if(t == 1) {
            int l, r, c, k;
            cin >> l >> r >> c >> k;
            join(l, r, c, k);
        }
        else if(t == 2) {
            int l, r, k;
            cin >> l >> r >> k;
            leave(l, r, k);
        }
        else {
            int a, b;
            cin >> a >> b;
            cout << service(a, b) << "\n";
        }
    }
}
int32_t main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1; //cin >> t;
    for(int i=1; i<=t; i++) {
        solve(i);
    }
}

Compilation message

foodcourt.cpp: In member function 'void segtree_beats::pushup(long long int)':
foodcourt.cpp:86:18: warning: unused variable 'max1' [-Wunused-variable]
   86 |         __int128 max1, max2, maxc;
      |                  ^~~~
foodcourt.cpp:86:24: warning: unused variable 'max2' [-Wunused-variable]
   86 |         __int128 max1, max2, maxc;
      |                        ^~~~
foodcourt.cpp:86:30: warning: unused variable 'maxc' [-Wunused-variable]
   86 |         __int128 max1, max2, maxc;
      |                              ^~~~
foodcourt.cpp:87:18: warning: unused variable 'min1' [-Wunused-variable]
   87 |         __int128 min1, min2, minc;
      |                  ^~~~
foodcourt.cpp:87:24: warning: unused variable 'min2' [-Wunused-variable]
   87 |         __int128 min1, min2, minc;
      |                        ^~~~
foodcourt.cpp:87:30: warning: unused variable 'minc' [-Wunused-variable]
   87 |         __int128 min1, min2, minc;
      |                              ^~~~
foodcourt.cpp:88:18: warning: unused variable 'lazy' [-Wunused-variable]
   88 |         __int128 lazy, sum;
      |                  ^~~~
foodcourt.cpp:88:24: warning: unused variable 'sum' [-Wunused-variable]
   88 |         __int128 lazy, sum;
      |                        ^~~
foodcourt.cpp:89:18: warning: unused variable 'l' [-Wunused-variable]
   89 |         __int128 l, r;
      |                  ^
foodcourt.cpp:89:21: warning: unused variable 'r' [-Wunused-variable]
   89 |         __int128 l, r;
      |                     ^
foodcourt.cpp: In function 'long long int service(long long int, long long int)':
foodcourt.cpp:294:17: warning: control reaches end of non-void function [-Wreturn-type]
  294 |     vector<int> q;
      |                 ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 54460 KB Output is correct
2 Correct 36 ms 54900 KB Output is correct
3 Correct 33 ms 54816 KB Output is correct
4 Correct 35 ms 54980 KB Output is correct
5 Correct 31 ms 53316 KB Output is correct
6 Correct 33 ms 53432 KB Output is correct
7 Correct 41 ms 54980 KB Output is correct
8 Correct 35 ms 54984 KB Output is correct
9 Correct 34 ms 54968 KB Output is correct
10 Correct 34 ms 54956 KB Output is correct
11 Correct 37 ms 55000 KB Output is correct
12 Correct 34 ms 54992 KB Output is correct
13 Correct 33 ms 54888 KB Output is correct
14 Correct 32 ms 54988 KB Output is correct
15 Correct 40 ms 54852 KB Output is correct
16 Correct 37 ms 54980 KB Output is correct
17 Correct 35 ms 54540 KB Output is correct
18 Correct 34 ms 54920 KB Output is correct
19 Correct 35 ms 54496 KB Output is correct
20 Correct 35 ms 54860 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 54460 KB Output is correct
2 Correct 36 ms 54900 KB Output is correct
3 Correct 33 ms 54816 KB Output is correct
4 Correct 35 ms 54980 KB Output is correct
5 Correct 31 ms 53316 KB Output is correct
6 Correct 33 ms 53432 KB Output is correct
7 Correct 41 ms 54980 KB Output is correct
8 Correct 35 ms 54984 KB Output is correct
9 Correct 34 ms 54968 KB Output is correct
10 Correct 34 ms 54956 KB Output is correct
11 Correct 37 ms 55000 KB Output is correct
12 Correct 34 ms 54992 KB Output is correct
13 Correct 33 ms 54888 KB Output is correct
14 Correct 32 ms 54988 KB Output is correct
15 Correct 40 ms 54852 KB Output is correct
16 Correct 37 ms 54980 KB Output is correct
17 Correct 35 ms 54540 KB Output is correct
18 Correct 34 ms 54920 KB Output is correct
19 Correct 35 ms 54496 KB Output is correct
20 Correct 35 ms 54860 KB Output is correct
21 Correct 34 ms 54840 KB Output is correct
22 Correct 34 ms 54936 KB Output is correct
23 Correct 35 ms 54652 KB Output is correct
24 Correct 39 ms 55108 KB Output is correct
25 Correct 34 ms 53432 KB Output is correct
26 Correct 37 ms 53432 KB Output is correct
27 Correct 36 ms 54924 KB Output is correct
28 Correct 34 ms 55016 KB Output is correct
29 Correct 34 ms 54976 KB Output is correct
30 Correct 34 ms 54988 KB Output is correct
31 Correct 37 ms 54980 KB Output is correct
32 Correct 35 ms 54996 KB Output is correct
33 Correct 34 ms 54836 KB Output is correct
34 Correct 34 ms 54980 KB Output is correct
35 Correct 44 ms 54656 KB Output is correct
36 Correct 36 ms 54988 KB Output is correct
37 Correct 33 ms 54488 KB Output is correct
38 Correct 34 ms 54756 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 98480 KB Output is correct
2 Correct 283 ms 99872 KB Output is correct
3 Correct 255 ms 99392 KB Output is correct
4 Correct 288 ms 99464 KB Output is correct
5 Correct 316 ms 101296 KB Output is correct
6 Correct 297 ms 101312 KB Output is correct
7 Correct 60 ms 55060 KB Output is correct
8 Correct 64 ms 55736 KB Output is correct
9 Correct 280 ms 98752 KB Output is correct
10 Correct 296 ms 98924 KB Output is correct
11 Correct 262 ms 98872 KB Output is correct
12 Correct 332 ms 98904 KB Output is correct
13 Correct 224 ms 86580 KB Output is correct
14 Correct 273 ms 100476 KB Output is correct
15 Correct 300 ms 89644 KB Output is correct
16 Correct 268 ms 102864 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 864 ms 193360 KB Output is correct
2 Correct 786 ms 173480 KB Output is correct
3 Correct 866 ms 209832 KB Output is correct
4 Correct 655 ms 207168 KB Output is correct
5 Correct 593 ms 169356 KB Output is correct
6 Correct 842 ms 210088 KB Output is correct
7 Correct 116 ms 51548 KB Output is correct
8 Correct 112 ms 51468 KB Output is correct
9 Correct 727 ms 210068 KB Output is correct
10 Correct 723 ms 210080 KB Output is correct
11 Correct 889 ms 210080 KB Output is correct
12 Correct 808 ms 210076 KB Output is correct
13 Correct 831 ms 209920 KB Output is correct
14 Correct 946 ms 209972 KB Output is correct
15 Correct 931 ms 210064 KB Output is correct
16 Correct 967 ms 210052 KB Output is correct
17 Execution timed out 1004 ms 209916 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 54460 KB Output is correct
2 Correct 36 ms 54900 KB Output is correct
3 Correct 33 ms 54816 KB Output is correct
4 Correct 35 ms 54980 KB Output is correct
5 Correct 31 ms 53316 KB Output is correct
6 Correct 33 ms 53432 KB Output is correct
7 Correct 41 ms 54980 KB Output is correct
8 Correct 35 ms 54984 KB Output is correct
9 Correct 34 ms 54968 KB Output is correct
10 Correct 34 ms 54956 KB Output is correct
11 Correct 37 ms 55000 KB Output is correct
12 Correct 34 ms 54992 KB Output is correct
13 Correct 33 ms 54888 KB Output is correct
14 Correct 32 ms 54988 KB Output is correct
15 Correct 40 ms 54852 KB Output is correct
16 Correct 37 ms 54980 KB Output is correct
17 Correct 35 ms 54540 KB Output is correct
18 Correct 34 ms 54920 KB Output is correct
19 Correct 35 ms 54496 KB Output is correct
20 Correct 35 ms 54860 KB Output is correct
21 Correct 248 ms 98480 KB Output is correct
22 Correct 283 ms 99872 KB Output is correct
23 Correct 255 ms 99392 KB Output is correct
24 Correct 288 ms 99464 KB Output is correct
25 Correct 316 ms 101296 KB Output is correct
26 Correct 297 ms 101312 KB Output is correct
27 Correct 60 ms 55060 KB Output is correct
28 Correct 64 ms 55736 KB Output is correct
29 Correct 280 ms 98752 KB Output is correct
30 Correct 296 ms 98924 KB Output is correct
31 Correct 262 ms 98872 KB Output is correct
32 Correct 332 ms 98904 KB Output is correct
33 Correct 224 ms 86580 KB Output is correct
34 Correct 273 ms 100476 KB Output is correct
35 Correct 300 ms 89644 KB Output is correct
36 Correct 268 ms 102864 KB Output is correct
37 Correct 376 ms 103456 KB Output is correct
38 Correct 347 ms 107764 KB Output is correct
39 Correct 58 ms 54916 KB Output is correct
40 Correct 67 ms 55616 KB Output is correct
41 Correct 409 ms 110948 KB Output is correct
42 Correct 432 ms 111196 KB Output is correct
43 Correct 442 ms 111060 KB Output is correct
44 Correct 423 ms 111124 KB Output is correct
45 Correct 403 ms 111080 KB Output is correct
46 Correct 462 ms 111140 KB Output is correct
47 Correct 186 ms 111596 KB Output is correct
48 Correct 264 ms 109276 KB Output is correct
49 Correct 286 ms 93764 KB Output is correct
50 Correct 404 ms 108424 KB Output is correct
51 Correct 412 ms 111744 KB Output is correct
52 Correct 468 ms 111668 KB Output is correct
53 Correct 217 ms 95808 KB Output is correct
54 Correct 288 ms 102988 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 112080 KB Output is correct
2 Correct 508 ms 108348 KB Output is correct
3 Correct 483 ms 115740 KB Output is correct
4 Correct 371 ms 108052 KB Output is correct
5 Correct 410 ms 112388 KB Output is correct
6 Correct 509 ms 116604 KB Output is correct
7 Correct 86 ms 55788 KB Output is correct
8 Correct 90 ms 56272 KB Output is correct
9 Correct 219 ms 118940 KB Output is correct
10 Correct 212 ms 107128 KB Output is correct
11 Correct 266 ms 116104 KB Output is correct
12 Correct 281 ms 116088 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 54460 KB Output is correct
2 Correct 36 ms 54900 KB Output is correct
3 Correct 33 ms 54816 KB Output is correct
4 Correct 35 ms 54980 KB Output is correct
5 Correct 31 ms 53316 KB Output is correct
6 Correct 33 ms 53432 KB Output is correct
7 Correct 41 ms 54980 KB Output is correct
8 Correct 35 ms 54984 KB Output is correct
9 Correct 34 ms 54968 KB Output is correct
10 Correct 34 ms 54956 KB Output is correct
11 Correct 37 ms 55000 KB Output is correct
12 Correct 34 ms 54992 KB Output is correct
13 Correct 33 ms 54888 KB Output is correct
14 Correct 32 ms 54988 KB Output is correct
15 Correct 40 ms 54852 KB Output is correct
16 Correct 37 ms 54980 KB Output is correct
17 Correct 35 ms 54540 KB Output is correct
18 Correct 34 ms 54920 KB Output is correct
19 Correct 35 ms 54496 KB Output is correct
20 Correct 35 ms 54860 KB Output is correct
21 Correct 34 ms 54840 KB Output is correct
22 Correct 34 ms 54936 KB Output is correct
23 Correct 35 ms 54652 KB Output is correct
24 Correct 39 ms 55108 KB Output is correct
25 Correct 34 ms 53432 KB Output is correct
26 Correct 37 ms 53432 KB Output is correct
27 Correct 36 ms 54924 KB Output is correct
28 Correct 34 ms 55016 KB Output is correct
29 Correct 34 ms 54976 KB Output is correct
30 Correct 34 ms 54988 KB Output is correct
31 Correct 37 ms 54980 KB Output is correct
32 Correct 35 ms 54996 KB Output is correct
33 Correct 34 ms 54836 KB Output is correct
34 Correct 34 ms 54980 KB Output is correct
35 Correct 44 ms 54656 KB Output is correct
36 Correct 36 ms 54988 KB Output is correct
37 Correct 33 ms 54488 KB Output is correct
38 Correct 34 ms 54756 KB Output is correct
39 Correct 248 ms 98480 KB Output is correct
40 Correct 283 ms 99872 KB Output is correct
41 Correct 255 ms 99392 KB Output is correct
42 Correct 288 ms 99464 KB Output is correct
43 Correct 316 ms 101296 KB Output is correct
44 Correct 297 ms 101312 KB Output is correct
45 Correct 60 ms 55060 KB Output is correct
46 Correct 64 ms 55736 KB Output is correct
47 Correct 280 ms 98752 KB Output is correct
48 Correct 296 ms 98924 KB Output is correct
49 Correct 262 ms 98872 KB Output is correct
50 Correct 332 ms 98904 KB Output is correct
51 Correct 224 ms 86580 KB Output is correct
52 Correct 273 ms 100476 KB Output is correct
53 Correct 300 ms 89644 KB Output is correct
54 Correct 268 ms 102864 KB Output is correct
55 Correct 376 ms 103456 KB Output is correct
56 Correct 347 ms 107764 KB Output is correct
57 Correct 58 ms 54916 KB Output is correct
58 Correct 67 ms 55616 KB Output is correct
59 Correct 409 ms 110948 KB Output is correct
60 Correct 432 ms 111196 KB Output is correct
61 Correct 442 ms 111060 KB Output is correct
62 Correct 423 ms 111124 KB Output is correct
63 Correct 403 ms 111080 KB Output is correct
64 Correct 462 ms 111140 KB Output is correct
65 Correct 186 ms 111596 KB Output is correct
66 Correct 264 ms 109276 KB Output is correct
67 Correct 286 ms 93764 KB Output is correct
68 Correct 404 ms 108424 KB Output is correct
69 Correct 412 ms 111744 KB Output is correct
70 Correct 468 ms 111668 KB Output is correct
71 Correct 217 ms 95808 KB Output is correct
72 Correct 288 ms 102988 KB Output is correct
73 Correct 458 ms 112080 KB Output is correct
74 Correct 508 ms 108348 KB Output is correct
75 Correct 483 ms 115740 KB Output is correct
76 Correct 371 ms 108052 KB Output is correct
77 Correct 410 ms 112388 KB Output is correct
78 Correct 509 ms 116604 KB Output is correct
79 Correct 86 ms 55788 KB Output is correct
80 Correct 90 ms 56272 KB Output is correct
81 Correct 219 ms 118940 KB Output is correct
82 Correct 212 ms 107128 KB Output is correct
83 Correct 266 ms 116104 KB Output is correct
84 Correct 281 ms 116088 KB Output is correct
85 Correct 356 ms 99060 KB Output is correct
86 Correct 387 ms 109496 KB Output is correct
87 Correct 343 ms 111412 KB Output is correct
88 Correct 406 ms 116636 KB Output is correct
89 Correct 284 ms 97144 KB Output is correct
90 Correct 386 ms 111648 KB Output is correct
91 Correct 328 ms 94532 KB Output is correct
92 Correct 292 ms 94204 KB Output is correct
93 Correct 371 ms 111516 KB Output is correct
94 Correct 413 ms 111744 KB Output is correct
95 Correct 350 ms 107336 KB Output is correct
96 Correct 426 ms 111832 KB Output is correct
97 Correct 423 ms 111684 KB Output is correct
98 Correct 319 ms 96784 KB Output is correct
99 Correct 212 ms 112224 KB Output is correct
100 Correct 251 ms 101424 KB Output is correct
101 Correct 245 ms 109792 KB Output is correct
102 Correct 307 ms 105892 KB Output is correct

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 54460 KB Output is correct
2 Correct 36 ms 54900 KB Output is correct
3 Correct 33 ms 54816 KB Output is correct
4 Correct 35 ms 54980 KB Output is correct
5 Correct 31 ms 53316 KB Output is correct
6 Correct 33 ms 53432 KB Output is correct
7 Correct 41 ms 54980 KB Output is correct
8 Correct 35 ms 54984 KB Output is correct
9 Correct 34 ms 54968 KB Output is correct
10 Correct 34 ms 54956 KB Output is correct
11 Correct 37 ms 55000 KB Output is correct
12 Correct 34 ms 54992 KB Output is correct
13 Correct 33 ms 54888 KB Output is correct
14 Correct 32 ms 54988 KB Output is correct
15 Correct 40 ms 54852 KB Output is correct
16 Correct 37 ms 54980 KB Output is correct
17 Correct 35 ms 54540 KB Output is correct
18 Correct 34 ms 54920 KB Output is correct
19 Correct 35 ms 54496 KB Output is correct
20 Correct 35 ms 54860 KB Output is correct
21 Correct 34 ms 54840 KB Output is correct
22 Correct 34 ms 54936 KB Output is correct
23 Correct 35 ms 54652 KB Output is correct
24 Correct 39 ms 55108 KB Output is correct
25 Correct 34 ms 53432 KB Output is correct
26 Correct 37 ms 53432 KB Output is correct
27 Correct 36 ms 54924 KB Output is correct
28 Correct 34 ms 55016 KB Output is correct
29 Correct 34 ms 54976 KB Output is correct
30 Correct 34 ms 54988 KB Output is correct
31 Correct 37 ms 54980 KB Output is correct
32 Correct 35 ms 54996 KB Output is correct
33 Correct 34 ms 54836 KB Output is correct
34 Correct 34 ms 54980 KB Output is correct
35 Correct 44 ms 54656 KB Output is correct
36 Correct 36 ms 54988 KB Output is correct
37 Correct 33 ms 54488 KB Output is correct
38 Correct 34 ms 54756 KB Output is correct
39 Correct 248 ms 98480 KB Output is correct
40 Correct 283 ms 99872 KB Output is correct
41 Correct 255 ms 99392 KB Output is correct
42 Correct 288 ms 99464 KB Output is correct
43 Correct 316 ms 101296 KB Output is correct
44 Correct 297 ms 101312 KB Output is correct
45 Correct 60 ms 55060 KB Output is correct
46 Correct 64 ms 55736 KB Output is correct
47 Correct 280 ms 98752 KB Output is correct
48 Correct 296 ms 98924 KB Output is correct
49 Correct 262 ms 98872 KB Output is correct
50 Correct 332 ms 98904 KB Output is correct
51 Correct 224 ms 86580 KB Output is correct
52 Correct 273 ms 100476 KB Output is correct
53 Correct 300 ms 89644 KB Output is correct
54 Correct 268 ms 102864 KB Output is correct
55 Correct 864 ms 193360 KB Output is correct
56 Correct 786 ms 173480 KB Output is correct
57 Correct 866 ms 209832 KB Output is correct
58 Correct 655 ms 207168 KB Output is correct
59 Correct 593 ms 169356 KB Output is correct
60 Correct 842 ms 210088 KB Output is correct
61 Correct 116 ms 51548 KB Output is correct
62 Correct 112 ms 51468 KB Output is correct
63 Correct 727 ms 210068 KB Output is correct
64 Correct 723 ms 210080 KB Output is correct
65 Correct 889 ms 210080 KB Output is correct
66 Correct 808 ms 210076 KB Output is correct
67 Correct 831 ms 209920 KB Output is correct
68 Correct 946 ms 209972 KB Output is correct
69 Correct 931 ms 210064 KB Output is correct
70 Correct 967 ms 210052 KB Output is correct
71 Execution timed out 1004 ms 209916 KB Time limit exceeded
72 Halted 0 ms 0 KB -