oj.uz

Submission #503448

# Submission time Handle Problem Language Result Execution time Memory
503448 2022-01-08T02:45:22 Z cig32 Food Court (JOI21_foodcourt) C++17
89 / 100
 1000 ms 175692 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 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, long long k) {
        a.range_add(l, r, k);
    }
    void leave(int l, int r, long long k) {
        a.range_add(l, r, -k);
        a.max_with(l, r, 0);
    }
    int service(int shop, long long 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;
            long long k;
            cin >> l >> r >> c >> k;
            ar.join(l, r, c, k);
        }
        else if(t == 2) {
            int l, r;
            long long k;
            cin >> l >> r >> k;
            ar.leave(l, r, k);
        }
        else {
            int a;
            long long b;
            cin >> a >> b;
            cout << ar.service(a, b) << "\n";
        }
    }
}
segtree_beats stb;
vector<pair<int, pair<int, long long> > > v[4*MAXN];
vector<long long> 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, long long 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, long long k) {
    ti++;
    stb.range_add(l, r, k);
    update(l, r, 0, MAXN-1, 0, c, k);
}
void leave(int l, int r, long long k) {
    stb.range_add(l, r, -k);
    stb.max_with(l, r, 0);
}
int service(int a, long long b) { // log^3 n
    int cur = rp[a];
    vector<int> q;
    long long 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;
        long long 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;
            long long k;
            cin >> l >> r >> c >> k;
            join(l, r, c, k);
        }
        else if(t == 2) {
            int l, r;
            long long k;
            cin >> l >> r >> k;
            leave(l, r, k);
        }
        else {
            int a;
            long long 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(int)':
foodcourt.cpp:81:19: warning: unused variable 'max1' [-Wunused-variable]
   81 |         long long max1, max2, maxc;
      |                   ^~~~
foodcourt.cpp:81:25: warning: unused variable 'max2' [-Wunused-variable]
   81 |         long long max1, max2, maxc;
      |                         ^~~~
foodcourt.cpp:81:31: warning: unused variable 'maxc' [-Wunused-variable]
   81 |         long long max1, max2, maxc;
      |                               ^~~~
foodcourt.cpp:82:19: warning: unused variable 'min1' [-Wunused-variable]
   82 |         long long min1, min2, minc;
      |                   ^~~~
foodcourt.cpp:82:25: warning: unused variable 'min2' [-Wunused-variable]
   82 |         long long min1, min2, minc;
      |                         ^~~~
foodcourt.cpp:82:31: warning: unused variable 'minc' [-Wunused-variable]
   82 |         long long min1, min2, minc;
      |                               ^~~~
foodcourt.cpp:83:19: warning: unused variable 'lazy' [-Wunused-variable]
   83 |         long long lazy, sum;
      |                   ^~~~
foodcourt.cpp:83:25: warning: unused variable 'sum' [-Wunused-variable]
   83 |         long long lazy, sum;
      |                         ^~~
foodcourt.cpp:84:19: warning: unused variable 'l' [-Wunused-variable]
   84 |         long long l, r;
      |                   ^
foodcourt.cpp:84:22: warning: unused variable 'r' [-Wunused-variable]
   84 |         long long l, r;
      |                      ^
foodcourt.cpp: In function 'int service(int, long long int)':
foodcourt.cpp:292:17: warning: control reaches end of non-void function [-Wreturn-type]
  292 |     vector<int> q;
      |                 ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 50892 KB Output is correct
2 Correct 30 ms 51268 KB Output is correct
3 Correct 31 ms 51240 KB Output is correct
4 Correct 30 ms 51404 KB Output is correct
5 Correct 36 ms 50356 KB Output is correct
6 Correct 30 ms 50396 KB Output is correct
7 Correct 43 ms 51288 KB Output is correct
8 Correct 31 ms 51312 KB Output is correct
9 Correct 35 ms 51272 KB Output is correct
10 Correct 32 ms 51324 KB Output is correct
11 Correct 32 ms 51356 KB Output is correct
12 Correct 32 ms 51264 KB Output is correct
13 Correct 37 ms 51344 KB Output is correct
14 Correct 34 ms 51348 KB Output is correct
15 Correct 32 ms 51232 KB Output is correct
16 Correct 30 ms 51532 KB Output is correct
17 Correct 31 ms 51012 KB Output is correct
18 Correct 34 ms 51268 KB Output is correct
19 Correct 31 ms 50940 KB Output is correct
20 Correct 32 ms 51176 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 50892 KB Output is correct
2 Correct 30 ms 51268 KB Output is correct
3 Correct 31 ms 51240 KB Output is correct
4 Correct 30 ms 51404 KB Output is correct
5 Correct 36 ms 50356 KB Output is correct
6 Correct 30 ms 50396 KB Output is correct
7 Correct 43 ms 51288 KB Output is correct
8 Correct 31 ms 51312 KB Output is correct
9 Correct 35 ms 51272 KB Output is correct
10 Correct 32 ms 51324 KB Output is correct
11 Correct 32 ms 51356 KB Output is correct
12 Correct 32 ms 51264 KB Output is correct
13 Correct 37 ms 51344 KB Output is correct
14 Correct 34 ms 51348 KB Output is correct
15 Correct 32 ms 51232 KB Output is correct
16 Correct 30 ms 51532 KB Output is correct
17 Correct 31 ms 51012 KB Output is correct
18 Correct 34 ms 51268 KB Output is correct
19 Correct 31 ms 50940 KB Output is correct
20 Correct 32 ms 51176 KB Output is correct
21 Correct 31 ms 51112 KB Output is correct
22 Correct 31 ms 51224 KB Output is correct
23 Correct 34 ms 51084 KB Output is correct
24 Correct 31 ms 51456 KB Output is correct
25 Correct 31 ms 50468 KB Output is correct
26 Correct 33 ms 50376 KB Output is correct
27 Correct 44 ms 51236 KB Output is correct
28 Correct 31 ms 51276 KB Output is correct
29 Correct 31 ms 51316 KB Output is correct
30 Correct 31 ms 51360 KB Output is correct
31 Correct 31 ms 51280 KB Output is correct
32 Correct 33 ms 51280 KB Output is correct
33 Correct 30 ms 51288 KB Output is correct
34 Correct 40 ms 51452 KB Output is correct
35 Correct 34 ms 51228 KB Output is correct
36 Correct 38 ms 51488 KB Output is correct
37 Correct 30 ms 50884 KB Output is correct
38 Correct 31 ms 51140 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 73872 KB Output is correct
2 Correct 246 ms 75280 KB Output is correct
3 Correct 227 ms 74780 KB Output is correct
4 Correct 187 ms 74836 KB Output is correct
5 Correct 253 ms 76676 KB Output is correct
6 Correct 213 ms 76680 KB Output is correct
7 Correct 56 ms 51404 KB Output is correct
8 Correct 59 ms 51924 KB Output is correct
9 Correct 175 ms 75332 KB Output is correct
10 Correct 225 ms 75360 KB Output is correct
11 Correct 181 ms 75388 KB Output is correct
12 Correct 193 ms 75416 KB Output is correct
13 Correct 179 ms 69712 KB Output is correct
14 Correct 200 ms 77124 KB Output is correct
15 Correct 184 ms 72768 KB Output is correct
16 Correct 224 ms 79472 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 117716 KB Output is correct
2 Correct 494 ms 108320 KB Output is correct
3 Correct 596 ms 125668 KB Output is correct
4 Correct 349 ms 125296 KB Output is correct
5 Correct 471 ms 106036 KB Output is correct
6 Correct 506 ms 125572 KB Output is correct
7 Correct 96 ms 47424 KB Output is correct
8 Correct 107 ms 47428 KB Output is correct
9 Correct 520 ms 125800 KB Output is correct
10 Correct 409 ms 125856 KB Output is correct
11 Correct 541 ms 125564 KB Output is correct
12 Correct 561 ms 125680 KB Output is correct
13 Correct 496 ms 125608 KB Output is correct
14 Correct 554 ms 125684 KB Output is correct
15 Correct 684 ms 125836 KB Output is correct
16 Correct 560 ms 125668 KB Output is correct
17 Correct 557 ms 125644 KB Output is correct
18 Correct 525 ms 125572 KB Output is correct
19 Correct 531 ms 125692 KB Output is correct
20 Correct 547 ms 125568 KB Output is correct
21 Correct 672 ms 125740 KB Output is correct
22 Correct 563 ms 125680 KB Output is correct
23 Correct 598 ms 125668 KB Output is correct
24 Correct 593 ms 125772 KB Output is correct
25 Correct 433 ms 107816 KB Output is correct
26 Correct 398 ms 125732 KB Output is correct
27 Correct 467 ms 125588 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 50892 KB Output is correct
2 Correct 30 ms 51268 KB Output is correct
3 Correct 31 ms 51240 KB Output is correct
4 Correct 30 ms 51404 KB Output is correct
5 Correct 36 ms 50356 KB Output is correct
6 Correct 30 ms 50396 KB Output is correct
7 Correct 43 ms 51288 KB Output is correct
8 Correct 31 ms 51312 KB Output is correct
9 Correct 35 ms 51272 KB Output is correct
10 Correct 32 ms 51324 KB Output is correct
11 Correct 32 ms 51356 KB Output is correct
12 Correct 32 ms 51264 KB Output is correct
13 Correct 37 ms 51344 KB Output is correct
14 Correct 34 ms 51348 KB Output is correct
15 Correct 32 ms 51232 KB Output is correct
16 Correct 30 ms 51532 KB Output is correct
17 Correct 31 ms 51012 KB Output is correct
18 Correct 34 ms 51268 KB Output is correct
19 Correct 31 ms 50940 KB Output is correct
20 Correct 32 ms 51176 KB Output is correct
21 Correct 183 ms 73872 KB Output is correct
22 Correct 246 ms 75280 KB Output is correct
23 Correct 227 ms 74780 KB Output is correct
24 Correct 187 ms 74836 KB Output is correct
25 Correct 253 ms 76676 KB Output is correct
26 Correct 213 ms 76680 KB Output is correct
27 Correct 56 ms 51404 KB Output is correct
28 Correct 59 ms 51924 KB Output is correct
29 Correct 175 ms 75332 KB Output is correct
30 Correct 225 ms 75360 KB Output is correct
31 Correct 181 ms 75388 KB Output is correct
32 Correct 193 ms 75416 KB Output is correct
33 Correct 179 ms 69712 KB Output is correct
34 Correct 200 ms 77124 KB Output is correct
35 Correct 184 ms 72768 KB Output is correct
36 Correct 224 ms 79472 KB Output is correct
37 Correct 300 ms 82004 KB Output is correct
38 Correct 263 ms 86416 KB Output is correct
39 Correct 56 ms 51840 KB Output is correct
40 Correct 67 ms 52628 KB Output is correct
41 Correct 368 ms 87644 KB Output is correct
42 Correct 323 ms 87752 KB Output is correct
43 Correct 311 ms 87660 KB Output is correct
44 Correct 330 ms 87548 KB Output is correct
45 Correct 305 ms 87648 KB Output is correct
46 Correct 325 ms 87884 KB Output is correct
47 Correct 141 ms 88376 KB Output is correct
48 Correct 199 ms 85980 KB Output is correct
49 Correct 234 ms 76656 KB Output is correct
50 Correct 293 ms 85296 KB Output is correct
51 Correct 361 ms 88312 KB Output is correct
52 Correct 329 ms 88324 KB Output is correct
53 Correct 172 ms 75080 KB Output is correct
54 Correct 203 ms 79500 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 89276 KB Output is correct
2 Correct 431 ms 88464 KB Output is correct
3 Correct 435 ms 92288 KB Output is correct
4 Correct 372 ms 85880 KB Output is correct
5 Correct 363 ms 89788 KB Output is correct
6 Correct 435 ms 93384 KB Output is correct
7 Correct 87 ms 52728 KB Output is correct
8 Correct 83 ms 53272 KB Output is correct
9 Correct 192 ms 96048 KB Output is correct
10 Correct 157 ms 86136 KB Output is correct
11 Correct 205 ms 92872 KB Output is correct
12 Correct 208 ms 92844 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 50892 KB Output is correct
2 Correct 30 ms 51268 KB Output is correct
3 Correct 31 ms 51240 KB Output is correct
4 Correct 30 ms 51404 KB Output is correct
5 Correct 36 ms 50356 KB Output is correct
6 Correct 30 ms 50396 KB Output is correct
7 Correct 43 ms 51288 KB Output is correct
8 Correct 31 ms 51312 KB Output is correct
9 Correct 35 ms 51272 KB Output is correct
10 Correct 32 ms 51324 KB Output is correct
11 Correct 32 ms 51356 KB Output is correct
12 Correct 32 ms 51264 KB Output is correct
13 Correct 37 ms 51344 KB Output is correct
14 Correct 34 ms 51348 KB Output is correct
15 Correct 32 ms 51232 KB Output is correct
16 Correct 30 ms 51532 KB Output is correct
17 Correct 31 ms 51012 KB Output is correct
18 Correct 34 ms 51268 KB Output is correct
19 Correct 31 ms 50940 KB Output is correct
20 Correct 32 ms 51176 KB Output is correct
21 Correct 31 ms 51112 KB Output is correct
22 Correct 31 ms 51224 KB Output is correct
23 Correct 34 ms 51084 KB Output is correct
24 Correct 31 ms 51456 KB Output is correct
25 Correct 31 ms 50468 KB Output is correct
26 Correct 33 ms 50376 KB Output is correct
27 Correct 44 ms 51236 KB Output is correct
28 Correct 31 ms 51276 KB Output is correct
29 Correct 31 ms 51316 KB Output is correct
30 Correct 31 ms 51360 KB Output is correct
31 Correct 31 ms 51280 KB Output is correct
32 Correct 33 ms 51280 KB Output is correct
33 Correct 30 ms 51288 KB Output is correct
34 Correct 40 ms 51452 KB Output is correct
35 Correct 34 ms 51228 KB Output is correct
36 Correct 38 ms 51488 KB Output is correct
37 Correct 30 ms 50884 KB Output is correct
38 Correct 31 ms 51140 KB Output is correct
39 Correct 183 ms 73872 KB Output is correct
40 Correct 246 ms 75280 KB Output is correct
41 Correct 227 ms 74780 KB Output is correct
42 Correct 187 ms 74836 KB Output is correct
43 Correct 253 ms 76676 KB Output is correct
44 Correct 213 ms 76680 KB Output is correct
45 Correct 56 ms 51404 KB Output is correct
46 Correct 59 ms 51924 KB Output is correct
47 Correct 175 ms 75332 KB Output is correct
48 Correct 225 ms 75360 KB Output is correct
49 Correct 181 ms 75388 KB Output is correct
50 Correct 193 ms 75416 KB Output is correct
51 Correct 179 ms 69712 KB Output is correct
52 Correct 200 ms 77124 KB Output is correct
53 Correct 184 ms 72768 KB Output is correct
54 Correct 224 ms 79472 KB Output is correct
55 Correct 300 ms 82004 KB Output is correct
56 Correct 263 ms 86416 KB Output is correct
57 Correct 56 ms 51840 KB Output is correct
58 Correct 67 ms 52628 KB Output is correct
59 Correct 368 ms 87644 KB Output is correct
60 Correct 323 ms 87752 KB Output is correct
61 Correct 311 ms 87660 KB Output is correct
62 Correct 330 ms 87548 KB Output is correct
63 Correct 305 ms 87648 KB Output is correct
64 Correct 325 ms 87884 KB Output is correct
65 Correct 141 ms 88376 KB Output is correct
66 Correct 199 ms 85980 KB Output is correct
67 Correct 234 ms 76656 KB Output is correct
68 Correct 293 ms 85296 KB Output is correct
69 Correct 361 ms 88312 KB Output is correct
70 Correct 329 ms 88324 KB Output is correct
71 Correct 172 ms 75080 KB Output is correct
72 Correct 203 ms 79500 KB Output is correct
73 Correct 399 ms 89276 KB Output is correct
74 Correct 431 ms 88464 KB Output is correct
75 Correct 435 ms 92288 KB Output is correct
76 Correct 372 ms 85880 KB Output is correct
77 Correct 363 ms 89788 KB Output is correct
78 Correct 435 ms 93384 KB Output is correct
79 Correct 87 ms 52728 KB Output is correct
80 Correct 83 ms 53272 KB Output is correct
81 Correct 192 ms 96048 KB Output is correct
82 Correct 157 ms 86136 KB Output is correct
83 Correct 205 ms 92872 KB Output is correct
84 Correct 208 ms 92844 KB Output is correct
85 Correct 292 ms 79996 KB Output is correct
86 Correct 336 ms 86084 KB Output is correct
87 Correct 277 ms 89268 KB Output is correct
88 Correct 347 ms 93364 KB Output is correct
89 Correct 205 ms 78028 KB Output is correct
90 Correct 303 ms 88312 KB Output is correct
91 Correct 249 ms 77884 KB Output is correct
92 Correct 234 ms 77280 KB Output is correct
93 Correct 307 ms 88128 KB Output is correct
94 Correct 295 ms 88312 KB Output is correct
95 Correct 282 ms 85972 KB Output is correct
96 Correct 294 ms 88440 KB Output is correct
97 Correct 312 ms 88224 KB Output is correct
98 Correct 250 ms 79420 KB Output is correct
99 Correct 136 ms 89076 KB Output is correct
100 Correct 149 ms 80964 KB Output is correct
101 Correct 179 ms 86364 KB Output is correct
102 Correct 212 ms 82500 KB Output is correct

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 50892 KB Output is correct
2 Correct 30 ms 51268 KB Output is correct
3 Correct 31 ms 51240 KB Output is correct
4 Correct 30 ms 51404 KB Output is correct
5 Correct 36 ms 50356 KB Output is correct
6 Correct 30 ms 50396 KB Output is correct
7 Correct 43 ms 51288 KB Output is correct
8 Correct 31 ms 51312 KB Output is correct
9 Correct 35 ms 51272 KB Output is correct
10 Correct 32 ms 51324 KB Output is correct
11 Correct 32 ms 51356 KB Output is correct
12 Correct 32 ms 51264 KB Output is correct
13 Correct 37 ms 51344 KB Output is correct
14 Correct 34 ms 51348 KB Output is correct
15 Correct 32 ms 51232 KB Output is correct
16 Correct 30 ms 51532 KB Output is correct
17 Correct 31 ms 51012 KB Output is correct
18 Correct 34 ms 51268 KB Output is correct
19 Correct 31 ms 50940 KB Output is correct
20 Correct 32 ms 51176 KB Output is correct
21 Correct 31 ms 51112 KB Output is correct
22 Correct 31 ms 51224 KB Output is correct
23 Correct 34 ms 51084 KB Output is correct
24 Correct 31 ms 51456 KB Output is correct
25 Correct 31 ms 50468 KB Output is correct
26 Correct 33 ms 50376 KB Output is correct
27 Correct 44 ms 51236 KB Output is correct
28 Correct 31 ms 51276 KB Output is correct
29 Correct 31 ms 51316 KB Output is correct
30 Correct 31 ms 51360 KB Output is correct
31 Correct 31 ms 51280 KB Output is correct
32 Correct 33 ms 51280 KB Output is correct
33 Correct 30 ms 51288 KB Output is correct
34 Correct 40 ms 51452 KB Output is correct
35 Correct 34 ms 51228 KB Output is correct
36 Correct 38 ms 51488 KB Output is correct
37 Correct 30 ms 50884 KB Output is correct
38 Correct 31 ms 51140 KB Output is correct
39 Correct 183 ms 73872 KB Output is correct
40 Correct 246 ms 75280 KB Output is correct
41 Correct 227 ms 74780 KB Output is correct
42 Correct 187 ms 74836 KB Output is correct
43 Correct 253 ms 76676 KB Output is correct
44 Correct 213 ms 76680 KB Output is correct
45 Correct 56 ms 51404 KB Output is correct
46 Correct 59 ms 51924 KB Output is correct
47 Correct 175 ms 75332 KB Output is correct
48 Correct 225 ms 75360 KB Output is correct
49 Correct 181 ms 75388 KB Output is correct
50 Correct 193 ms 75416 KB Output is correct
51 Correct 179 ms 69712 KB Output is correct
52 Correct 200 ms 77124 KB Output is correct
53 Correct 184 ms 72768 KB Output is correct
54 Correct 224 ms 79472 KB Output is correct
55 Correct 481 ms 117716 KB Output is correct
56 Correct 494 ms 108320 KB Output is correct
57 Correct 596 ms 125668 KB Output is correct
58 Correct 349 ms 125296 KB Output is correct
59 Correct 471 ms 106036 KB Output is correct
60 Correct 506 ms 125572 KB Output is correct
61 Correct 96 ms 47424 KB Output is correct
62 Correct 107 ms 47428 KB Output is correct
63 Correct 520 ms 125800 KB Output is correct
64 Correct 409 ms 125856 KB Output is correct
65 Correct 541 ms 125564 KB Output is correct
66 Correct 561 ms 125680 KB Output is correct
67 Correct 496 ms 125608 KB Output is correct
68 Correct 554 ms 125684 KB Output is correct
69 Correct 684 ms 125836 KB Output is correct
70 Correct 560 ms 125668 KB Output is correct
71 Correct 557 ms 125644 KB Output is correct
72 Correct 525 ms 125572 KB Output is correct
73 Correct 531 ms 125692 KB Output is correct
74 Correct 547 ms 125568 KB Output is correct
75 Correct 672 ms 125740 KB Output is correct
76 Correct 563 ms 125680 KB Output is correct
77 Correct 598 ms 125668 KB Output is correct
78 Correct 593 ms 125772 KB Output is correct
79 Correct 433 ms 107816 KB Output is correct
80 Correct 398 ms 125732 KB Output is correct
81 Correct 467 ms 125588 KB Output is correct
82 Correct 300 ms 82004 KB Output is correct
83 Correct 263 ms 86416 KB Output is correct
84 Correct 56 ms 51840 KB Output is correct
85 Correct 67 ms 52628 KB Output is correct
86 Correct 368 ms 87644 KB Output is correct
87 Correct 323 ms 87752 KB Output is correct
88 Correct 311 ms 87660 KB Output is correct
89 Correct 330 ms 87548 KB Output is correct
90 Correct 305 ms 87648 KB Output is correct
91 Correct 325 ms 87884 KB Output is correct
92 Correct 141 ms 88376 KB Output is correct
93 Correct 199 ms 85980 KB Output is correct
94 Correct 234 ms 76656 KB Output is correct
95 Correct 293 ms 85296 KB Output is correct
96 Correct 361 ms 88312 KB Output is correct
97 Correct 329 ms 88324 KB Output is correct
98 Correct 172 ms 75080 KB Output is correct
99 Correct 203 ms 79500 KB Output is correct
100 Correct 399 ms 89276 KB Output is correct
101 Correct 431 ms 88464 KB Output is correct
102 Correct 435 ms 92288 KB Output is correct
103 Correct 372 ms 85880 KB Output is correct
104 Correct 363 ms 89788 KB Output is correct
105 Correct 435 ms 93384 KB Output is correct
106 Correct 87 ms 52728 KB Output is correct
107 Correct 83 ms 53272 KB Output is correct
108 Correct 192 ms 96048 KB Output is correct
109 Correct 157 ms 86136 KB Output is correct
110 Correct 205 ms 92872 KB Output is correct
111 Correct 208 ms 92844 KB Output is correct
112 Correct 292 ms 79996 KB Output is correct
113 Correct 336 ms 86084 KB Output is correct
114 Correct 277 ms 89268 KB Output is correct
115 Correct 347 ms 93364 KB Output is correct
116 Correct 205 ms 78028 KB Output is correct
117 Correct 303 ms 88312 KB Output is correct
118 Correct 249 ms 77884 KB Output is correct
119 Correct 234 ms 77280 KB Output is correct
120 Correct 307 ms 88128 KB Output is correct
121 Correct 295 ms 88312 KB Output is correct
122 Correct 282 ms 85972 KB Output is correct
123 Correct 294 ms 88440 KB Output is correct
124 Correct 312 ms 88224 KB Output is correct
125 Correct 250 ms 79420 KB Output is correct
126 Correct 136 ms 89076 KB Output is correct
127 Correct 149 ms 80964 KB Output is correct
128 Correct 179 ms 86364 KB Output is correct
129 Correct 212 ms 82500 KB Output is correct
130 Execution timed out 1078 ms 175692 KB Time limit exceeded
131 Halted 0 ms 0 KB -