oj.uz

Submission #503180

# Submission time Handle Problem Language Result Execution time Memory
503180 2022-01-07T12:47:41 Z cig32 Food Court (JOI21_foodcourt) C++17
68 / 100
 467 ms 238108 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;
            scanf("%lld %lld %lld %lld", &l, &r, &c, &k);
            //cin >> l >> r >> c >> k;
            ar.join(l, r, c, k);
        }
        else if(t == 2) {
            int l, r, k;
            scanf("%lld %lld %lld", &l, &r, &k);
            //cin >> l >> r >> k;
            ar.leave(l, r, k);
        }
        else {
            int a, b;
            scanf("%lld %lld", &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) {
    scanf("%lld %lld %lld", &N, &M, &Q);
//    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;
        scanf("%lld", &t);
        //cin >> t;
        if(t == 1) {
            int l, r, c, k;
            scanf("%lld %lld %lld %lld", &l, &r, &c, &k);
            //cin >> l >> r >> c >> k;
            join(l, r, c, k);
        }
        else if(t == 2) {
            int l, r, k;
            scanf("%lld %lld %lld", &l, &r, &k);
            //cin >> l >> r >> k;
            leave(l, r, k);
        }
        else {
            int a, b;
            scanf("%lld %lld", &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 'void solve_1m()':
foodcourt.cpp:237:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  237 |             scanf("%lld %lld %lld %lld", &l, &r, &c, &k);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:243:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  243 |             scanf("%lld %lld %lld", &l, &r, &k);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:249:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  249 |             scanf("%lld %lld", &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp: In function 'long long int service(long long int, long long int)':
foodcourt.cpp:296:17: warning: control reaches end of non-void function [-Wreturn-type]
  296 |     vector<int> q;
      |                 ^
foodcourt.cpp: In function 'void solve(long long int)':
foodcourt.cpp:348:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  348 |     scanf("%lld %lld %lld", &N, &M, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:359:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  359 |         scanf("%lld", &t);
      |         ~~~~~^~~~~~~~~~~~
foodcourt.cpp:363:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  363 |             scanf("%lld %lld %lld %lld", &l, &r, &c, &k);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:369:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  369 |             scanf("%lld %lld %lld", &l, &r, &k);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:375:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  375 |             scanf("%lld %lld", &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 53924 KB Output is correct
2 Correct 29 ms 54216 KB Output is correct
3 Correct 30 ms 54212 KB Output is correct
4 Correct 34 ms 54328 KB Output is correct
5 Correct 32 ms 53312 KB Output is correct
6 Correct 28 ms 53324 KB Output is correct
7 Correct 30 ms 54228 KB Output is correct
8 Correct 30 ms 54328 KB Output is correct
9 Correct 30 ms 54320 KB Output is correct
10 Correct 29 ms 54260 KB Output is correct
11 Correct 29 ms 54348 KB Output is correct
12 Correct 30 ms 54332 KB Output is correct
13 Correct 27 ms 54336 KB Output is correct
14 Correct 28 ms 54364 KB Output is correct
15 Correct 32 ms 54268 KB Output is correct
16 Correct 34 ms 54332 KB Output is correct
17 Correct 31 ms 54016 KB Output is correct
18 Correct 31 ms 54340 KB Output is correct
19 Correct 29 ms 54028 KB Output is correct
20 Correct 29 ms 54140 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 53924 KB Output is correct
2 Correct 29 ms 54216 KB Output is correct
3 Correct 30 ms 54212 KB Output is correct
4 Correct 34 ms 54328 KB Output is correct
5 Correct 32 ms 53312 KB Output is correct
6 Correct 28 ms 53324 KB Output is correct
7 Correct 30 ms 54228 KB Output is correct
8 Correct 30 ms 54328 KB Output is correct
9 Correct 30 ms 54320 KB Output is correct
10 Correct 29 ms 54260 KB Output is correct
11 Correct 29 ms 54348 KB Output is correct
12 Correct 30 ms 54332 KB Output is correct
13 Correct 27 ms 54336 KB Output is correct
14 Correct 28 ms 54364 KB Output is correct
15 Correct 32 ms 54268 KB Output is correct
16 Correct 34 ms 54332 KB Output is correct
17 Correct 31 ms 54016 KB Output is correct
18 Correct 31 ms 54340 KB Output is correct
19 Correct 29 ms 54028 KB Output is correct
20 Correct 29 ms 54140 KB Output is correct
21 Correct 30 ms 54220 KB Output is correct
22 Correct 29 ms 54232 KB Output is correct
23 Correct 36 ms 54164 KB Output is correct
24 Correct 32 ms 54452 KB Output is correct
25 Correct 31 ms 53340 KB Output is correct
26 Correct 27 ms 53336 KB Output is correct
27 Correct 30 ms 54328 KB Output is correct
28 Correct 30 ms 54316 KB Output is correct
29 Correct 30 ms 54264 KB Output is correct
30 Correct 30 ms 54308 KB Output is correct
31 Correct 30 ms 54344 KB Output is correct
32 Correct 31 ms 54244 KB Output is correct
33 Correct 28 ms 54276 KB Output is correct
34 Correct 28 ms 54468 KB Output is correct
35 Correct 30 ms 54120 KB Output is correct
36 Correct 31 ms 54296 KB Output is correct
37 Correct 28 ms 53924 KB Output is correct
38 Correct 31 ms 54100 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 76948 KB Output is correct
2 Correct 196 ms 78396 KB Output is correct
3 Correct 198 ms 78148 KB Output is correct
4 Correct 232 ms 77976 KB Output is correct
5 Correct 210 ms 79784 KB Output is correct
6 Correct 226 ms 79864 KB Output is correct
7 Correct 61 ms 54420 KB Output is correct
8 Correct 82 ms 54996 KB Output is correct
9 Correct 196 ms 77252 KB Output is correct
10 Correct 193 ms 77288 KB Output is correct
11 Correct 229 ms 77360 KB Output is correct
12 Correct 192 ms 77292 KB Output is correct
13 Correct 166 ms 71888 KB Output is correct
14 Correct 198 ms 79152 KB Output is correct
15 Correct 189 ms 74564 KB Output is correct
16 Correct 195 ms 81416 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 149 ms 238108 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 53924 KB Output is correct
2 Correct 29 ms 54216 KB Output is correct
3 Correct 30 ms 54212 KB Output is correct
4 Correct 34 ms 54328 KB Output is correct
5 Correct 32 ms 53312 KB Output is correct
6 Correct 28 ms 53324 KB Output is correct
7 Correct 30 ms 54228 KB Output is correct
8 Correct 30 ms 54328 KB Output is correct
9 Correct 30 ms 54320 KB Output is correct
10 Correct 29 ms 54260 KB Output is correct
11 Correct 29 ms 54348 KB Output is correct
12 Correct 30 ms 54332 KB Output is correct
13 Correct 27 ms 54336 KB Output is correct
14 Correct 28 ms 54364 KB Output is correct
15 Correct 32 ms 54268 KB Output is correct
16 Correct 34 ms 54332 KB Output is correct
17 Correct 31 ms 54016 KB Output is correct
18 Correct 31 ms 54340 KB Output is correct
19 Correct 29 ms 54028 KB Output is correct
20 Correct 29 ms 54140 KB Output is correct
21 Correct 185 ms 76948 KB Output is correct
22 Correct 196 ms 78396 KB Output is correct
23 Correct 198 ms 78148 KB Output is correct
24 Correct 232 ms 77976 KB Output is correct
25 Correct 210 ms 79784 KB Output is correct
26 Correct 226 ms 79864 KB Output is correct
27 Correct 61 ms 54420 KB Output is correct
28 Correct 82 ms 54996 KB Output is correct
29 Correct 196 ms 77252 KB Output is correct
30 Correct 193 ms 77288 KB Output is correct
31 Correct 229 ms 77360 KB Output is correct
32 Correct 192 ms 77292 KB Output is correct
33 Correct 166 ms 71888 KB Output is correct
34 Correct 198 ms 79152 KB Output is correct
35 Correct 189 ms 74564 KB Output is correct
36 Correct 195 ms 81416 KB Output is correct
37 Correct 276 ms 84216 KB Output is correct
38 Correct 306 ms 88564 KB Output is correct
39 Correct 61 ms 54472 KB Output is correct
40 Correct 66 ms 55124 KB Output is correct
41 Correct 319 ms 89700 KB Output is correct
42 Correct 304 ms 89960 KB Output is correct
43 Correct 317 ms 89692 KB Output is correct
44 Correct 309 ms 89592 KB Output is correct
45 Correct 312 ms 89856 KB Output is correct
46 Correct 320 ms 89784 KB Output is correct
47 Correct 155 ms 90576 KB Output is correct
48 Correct 196 ms 88072 KB Output is correct
49 Correct 213 ms 79060 KB Output is correct
50 Correct 281 ms 87524 KB Output is correct
51 Correct 328 ms 90332 KB Output is correct
52 Correct 373 ms 90432 KB Output is correct
53 Correct 167 ms 77224 KB Output is correct
54 Correct 215 ms 81376 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 91092 KB Output is correct
2 Correct 467 ms 89824 KB Output is correct
3 Correct 466 ms 93884 KB Output is correct
4 Correct 326 ms 87772 KB Output is correct
5 Correct 370 ms 91588 KB Output is correct
6 Correct 432 ms 94764 KB Output is correct
7 Correct 86 ms 54744 KB Output is correct
8 Correct 96 ms 55268 KB Output is correct
9 Correct 183 ms 97228 KB Output is correct
10 Correct 157 ms 88228 KB Output is correct
11 Correct 237 ms 94284 KB Output is correct
12 Correct 212 ms 94236 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 53924 KB Output is correct
2 Correct 29 ms 54216 KB Output is correct
3 Correct 30 ms 54212 KB Output is correct
4 Correct 34 ms 54328 KB Output is correct
5 Correct 32 ms 53312 KB Output is correct
6 Correct 28 ms 53324 KB Output is correct
7 Correct 30 ms 54228 KB Output is correct
8 Correct 30 ms 54328 KB Output is correct
9 Correct 30 ms 54320 KB Output is correct
10 Correct 29 ms 54260 KB Output is correct
11 Correct 29 ms 54348 KB Output is correct
12 Correct 30 ms 54332 KB Output is correct
13 Correct 27 ms 54336 KB Output is correct
14 Correct 28 ms 54364 KB Output is correct
15 Correct 32 ms 54268 KB Output is correct
16 Correct 34 ms 54332 KB Output is correct
17 Correct 31 ms 54016 KB Output is correct
18 Correct 31 ms 54340 KB Output is correct
19 Correct 29 ms 54028 KB Output is correct
20 Correct 29 ms 54140 KB Output is correct
21 Correct 30 ms 54220 KB Output is correct
22 Correct 29 ms 54232 KB Output is correct
23 Correct 36 ms 54164 KB Output is correct
24 Correct 32 ms 54452 KB Output is correct
25 Correct 31 ms 53340 KB Output is correct
26 Correct 27 ms 53336 KB Output is correct
27 Correct 30 ms 54328 KB Output is correct
28 Correct 30 ms 54316 KB Output is correct
29 Correct 30 ms 54264 KB Output is correct
30 Correct 30 ms 54308 KB Output is correct
31 Correct 30 ms 54344 KB Output is correct
32 Correct 31 ms 54244 KB Output is correct
33 Correct 28 ms 54276 KB Output is correct
34 Correct 28 ms 54468 KB Output is correct
35 Correct 30 ms 54120 KB Output is correct
36 Correct 31 ms 54296 KB Output is correct
37 Correct 28 ms 53924 KB Output is correct
38 Correct 31 ms 54100 KB Output is correct
39 Correct 185 ms 76948 KB Output is correct
40 Correct 196 ms 78396 KB Output is correct
41 Correct 198 ms 78148 KB Output is correct
42 Correct 232 ms 77976 KB Output is correct
43 Correct 210 ms 79784 KB Output is correct
44 Correct 226 ms 79864 KB Output is correct
45 Correct 61 ms 54420 KB Output is correct
46 Correct 82 ms 54996 KB Output is correct
47 Correct 196 ms 77252 KB Output is correct
48 Correct 193 ms 77288 KB Output is correct
49 Correct 229 ms 77360 KB Output is correct
50 Correct 192 ms 77292 KB Output is correct
51 Correct 166 ms 71888 KB Output is correct
52 Correct 198 ms 79152 KB Output is correct
53 Correct 189 ms 74564 KB Output is correct
54 Correct 195 ms 81416 KB Output is correct
55 Correct 276 ms 84216 KB Output is correct
56 Correct 306 ms 88564 KB Output is correct
57 Correct 61 ms 54472 KB Output is correct
58 Correct 66 ms 55124 KB Output is correct
59 Correct 319 ms 89700 KB Output is correct
60 Correct 304 ms 89960 KB Output is correct
61 Correct 317 ms 89692 KB Output is correct
62 Correct 309 ms 89592 KB Output is correct
63 Correct 312 ms 89856 KB Output is correct
64 Correct 320 ms 89784 KB Output is correct
65 Correct 155 ms 90576 KB Output is correct
66 Correct 196 ms 88072 KB Output is correct
67 Correct 213 ms 79060 KB Output is correct
68 Correct 281 ms 87524 KB Output is correct
69 Correct 328 ms 90332 KB Output is correct
70 Correct 373 ms 90432 KB Output is correct
71 Correct 167 ms 77224 KB Output is correct
72 Correct 215 ms 81376 KB Output is correct
73 Correct 397 ms 91092 KB Output is correct
74 Correct 467 ms 89824 KB Output is correct
75 Correct 466 ms 93884 KB Output is correct
76 Correct 326 ms 87772 KB Output is correct
77 Correct 370 ms 91588 KB Output is correct
78 Correct 432 ms 94764 KB Output is correct
79 Correct 86 ms 54744 KB Output is correct
80 Correct 96 ms 55268 KB Output is correct
81 Correct 183 ms 97228 KB Output is correct
82 Correct 157 ms 88228 KB Output is correct
83 Correct 237 ms 94284 KB Output is correct
84 Correct 212 ms 94236 KB Output is correct
85 Correct 299 ms 81712 KB Output is correct
86 Correct 326 ms 87844 KB Output is correct
87 Correct 346 ms 91068 KB Output is correct
88 Correct 377 ms 94668 KB Output is correct
89 Correct 209 ms 80200 KB Output is correct
90 Correct 309 ms 89816 KB Output is correct
91 Correct 257 ms 79520 KB Output is correct
92 Correct 226 ms 79112 KB Output is correct
93 Correct 301 ms 89592 KB Output is correct
94 Correct 299 ms 89780 KB Output is correct
95 Correct 329 ms 87412 KB Output is correct
96 Correct 286 ms 89820 KB Output is correct
97 Correct 329 ms 89756 KB Output is correct
98 Correct 253 ms 81068 KB Output is correct
99 Correct 169 ms 90512 KB Output is correct
100 Correct 153 ms 82796 KB Output is correct
101 Correct 187 ms 88032 KB Output is correct
102 Correct 215 ms 83856 KB Output is correct

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 53924 KB Output is correct
2 Correct 29 ms 54216 KB Output is correct
3 Correct 30 ms 54212 KB Output is correct
4 Correct 34 ms 54328 KB Output is correct
5 Correct 32 ms 53312 KB Output is correct
6 Correct 28 ms 53324 KB Output is correct
7 Correct 30 ms 54228 KB Output is correct
8 Correct 30 ms 54328 KB Output is correct
9 Correct 30 ms 54320 KB Output is correct
10 Correct 29 ms 54260 KB Output is correct
11 Correct 29 ms 54348 KB Output is correct
12 Correct 30 ms 54332 KB Output is correct
13 Correct 27 ms 54336 KB Output is correct
14 Correct 28 ms 54364 KB Output is correct
15 Correct 32 ms 54268 KB Output is correct
16 Correct 34 ms 54332 KB Output is correct
17 Correct 31 ms 54016 KB Output is correct
18 Correct 31 ms 54340 KB Output is correct
19 Correct 29 ms 54028 KB Output is correct
20 Correct 29 ms 54140 KB Output is correct
21 Correct 30 ms 54220 KB Output is correct
22 Correct 29 ms 54232 KB Output is correct
23 Correct 36 ms 54164 KB Output is correct
24 Correct 32 ms 54452 KB Output is correct
25 Correct 31 ms 53340 KB Output is correct
26 Correct 27 ms 53336 KB Output is correct
27 Correct 30 ms 54328 KB Output is correct
28 Correct 30 ms 54316 KB Output is correct
29 Correct 30 ms 54264 KB Output is correct
30 Correct 30 ms 54308 KB Output is correct
31 Correct 30 ms 54344 KB Output is correct
32 Correct 31 ms 54244 KB Output is correct
33 Correct 28 ms 54276 KB Output is correct
34 Correct 28 ms 54468 KB Output is correct
35 Correct 30 ms 54120 KB Output is correct
36 Correct 31 ms 54296 KB Output is correct
37 Correct 28 ms 53924 KB Output is correct
38 Correct 31 ms 54100 KB Output is correct
39 Correct 185 ms 76948 KB Output is correct
40 Correct 196 ms 78396 KB Output is correct
41 Correct 198 ms 78148 KB Output is correct
42 Correct 232 ms 77976 KB Output is correct
43 Correct 210 ms 79784 KB Output is correct
44 Correct 226 ms 79864 KB Output is correct
45 Correct 61 ms 54420 KB Output is correct
46 Correct 82 ms 54996 KB Output is correct
47 Correct 196 ms 77252 KB Output is correct
48 Correct 193 ms 77288 KB Output is correct
49 Correct 229 ms 77360 KB Output is correct
50 Correct 192 ms 77292 KB Output is correct
51 Correct 166 ms 71888 KB Output is correct
52 Correct 198 ms 79152 KB Output is correct
53 Correct 189 ms 74564 KB Output is correct
54 Correct 195 ms 81416 KB Output is correct
55 Runtime error 149 ms 238108 KB Execution killed with signal 11
56 Halted 0 ms 0 KB -