oj.uz

Submission #503176

# Submission time Handle Problem Language Result Execution time Memory
503176 2022-01-07T12:38:01 Z cig32 Food Court (JOI21_foodcourt) C++17
89 / 100
 1000 ms 172120 KB 
#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(long long x, long long y) { return x > y; }
    int stok;
    const long long extr = 2e18;
    struct node {
        long long max1, max2, maxc;
        long long min1, min2, minc;
        long long lazy, sum;
        long long l, r;
    };
    vector<node> a;
    void pushtag_max(int idx, long long 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, long long 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, long long 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) {
        long long max1, max2, maxc;
        long long min1, min2, minc;
        long long lazy, sum;
        long long 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, long long 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, long long 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, long long 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, long long 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);
    }
    long long 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(long long v) { // Initialize everything to v
        init1(0, stok, 0, v);
    }
    void min_with(int l, int r, long long v) {
        u1(l, r, 0, stok, 0, v);
    }
    void max_with(int l, int r, long long v) {
        u2(l, r, 0, stok, 0, v);
    }
    void range_add(int l, int r, long long 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;
            if(v[x][w[x].size() - 1].first <= mid) lb2 = 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:85:19: warning: unused variable 'max1' [-Wunused-variable]
   85 |         long long max1, max2, maxc;
      |                   ^~~~
foodcourt.cpp:85:25: warning: unused variable 'max2' [-Wunused-variable]
   85 |         long long max1, max2, maxc;
      |                         ^~~~
foodcourt.cpp:85:31: warning: unused variable 'maxc' [-Wunused-variable]
   85 |         long long max1, max2, maxc;
      |                               ^~~~
foodcourt.cpp:86:19: warning: unused variable 'min1' [-Wunused-variable]
   86 |         long long min1, min2, minc;
      |                   ^~~~
foodcourt.cpp:86:25: warning: unused variable 'min2' [-Wunused-variable]
   86 |         long long min1, min2, minc;
      |                         ^~~~
foodcourt.cpp:86:31: warning: unused variable 'minc' [-Wunused-variable]
   86 |         long long min1, min2, minc;
      |                               ^~~~
foodcourt.cpp:87:19: warning: unused variable 'lazy' [-Wunused-variable]
   87 |         long long lazy, sum;
      |                   ^~~~
foodcourt.cpp:87:25: warning: unused variable 'sum' [-Wunused-variable]
   87 |         long long lazy, sum;
      |                         ^~~
foodcourt.cpp:88:19: warning: unused variable 'l' [-Wunused-variable]
   88 |         long long l, r;
      |                   ^
foodcourt.cpp:88:22: warning: unused variable 'r' [-Wunused-variable]
   88 |         long long l, r;
      |                      ^
foodcourt.cpp: In function 'long long int service(long long int, long long int)':
foodcourt.cpp:293:17: warning: control reaches end of non-void function [-Wreturn-type]
  293 |     vector<int> q;
      |                 ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 53964 KB Output is correct
2 Correct 31 ms 54160 KB Output is correct
3 Correct 36 ms 54244 KB Output is correct
4 Correct 38 ms 54376 KB Output is correct
5 Correct 30 ms 53392 KB Output is correct
6 Correct 26 ms 53392 KB Output is correct
7 Correct 32 ms 54284 KB Output is correct
8 Correct 29 ms 54348 KB Output is correct
9 Correct 31 ms 54348 KB Output is correct
10 Correct 30 ms 54288 KB Output is correct
11 Correct 29 ms 54364 KB Output is correct
12 Correct 30 ms 54268 KB Output is correct
13 Correct 27 ms 54316 KB Output is correct
14 Correct 33 ms 54308 KB Output is correct
15 Correct 31 ms 54144 KB Output is correct
16 Correct 28 ms 54328 KB Output is correct
17 Correct 29 ms 54068 KB Output is correct
18 Correct 31 ms 54280 KB Output is correct
19 Correct 28 ms 53976 KB Output is correct
20 Correct 30 ms 54200 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 53964 KB Output is correct
2 Correct 31 ms 54160 KB Output is correct
3 Correct 36 ms 54244 KB Output is correct
4 Correct 38 ms 54376 KB Output is correct
5 Correct 30 ms 53392 KB Output is correct
6 Correct 26 ms 53392 KB Output is correct
7 Correct 32 ms 54284 KB Output is correct
8 Correct 29 ms 54348 KB Output is correct
9 Correct 31 ms 54348 KB Output is correct
10 Correct 30 ms 54288 KB Output is correct
11 Correct 29 ms 54364 KB Output is correct
12 Correct 30 ms 54268 KB Output is correct
13 Correct 27 ms 54316 KB Output is correct
14 Correct 33 ms 54308 KB Output is correct
15 Correct 31 ms 54144 KB Output is correct
16 Correct 28 ms 54328 KB Output is correct
17 Correct 29 ms 54068 KB Output is correct
18 Correct 31 ms 54280 KB Output is correct
19 Correct 28 ms 53976 KB Output is correct
20 Correct 30 ms 54200 KB Output is correct
21 Correct 29 ms 54148 KB Output is correct
22 Correct 29 ms 54264 KB Output is correct
23 Correct 30 ms 54144 KB Output is correct
24 Correct 40 ms 54428 KB Output is correct
25 Correct 28 ms 53380 KB Output is correct
26 Correct 28 ms 53360 KB Output is correct
27 Correct 31 ms 54212 KB Output is correct
28 Correct 31 ms 54356 KB Output is correct
29 Correct 30 ms 54208 KB Output is correct
30 Correct 36 ms 54348 KB Output is correct
31 Correct 31 ms 54236 KB Output is correct
32 Correct 33 ms 54272 KB Output is correct
33 Correct 28 ms 54284 KB Output is correct
34 Correct 28 ms 54348 KB Output is correct
35 Correct 31 ms 54216 KB Output is correct
36 Correct 31 ms 54320 KB Output is correct
37 Correct 31 ms 53972 KB Output is correct
38 Correct 29 ms 54120 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 76800 KB Output is correct
2 Correct 233 ms 78264 KB Output is correct
3 Correct 205 ms 77880 KB Output is correct
4 Correct 208 ms 77800 KB Output is correct
5 Correct 209 ms 79688 KB Output is correct
6 Correct 206 ms 79716 KB Output is correct
7 Correct 58 ms 54356 KB Output is correct
8 Correct 74 ms 54960 KB Output is correct
9 Correct 196 ms 77248 KB Output is correct
10 Correct 197 ms 77188 KB Output is correct
11 Correct 207 ms 77192 KB Output is correct
12 Correct 181 ms 77252 KB Output is correct
13 Correct 171 ms 71748 KB Output is correct
14 Correct 192 ms 79040 KB Output is correct
15 Correct 183 ms 74464 KB Output is correct
16 Correct 204 ms 81184 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 570 ms 117700 KB Output is correct
2 Correct 446 ms 108320 KB Output is correct
3 Correct 527 ms 125656 KB Output is correct
4 Correct 355 ms 124972 KB Output is correct
5 Correct 344 ms 106048 KB Output is correct
6 Correct 507 ms 125920 KB Output is correct
7 Correct 96 ms 47428 KB Output is correct
8 Correct 96 ms 47424 KB Output is correct
9 Correct 471 ms 125860 KB Output is correct
10 Correct 429 ms 125808 KB Output is correct
11 Correct 512 ms 125680 KB Output is correct
12 Correct 486 ms 125664 KB Output is correct
13 Correct 485 ms 125784 KB Output is correct
14 Correct 532 ms 125648 KB Output is correct
15 Correct 585 ms 125656 KB Output is correct
16 Correct 554 ms 125660 KB Output is correct
17 Correct 579 ms 125856 KB Output is correct
18 Correct 536 ms 125684 KB Output is correct
19 Correct 589 ms 125620 KB Output is correct
20 Correct 548 ms 125708 KB Output is correct
21 Correct 597 ms 125636 KB Output is correct
22 Correct 634 ms 125736 KB Output is correct
23 Correct 589 ms 125600 KB Output is correct
24 Correct 594 ms 125680 KB Output is correct
25 Correct 374 ms 107836 KB Output is correct
26 Correct 399 ms 125764 KB Output is correct
27 Correct 425 ms 125608 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 53964 KB Output is correct
2 Correct 31 ms 54160 KB Output is correct
3 Correct 36 ms 54244 KB Output is correct
4 Correct 38 ms 54376 KB Output is correct
5 Correct 30 ms 53392 KB Output is correct
6 Correct 26 ms 53392 KB Output is correct
7 Correct 32 ms 54284 KB Output is correct
8 Correct 29 ms 54348 KB Output is correct
9 Correct 31 ms 54348 KB Output is correct
10 Correct 30 ms 54288 KB Output is correct
11 Correct 29 ms 54364 KB Output is correct
12 Correct 30 ms 54268 KB Output is correct
13 Correct 27 ms 54316 KB Output is correct
14 Correct 33 ms 54308 KB Output is correct
15 Correct 31 ms 54144 KB Output is correct
16 Correct 28 ms 54328 KB Output is correct
17 Correct 29 ms 54068 KB Output is correct
18 Correct 31 ms 54280 KB Output is correct
19 Correct 28 ms 53976 KB Output is correct
20 Correct 30 ms 54200 KB Output is correct
21 Correct 182 ms 76800 KB Output is correct
22 Correct 233 ms 78264 KB Output is correct
23 Correct 205 ms 77880 KB Output is correct
24 Correct 208 ms 77800 KB Output is correct
25 Correct 209 ms 79688 KB Output is correct
26 Correct 206 ms 79716 KB Output is correct
27 Correct 58 ms 54356 KB Output is correct
28 Correct 74 ms 54960 KB Output is correct
29 Correct 196 ms 77248 KB Output is correct
30 Correct 197 ms 77188 KB Output is correct
31 Correct 207 ms 77192 KB Output is correct
32 Correct 181 ms 77252 KB Output is correct
33 Correct 171 ms 71748 KB Output is correct
34 Correct 192 ms 79040 KB Output is correct
35 Correct 183 ms 74464 KB Output is correct
36 Correct 204 ms 81184 KB Output is correct
37 Correct 314 ms 84052 KB Output is correct
38 Correct 256 ms 88492 KB Output is correct
39 Correct 70 ms 54332 KB Output is correct
40 Correct 60 ms 55080 KB Output is correct
41 Correct 303 ms 89688 KB Output is correct
42 Correct 332 ms 89808 KB Output is correct
43 Correct 298 ms 89604 KB Output is correct
44 Correct 323 ms 89516 KB Output is correct
45 Correct 294 ms 89736 KB Output is correct
46 Correct 348 ms 89792 KB Output is correct
47 Correct 135 ms 90304 KB Output is correct
48 Correct 166 ms 88024 KB Output is correct
49 Correct 271 ms 78936 KB Output is correct
50 Correct 272 ms 87420 KB Output is correct
51 Correct 327 ms 90240 KB Output is correct
52 Correct 323 ms 90264 KB Output is correct
53 Correct 155 ms 77080 KB Output is correct
54 Correct 237 ms 81360 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 91000 KB Output is correct
2 Correct 410 ms 90036 KB Output is correct
3 Correct 519 ms 93764 KB Output is correct
4 Correct 291 ms 87660 KB Output is correct
5 Correct 373 ms 91324 KB Output is correct
6 Correct 430 ms 94628 KB Output is correct
7 Correct 80 ms 54652 KB Output is correct
8 Correct 81 ms 55244 KB Output is correct
9 Correct 179 ms 97160 KB Output is correct
10 Correct 156 ms 87980 KB Output is correct
11 Correct 212 ms 94148 KB Output is correct
12 Correct 250 ms 94152 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 53964 KB Output is correct
2 Correct 31 ms 54160 KB Output is correct
3 Correct 36 ms 54244 KB Output is correct
4 Correct 38 ms 54376 KB Output is correct
5 Correct 30 ms 53392 KB Output is correct
6 Correct 26 ms 53392 KB Output is correct
7 Correct 32 ms 54284 KB Output is correct
8 Correct 29 ms 54348 KB Output is correct
9 Correct 31 ms 54348 KB Output is correct
10 Correct 30 ms 54288 KB Output is correct
11 Correct 29 ms 54364 KB Output is correct
12 Correct 30 ms 54268 KB Output is correct
13 Correct 27 ms 54316 KB Output is correct
14 Correct 33 ms 54308 KB Output is correct
15 Correct 31 ms 54144 KB Output is correct
16 Correct 28 ms 54328 KB Output is correct
17 Correct 29 ms 54068 KB Output is correct
18 Correct 31 ms 54280 KB Output is correct
19 Correct 28 ms 53976 KB Output is correct
20 Correct 30 ms 54200 KB Output is correct
21 Correct 29 ms 54148 KB Output is correct
22 Correct 29 ms 54264 KB Output is correct
23 Correct 30 ms 54144 KB Output is correct
24 Correct 40 ms 54428 KB Output is correct
25 Correct 28 ms 53380 KB Output is correct
26 Correct 28 ms 53360 KB Output is correct
27 Correct 31 ms 54212 KB Output is correct
28 Correct 31 ms 54356 KB Output is correct
29 Correct 30 ms 54208 KB Output is correct
30 Correct 36 ms 54348 KB Output is correct
31 Correct 31 ms 54236 KB Output is correct
32 Correct 33 ms 54272 KB Output is correct
33 Correct 28 ms 54284 KB Output is correct
34 Correct 28 ms 54348 KB Output is correct
35 Correct 31 ms 54216 KB Output is correct
36 Correct 31 ms 54320 KB Output is correct
37 Correct 31 ms 53972 KB Output is correct
38 Correct 29 ms 54120 KB Output is correct
39 Correct 182 ms 76800 KB Output is correct
40 Correct 233 ms 78264 KB Output is correct
41 Correct 205 ms 77880 KB Output is correct
42 Correct 208 ms 77800 KB Output is correct
43 Correct 209 ms 79688 KB Output is correct
44 Correct 206 ms 79716 KB Output is correct
45 Correct 58 ms 54356 KB Output is correct
46 Correct 74 ms 54960 KB Output is correct
47 Correct 196 ms 77248 KB Output is correct
48 Correct 197 ms 77188 KB Output is correct
49 Correct 207 ms 77192 KB Output is correct
50 Correct 181 ms 77252 KB Output is correct
51 Correct 171 ms 71748 KB Output is correct
52 Correct 192 ms 79040 KB Output is correct
53 Correct 183 ms 74464 KB Output is correct
54 Correct 204 ms 81184 KB Output is correct
55 Correct 314 ms 84052 KB Output is correct
56 Correct 256 ms 88492 KB Output is correct
57 Correct 70 ms 54332 KB Output is correct
58 Correct 60 ms 55080 KB Output is correct
59 Correct 303 ms 89688 KB Output is correct
60 Correct 332 ms 89808 KB Output is correct
61 Correct 298 ms 89604 KB Output is correct
62 Correct 323 ms 89516 KB Output is correct
63 Correct 294 ms 89736 KB Output is correct
64 Correct 348 ms 89792 KB Output is correct
65 Correct 135 ms 90304 KB Output is correct
66 Correct 166 ms 88024 KB Output is correct
67 Correct 271 ms 78936 KB Output is correct
68 Correct 272 ms 87420 KB Output is correct
69 Correct 327 ms 90240 KB Output is correct
70 Correct 323 ms 90264 KB Output is correct
71 Correct 155 ms 77080 KB Output is correct
72 Correct 237 ms 81360 KB Output is correct
73 Correct 378 ms 91000 KB Output is correct
74 Correct 410 ms 90036 KB Output is correct
75 Correct 519 ms 93764 KB Output is correct
76 Correct 291 ms 87660 KB Output is correct
77 Correct 373 ms 91324 KB Output is correct
78 Correct 430 ms 94628 KB Output is correct
79 Correct 80 ms 54652 KB Output is correct
80 Correct 81 ms 55244 KB Output is correct
81 Correct 179 ms 97160 KB Output is correct
82 Correct 156 ms 87980 KB Output is correct
83 Correct 212 ms 94148 KB Output is correct
84 Correct 250 ms 94152 KB Output is correct
85 Correct 300 ms 81752 KB Output is correct
86 Correct 311 ms 87612 KB Output is correct
87 Correct 274 ms 90908 KB Output is correct
88 Correct 338 ms 94628 KB Output is correct
89 Correct 205 ms 79980 KB Output is correct
90 Correct 318 ms 89772 KB Output is correct
91 Correct 240 ms 79548 KB Output is correct
92 Correct 293 ms 79144 KB Output is correct
93 Correct 325 ms 89692 KB Output is correct
94 Correct 320 ms 89676 KB Output is correct
95 Correct 282 ms 87428 KB Output is correct
96 Correct 296 ms 89924 KB Output is correct
97 Correct 338 ms 89756 KB Output is correct
98 Correct 261 ms 81040 KB Output is correct
99 Correct 185 ms 90556 KB Output is correct
100 Correct 144 ms 82812 KB Output is correct
101 Correct 176 ms 87964 KB Output is correct
102 Correct 258 ms 83916 KB Output is correct

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 53964 KB Output is correct
2 Correct 31 ms 54160 KB Output is correct
3 Correct 36 ms 54244 KB Output is correct
4 Correct 38 ms 54376 KB Output is correct
5 Correct 30 ms 53392 KB Output is correct
6 Correct 26 ms 53392 KB Output is correct
7 Correct 32 ms 54284 KB Output is correct
8 Correct 29 ms 54348 KB Output is correct
9 Correct 31 ms 54348 KB Output is correct
10 Correct 30 ms 54288 KB Output is correct
11 Correct 29 ms 54364 KB Output is correct
12 Correct 30 ms 54268 KB Output is correct
13 Correct 27 ms 54316 KB Output is correct
14 Correct 33 ms 54308 KB Output is correct
15 Correct 31 ms 54144 KB Output is correct
16 Correct 28 ms 54328 KB Output is correct
17 Correct 29 ms 54068 KB Output is correct
18 Correct 31 ms 54280 KB Output is correct
19 Correct 28 ms 53976 KB Output is correct
20 Correct 30 ms 54200 KB Output is correct
21 Correct 29 ms 54148 KB Output is correct
22 Correct 29 ms 54264 KB Output is correct
23 Correct 30 ms 54144 KB Output is correct
24 Correct 40 ms 54428 KB Output is correct
25 Correct 28 ms 53380 KB Output is correct
26 Correct 28 ms 53360 KB Output is correct
27 Correct 31 ms 54212 KB Output is correct
28 Correct 31 ms 54356 KB Output is correct
29 Correct 30 ms 54208 KB Output is correct
30 Correct 36 ms 54348 KB Output is correct
31 Correct 31 ms 54236 KB Output is correct
32 Correct 33 ms 54272 KB Output is correct
33 Correct 28 ms 54284 KB Output is correct
34 Correct 28 ms 54348 KB Output is correct
35 Correct 31 ms 54216 KB Output is correct
36 Correct 31 ms 54320 KB Output is correct
37 Correct 31 ms 53972 KB Output is correct
38 Correct 29 ms 54120 KB Output is correct
39 Correct 182 ms 76800 KB Output is correct
40 Correct 233 ms 78264 KB Output is correct
41 Correct 205 ms 77880 KB Output is correct
42 Correct 208 ms 77800 KB Output is correct
43 Correct 209 ms 79688 KB Output is correct
44 Correct 206 ms 79716 KB Output is correct
45 Correct 58 ms 54356 KB Output is correct
46 Correct 74 ms 54960 KB Output is correct
47 Correct 196 ms 77248 KB Output is correct
48 Correct 197 ms 77188 KB Output is correct
49 Correct 207 ms 77192 KB Output is correct
50 Correct 181 ms 77252 KB Output is correct
51 Correct 171 ms 71748 KB Output is correct
52 Correct 192 ms 79040 KB Output is correct
53 Correct 183 ms 74464 KB Output is correct
54 Correct 204 ms 81184 KB Output is correct
55 Correct 570 ms 117700 KB Output is correct
56 Correct 446 ms 108320 KB Output is correct
57 Correct 527 ms 125656 KB Output is correct
58 Correct 355 ms 124972 KB Output is correct
59 Correct 344 ms 106048 KB Output is correct
60 Correct 507 ms 125920 KB Output is correct
61 Correct 96 ms 47428 KB Output is correct
62 Correct 96 ms 47424 KB Output is correct
63 Correct 471 ms 125860 KB Output is correct
64 Correct 429 ms 125808 KB Output is correct
65 Correct 512 ms 125680 KB Output is correct
66 Correct 486 ms 125664 KB Output is correct
67 Correct 485 ms 125784 KB Output is correct
68 Correct 532 ms 125648 KB Output is correct
69 Correct 585 ms 125656 KB Output is correct
70 Correct 554 ms 125660 KB Output is correct
71 Correct 579 ms 125856 KB Output is correct
72 Correct 536 ms 125684 KB Output is correct
73 Correct 589 ms 125620 KB Output is correct
74 Correct 548 ms 125708 KB Output is correct
75 Correct 597 ms 125636 KB Output is correct
76 Correct 634 ms 125736 KB Output is correct
77 Correct 589 ms 125600 KB Output is correct
78 Correct 594 ms 125680 KB Output is correct
79 Correct 374 ms 107836 KB Output is correct
80 Correct 399 ms 125764 KB Output is correct
81 Correct 425 ms 125608 KB Output is correct
82 Correct 314 ms 84052 KB Output is correct
83 Correct 256 ms 88492 KB Output is correct
84 Correct 70 ms 54332 KB Output is correct
85 Correct 60 ms 55080 KB Output is correct
86 Correct 303 ms 89688 KB Output is correct
87 Correct 332 ms 89808 KB Output is correct
88 Correct 298 ms 89604 KB Output is correct
89 Correct 323 ms 89516 KB Output is correct
90 Correct 294 ms 89736 KB Output is correct
91 Correct 348 ms 89792 KB Output is correct
92 Correct 135 ms 90304 KB Output is correct
93 Correct 166 ms 88024 KB Output is correct
94 Correct 271 ms 78936 KB Output is correct
95 Correct 272 ms 87420 KB Output is correct
96 Correct 327 ms 90240 KB Output is correct
97 Correct 323 ms 90264 KB Output is correct
98 Correct 155 ms 77080 KB Output is correct
99 Correct 237 ms 81360 KB Output is correct
100 Correct 378 ms 91000 KB Output is correct
101 Correct 410 ms 90036 KB Output is correct
102 Correct 519 ms 93764 KB Output is correct
103 Correct 291 ms 87660 KB Output is correct
104 Correct 373 ms 91324 KB Output is correct
105 Correct 430 ms 94628 KB Output is correct
106 Correct 80 ms 54652 KB Output is correct
107 Correct 81 ms 55244 KB Output is correct
108 Correct 179 ms 97160 KB Output is correct
109 Correct 156 ms 87980 KB Output is correct
110 Correct 212 ms 94148 KB Output is correct
111 Correct 250 ms 94152 KB Output is correct
112 Correct 300 ms 81752 KB Output is correct
113 Correct 311 ms 87612 KB Output is correct
114 Correct 274 ms 90908 KB Output is correct
115 Correct 338 ms 94628 KB Output is correct
116 Correct 205 ms 79980 KB Output is correct
117 Correct 318 ms 89772 KB Output is correct
118 Correct 240 ms 79548 KB Output is correct
119 Correct 293 ms 79144 KB Output is correct
120 Correct 325 ms 89692 KB Output is correct
121 Correct 320 ms 89676 KB Output is correct
122 Correct 282 ms 87428 KB Output is correct
123 Correct 296 ms 89924 KB Output is correct
124 Correct 338 ms 89756 KB Output is correct
125 Correct 261 ms 81040 KB Output is correct
126 Correct 185 ms 90556 KB Output is correct
127 Correct 144 ms 82812 KB Output is correct
128 Correct 176 ms 87964 KB Output is correct
129 Correct 258 ms 83916 KB Output is correct
130 Execution timed out 1091 ms 172120 KB Time limit exceeded
131 Halted 0 ms 0 KB -