oj.uz

Submission #503172

# Submission time Handle Problem Language Result Execution time Memory
503172 2022-01-07T12:28:56 Z cig32 Food Court (JOI21_foodcourt) C++17
89 / 100
 1000 ms 179564 KB 
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
#define int long long
 
const int MAXN = 2.5e5 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
    int u = uniform_int_distribution<int>(x, y)(rng);
    return u;
}
int bm(int b, int p) { // bigmod
    if(p==0) return 1;
    int r = bm(b, p/2);
    if(p&1) return (((r*r) % MOD) * b) % MOD;
    return (r*r) % MOD;
}
int N, M, Q;
 
struct segtree_beats {
    bool cmp(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;
    int lsto[q.size()], rsto[q.size()];
    for(int i=0; i<q.size(); i++) {
        int x = q[i];
        lsto[i] = 0, rsto[i] = (w[x].size() ? w[x].size() - 1 : 0);
    }
    while(lb < rb) { // log n
        int mid = (lb+rb) >> 1;
        int tot = 0;
        int res[q.size()];
        for(int i=0; i<q.size(); i++) { // log n 
            int x = q[i];
            if(w[x].empty()) continue;
            int lb2 = lsto[i], rb2 = rsto[i];
            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];
            }
            res[i] = lb2;
        }
        if(tot >= b) {
            rb = mid;
            for(int i=0; i<q.size(); i++) {
                rsto[i] = res[i];
            }
        }
        else {
            lb = mid + 1;
            for(int i=0; i<q.size(); i++) {
                lsto[i] = res[i];
            }
        }
    }
    for(int x: q) {
        if(w[x].empty()) continue;
        int lb2 = 0, rb2 = w[x].size() - 1;
        while(lb2 < rb2) { // log n
            int mid2 = (lb2 + rb2 + 1) >> 1;
            if(v[x][mid2].first <= lb) {
                lb2 = mid2;
            }
            else {
                rb2 = mid2 - 1;
            }
        }
        if(v[x][lb2].first == lb) {
            return v[x][lb2].second.first;
        }
    }
}

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

Compilation message

foodcourt.cpp: In member function 'void segtree_beats::pushup(long long int)':
foodcourt.cpp:86:19: warning: unused variable 'max1' [-Wunused-variable]
   86 |         long long max1, max2, maxc;
      |                   ^~~~
foodcourt.cpp:86:25: warning: unused variable 'max2' [-Wunused-variable]
   86 |         long long max1, max2, maxc;
      |                         ^~~~
foodcourt.cpp:86:31: warning: unused variable 'maxc' [-Wunused-variable]
   86 |         long long max1, max2, maxc;
      |                               ^~~~
foodcourt.cpp:87:19: warning: unused variable 'min1' [-Wunused-variable]
   87 |         long long min1, min2, minc;
      |                   ^~~~
foodcourt.cpp:87:25: warning: unused variable 'min2' [-Wunused-variable]
   87 |         long long min1, min2, minc;
      |                         ^~~~
foodcourt.cpp:87:31: warning: unused variable 'minc' [-Wunused-variable]
   87 |         long long min1, min2, minc;
      |                               ^~~~
foodcourt.cpp:88:19: warning: unused variable 'lazy' [-Wunused-variable]
   88 |         long long lazy, sum;
      |                   ^~~~
foodcourt.cpp:88:25: warning: unused variable 'sum' [-Wunused-variable]
   88 |         long long lazy, sum;
      |                         ^~~
foodcourt.cpp:89:19: warning: unused variable 'l' [-Wunused-variable]
   89 |         long long l, r;
      |                   ^
foodcourt.cpp:89:22: warning: unused variable 'r' [-Wunused-variable]
   89 |         long long l, r;
      |                      ^
foodcourt.cpp: In function 'long long int service(long long int, long long int)':
foodcourt.cpp:306:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  306 |     for(int i=0; i<q.size(); i++) {
      |                  ~^~~~~~~~~
foodcourt.cpp:314:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  314 |         for(int i=0; i<q.size(); i++) { // log n
      |                      ~^~~~~~~~~
foodcourt.cpp:334:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  334 |             for(int i=0; i<q.size(); i++) {
      |                          ~^~~~~~~~~
foodcourt.cpp:340:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  340 |             for(int i=0; i<q.size(); i++) {
      |                          ~^~~~~~~~~
foodcourt.cpp:294:17: warning: control reaches end of non-void function [-Wreturn-type]
  294 |     vector<int> q;
      |                 ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 53944 KB Output is correct
2 Correct 35 ms 54292 KB Output is correct
3 Correct 35 ms 54212 KB Output is correct
4 Correct 34 ms 54380 KB Output is correct
5 Correct 34 ms 53324 KB Output is correct
6 Correct 30 ms 53296 KB Output is correct
7 Correct 38 ms 54408 KB Output is correct
8 Correct 34 ms 54296 KB Output is correct
9 Correct 35 ms 54332 KB Output is correct
10 Correct 34 ms 54272 KB Output is correct
11 Correct 36 ms 54364 KB Output is correct
12 Correct 37 ms 54344 KB Output is correct
13 Correct 35 ms 54340 KB Output is correct
14 Correct 36 ms 54404 KB Output is correct
15 Correct 35 ms 54192 KB Output is correct
16 Correct 36 ms 54340 KB Output is correct
17 Correct 37 ms 54092 KB Output is correct
18 Correct 35 ms 54348 KB Output is correct
19 Correct 34 ms 54004 KB Output is correct
20 Correct 34 ms 54240 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 53944 KB Output is correct
2 Correct 35 ms 54292 KB Output is correct
3 Correct 35 ms 54212 KB Output is correct
4 Correct 34 ms 54380 KB Output is correct
5 Correct 34 ms 53324 KB Output is correct
6 Correct 30 ms 53296 KB Output is correct
7 Correct 38 ms 54408 KB Output is correct
8 Correct 34 ms 54296 KB Output is correct
9 Correct 35 ms 54332 KB Output is correct
10 Correct 34 ms 54272 KB Output is correct
11 Correct 36 ms 54364 KB Output is correct
12 Correct 37 ms 54344 KB Output is correct
13 Correct 35 ms 54340 KB Output is correct
14 Correct 36 ms 54404 KB Output is correct
15 Correct 35 ms 54192 KB Output is correct
16 Correct 36 ms 54340 KB Output is correct
17 Correct 37 ms 54092 KB Output is correct
18 Correct 35 ms 54348 KB Output is correct
19 Correct 34 ms 54004 KB Output is correct
20 Correct 34 ms 54240 KB Output is correct
21 Correct 35 ms 54212 KB Output is correct
22 Correct 35 ms 54212 KB Output is correct
23 Correct 34 ms 54164 KB Output is correct
24 Correct 39 ms 54464 KB Output is correct
25 Correct 32 ms 53316 KB Output is correct
26 Correct 34 ms 53488 KB Output is correct
27 Correct 35 ms 54268 KB Output is correct
28 Correct 34 ms 54288 KB Output is correct
29 Correct 35 ms 54364 KB Output is correct
30 Correct 34 ms 54332 KB Output is correct
31 Correct 34 ms 54340 KB Output is correct
32 Correct 36 ms 54348 KB Output is correct
33 Correct 32 ms 54340 KB Output is correct
34 Correct 33 ms 54476 KB Output is correct
35 Correct 35 ms 54340 KB Output is correct
36 Correct 34 ms 54424 KB Output is correct
37 Correct 33 ms 53968 KB Output is correct
38 Correct 36 ms 54348 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 77908 KB Output is correct
2 Correct 200 ms 79328 KB Output is correct
3 Correct 211 ms 78944 KB Output is correct
4 Correct 196 ms 78868 KB Output is correct
5 Correct 213 ms 80700 KB Output is correct
6 Correct 211 ms 80712 KB Output is correct
7 Correct 58 ms 55048 KB Output is correct
8 Correct 62 ms 55764 KB Output is correct
9 Correct 180 ms 78132 KB Output is correct
10 Correct 199 ms 78352 KB Output is correct
11 Correct 194 ms 78276 KB Output is correct
12 Correct 192 ms 78200 KB Output is correct
13 Correct 170 ms 72768 KB Output is correct
14 Correct 196 ms 80064 KB Output is correct
15 Correct 191 ms 75460 KB Output is correct
16 Correct 205 ms 82316 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 119656 KB Output is correct
2 Correct 447 ms 110288 KB Output is correct
3 Correct 499 ms 127728 KB Output is correct
4 Correct 362 ms 126916 KB Output is correct
5 Correct 348 ms 107972 KB Output is correct
6 Correct 479 ms 127520 KB Output is correct
7 Correct 110 ms 49344 KB Output is correct
8 Correct 101 ms 49316 KB Output is correct
9 Correct 400 ms 127516 KB Output is correct
10 Correct 408 ms 127556 KB Output is correct
11 Correct 519 ms 127408 KB Output is correct
12 Correct 474 ms 127424 KB Output is correct
13 Correct 526 ms 127476 KB Output is correct
14 Correct 518 ms 127288 KB Output is correct
15 Correct 597 ms 127248 KB Output is correct
16 Correct 586 ms 127036 KB Output is correct
17 Correct 568 ms 127128 KB Output is correct
18 Correct 512 ms 126784 KB Output is correct
19 Correct 515 ms 126788 KB Output is correct
20 Correct 531 ms 126788 KB Output is correct
21 Correct 569 ms 126868 KB Output is correct
22 Correct 554 ms 126984 KB Output is correct
23 Correct 534 ms 126776 KB Output is correct
24 Correct 553 ms 126788 KB Output is correct
25 Correct 375 ms 108972 KB Output is correct
26 Correct 372 ms 126784 KB Output is correct
27 Correct 439 ms 126660 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 53944 KB Output is correct
2 Correct 35 ms 54292 KB Output is correct
3 Correct 35 ms 54212 KB Output is correct
4 Correct 34 ms 54380 KB Output is correct
5 Correct 34 ms 53324 KB Output is correct
6 Correct 30 ms 53296 KB Output is correct
7 Correct 38 ms 54408 KB Output is correct
8 Correct 34 ms 54296 KB Output is correct
9 Correct 35 ms 54332 KB Output is correct
10 Correct 34 ms 54272 KB Output is correct
11 Correct 36 ms 54364 KB Output is correct
12 Correct 37 ms 54344 KB Output is correct
13 Correct 35 ms 54340 KB Output is correct
14 Correct 36 ms 54404 KB Output is correct
15 Correct 35 ms 54192 KB Output is correct
16 Correct 36 ms 54340 KB Output is correct
17 Correct 37 ms 54092 KB Output is correct
18 Correct 35 ms 54348 KB Output is correct
19 Correct 34 ms 54004 KB Output is correct
20 Correct 34 ms 54240 KB Output is correct
21 Correct 190 ms 77908 KB Output is correct
22 Correct 200 ms 79328 KB Output is correct
23 Correct 211 ms 78944 KB Output is correct
24 Correct 196 ms 78868 KB Output is correct
25 Correct 213 ms 80700 KB Output is correct
26 Correct 211 ms 80712 KB Output is correct
27 Correct 58 ms 55048 KB Output is correct
28 Correct 62 ms 55764 KB Output is correct
29 Correct 180 ms 78132 KB Output is correct
30 Correct 199 ms 78352 KB Output is correct
31 Correct 194 ms 78276 KB Output is correct
32 Correct 192 ms 78200 KB Output is correct
33 Correct 170 ms 72768 KB Output is correct
34 Correct 196 ms 80064 KB Output is correct
35 Correct 191 ms 75460 KB Output is correct
36 Correct 205 ms 82316 KB Output is correct
37 Correct 268 ms 85004 KB Output is correct
38 Correct 238 ms 89404 KB Output is correct
39 Correct 56 ms 54920 KB Output is correct
40 Correct 63 ms 55632 KB Output is correct
41 Correct 291 ms 90712 KB Output is correct
42 Correct 308 ms 90848 KB Output is correct
43 Correct 297 ms 90592 KB Output is correct
44 Correct 299 ms 90672 KB Output is correct
45 Correct 283 ms 90744 KB Output is correct
46 Correct 303 ms 90872 KB Output is correct
47 Correct 140 ms 91316 KB Output is correct
48 Correct 173 ms 88936 KB Output is correct
49 Correct 220 ms 79700 KB Output is correct
50 Correct 280 ms 88520 KB Output is correct
51 Correct 317 ms 91396 KB Output is correct
52 Correct 328 ms 91312 KB Output is correct
53 Correct 170 ms 78020 KB Output is correct
54 Correct 203 ms 82604 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 92368 KB Output is correct
2 Correct 409 ms 91108 KB Output is correct
3 Correct 402 ms 95372 KB Output is correct
4 Correct 269 ms 88816 KB Output is correct
5 Correct 337 ms 92732 KB Output is correct
6 Correct 387 ms 96028 KB Output is correct
7 Correct 87 ms 55744 KB Output is correct
8 Correct 82 ms 56212 KB Output is correct
9 Correct 186 ms 98472 KB Output is correct
10 Correct 154 ms 89156 KB Output is correct
11 Correct 203 ms 95612 KB Output is correct
12 Correct 213 ms 95576 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 53944 KB Output is correct
2 Correct 35 ms 54292 KB Output is correct
3 Correct 35 ms 54212 KB Output is correct
4 Correct 34 ms 54380 KB Output is correct
5 Correct 34 ms 53324 KB Output is correct
6 Correct 30 ms 53296 KB Output is correct
7 Correct 38 ms 54408 KB Output is correct
8 Correct 34 ms 54296 KB Output is correct
9 Correct 35 ms 54332 KB Output is correct
10 Correct 34 ms 54272 KB Output is correct
11 Correct 36 ms 54364 KB Output is correct
12 Correct 37 ms 54344 KB Output is correct
13 Correct 35 ms 54340 KB Output is correct
14 Correct 36 ms 54404 KB Output is correct
15 Correct 35 ms 54192 KB Output is correct
16 Correct 36 ms 54340 KB Output is correct
17 Correct 37 ms 54092 KB Output is correct
18 Correct 35 ms 54348 KB Output is correct
19 Correct 34 ms 54004 KB Output is correct
20 Correct 34 ms 54240 KB Output is correct
21 Correct 35 ms 54212 KB Output is correct
22 Correct 35 ms 54212 KB Output is correct
23 Correct 34 ms 54164 KB Output is correct
24 Correct 39 ms 54464 KB Output is correct
25 Correct 32 ms 53316 KB Output is correct
26 Correct 34 ms 53488 KB Output is correct
27 Correct 35 ms 54268 KB Output is correct
28 Correct 34 ms 54288 KB Output is correct
29 Correct 35 ms 54364 KB Output is correct
30 Correct 34 ms 54332 KB Output is correct
31 Correct 34 ms 54340 KB Output is correct
32 Correct 36 ms 54348 KB Output is correct
33 Correct 32 ms 54340 KB Output is correct
34 Correct 33 ms 54476 KB Output is correct
35 Correct 35 ms 54340 KB Output is correct
36 Correct 34 ms 54424 KB Output is correct
37 Correct 33 ms 53968 KB Output is correct
38 Correct 36 ms 54348 KB Output is correct
39 Correct 190 ms 77908 KB Output is correct
40 Correct 200 ms 79328 KB Output is correct
41 Correct 211 ms 78944 KB Output is correct
42 Correct 196 ms 78868 KB Output is correct
43 Correct 213 ms 80700 KB Output is correct
44 Correct 211 ms 80712 KB Output is correct
45 Correct 58 ms 55048 KB Output is correct
46 Correct 62 ms 55764 KB Output is correct
47 Correct 180 ms 78132 KB Output is correct
48 Correct 199 ms 78352 KB Output is correct
49 Correct 194 ms 78276 KB Output is correct
50 Correct 192 ms 78200 KB Output is correct
51 Correct 170 ms 72768 KB Output is correct
52 Correct 196 ms 80064 KB Output is correct
53 Correct 191 ms 75460 KB Output is correct
54 Correct 205 ms 82316 KB Output is correct
55 Correct 268 ms 85004 KB Output is correct
56 Correct 238 ms 89404 KB Output is correct
57 Correct 56 ms 54920 KB Output is correct
58 Correct 63 ms 55632 KB Output is correct
59 Correct 291 ms 90712 KB Output is correct
60 Correct 308 ms 90848 KB Output is correct
61 Correct 297 ms 90592 KB Output is correct
62 Correct 299 ms 90672 KB Output is correct
63 Correct 283 ms 90744 KB Output is correct
64 Correct 303 ms 90872 KB Output is correct
65 Correct 140 ms 91316 KB Output is correct
66 Correct 173 ms 88936 KB Output is correct
67 Correct 220 ms 79700 KB Output is correct
68 Correct 280 ms 88520 KB Output is correct
69 Correct 317 ms 91396 KB Output is correct
70 Correct 328 ms 91312 KB Output is correct
71 Correct 170 ms 78020 KB Output is correct
72 Correct 203 ms 82604 KB Output is correct
73 Correct 351 ms 92368 KB Output is correct
74 Correct 409 ms 91108 KB Output is correct
75 Correct 402 ms 95372 KB Output is correct
76 Correct 269 ms 88816 KB Output is correct
77 Correct 337 ms 92732 KB Output is correct
78 Correct 387 ms 96028 KB Output is correct
79 Correct 87 ms 55744 KB Output is correct
80 Correct 82 ms 56212 KB Output is correct
81 Correct 186 ms 98472 KB Output is correct
82 Correct 154 ms 89156 KB Output is correct
83 Correct 203 ms 95612 KB Output is correct
84 Correct 213 ms 95576 KB Output is correct
85 Correct 281 ms 83104 KB Output is correct
86 Correct 303 ms 89192 KB Output is correct
87 Correct 269 ms 92208 KB Output is correct
88 Correct 324 ms 96132 KB Output is correct
89 Correct 201 ms 81032 KB Output is correct
90 Correct 285 ms 91128 KB Output is correct
91 Correct 239 ms 80860 KB Output is correct
92 Correct 221 ms 80300 KB Output is correct
93 Correct 288 ms 91048 KB Output is correct
94 Correct 295 ms 91112 KB Output is correct
95 Correct 278 ms 88840 KB Output is correct
96 Correct 286 ms 91472 KB Output is correct
97 Correct 311 ms 91096 KB Output is correct
98 Correct 247 ms 82652 KB Output is correct
99 Correct 149 ms 91824 KB Output is correct
100 Correct 158 ms 84096 KB Output is correct
101 Correct 182 ms 89420 KB Output is correct
102 Correct 209 ms 85272 KB Output is correct

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 53944 KB Output is correct
2 Correct 35 ms 54292 KB Output is correct
3 Correct 35 ms 54212 KB Output is correct
4 Correct 34 ms 54380 KB Output is correct
5 Correct 34 ms 53324 KB Output is correct
6 Correct 30 ms 53296 KB Output is correct
7 Correct 38 ms 54408 KB Output is correct
8 Correct 34 ms 54296 KB Output is correct
9 Correct 35 ms 54332 KB Output is correct
10 Correct 34 ms 54272 KB Output is correct
11 Correct 36 ms 54364 KB Output is correct
12 Correct 37 ms 54344 KB Output is correct
13 Correct 35 ms 54340 KB Output is correct
14 Correct 36 ms 54404 KB Output is correct
15 Correct 35 ms 54192 KB Output is correct
16 Correct 36 ms 54340 KB Output is correct
17 Correct 37 ms 54092 KB Output is correct
18 Correct 35 ms 54348 KB Output is correct
19 Correct 34 ms 54004 KB Output is correct
20 Correct 34 ms 54240 KB Output is correct
21 Correct 35 ms 54212 KB Output is correct
22 Correct 35 ms 54212 KB Output is correct
23 Correct 34 ms 54164 KB Output is correct
24 Correct 39 ms 54464 KB Output is correct
25 Correct 32 ms 53316 KB Output is correct
26 Correct 34 ms 53488 KB Output is correct
27 Correct 35 ms 54268 KB Output is correct
28 Correct 34 ms 54288 KB Output is correct
29 Correct 35 ms 54364 KB Output is correct
30 Correct 34 ms 54332 KB Output is correct
31 Correct 34 ms 54340 KB Output is correct
32 Correct 36 ms 54348 KB Output is correct
33 Correct 32 ms 54340 KB Output is correct
34 Correct 33 ms 54476 KB Output is correct
35 Correct 35 ms 54340 KB Output is correct
36 Correct 34 ms 54424 KB Output is correct
37 Correct 33 ms 53968 KB Output is correct
38 Correct 36 ms 54348 KB Output is correct
39 Correct 190 ms 77908 KB Output is correct
40 Correct 200 ms 79328 KB Output is correct
41 Correct 211 ms 78944 KB Output is correct
42 Correct 196 ms 78868 KB Output is correct
43 Correct 213 ms 80700 KB Output is correct
44 Correct 211 ms 80712 KB Output is correct
45 Correct 58 ms 55048 KB Output is correct
46 Correct 62 ms 55764 KB Output is correct
47 Correct 180 ms 78132 KB Output is correct
48 Correct 199 ms 78352 KB Output is correct
49 Correct 194 ms 78276 KB Output is correct
50 Correct 192 ms 78200 KB Output is correct
51 Correct 170 ms 72768 KB Output is correct
52 Correct 196 ms 80064 KB Output is correct
53 Correct 191 ms 75460 KB Output is correct
54 Correct 205 ms 82316 KB Output is correct
55 Correct 503 ms 119656 KB Output is correct
56 Correct 447 ms 110288 KB Output is correct
57 Correct 499 ms 127728 KB Output is correct
58 Correct 362 ms 126916 KB Output is correct
59 Correct 348 ms 107972 KB Output is correct
60 Correct 479 ms 127520 KB Output is correct
61 Correct 110 ms 49344 KB Output is correct
62 Correct 101 ms 49316 KB Output is correct
63 Correct 400 ms 127516 KB Output is correct
64 Correct 408 ms 127556 KB Output is correct
65 Correct 519 ms 127408 KB Output is correct
66 Correct 474 ms 127424 KB Output is correct
67 Correct 526 ms 127476 KB Output is correct
68 Correct 518 ms 127288 KB Output is correct
69 Correct 597 ms 127248 KB Output is correct
70 Correct 586 ms 127036 KB Output is correct
71 Correct 568 ms 127128 KB Output is correct
72 Correct 512 ms 126784 KB Output is correct
73 Correct 515 ms 126788 KB Output is correct
74 Correct 531 ms 126788 KB Output is correct
75 Correct 569 ms 126868 KB Output is correct
76 Correct 554 ms 126984 KB Output is correct
77 Correct 534 ms 126776 KB Output is correct
78 Correct 553 ms 126788 KB Output is correct
79 Correct 375 ms 108972 KB Output is correct
80 Correct 372 ms 126784 KB Output is correct
81 Correct 439 ms 126660 KB Output is correct
82 Correct 268 ms 85004 KB Output is correct
83 Correct 238 ms 89404 KB Output is correct
84 Correct 56 ms 54920 KB Output is correct
85 Correct 63 ms 55632 KB Output is correct
86 Correct 291 ms 90712 KB Output is correct
87 Correct 308 ms 90848 KB Output is correct
88 Correct 297 ms 90592 KB Output is correct
89 Correct 299 ms 90672 KB Output is correct
90 Correct 283 ms 90744 KB Output is correct
91 Correct 303 ms 90872 KB Output is correct
92 Correct 140 ms 91316 KB Output is correct
93 Correct 173 ms 88936 KB Output is correct
94 Correct 220 ms 79700 KB Output is correct
95 Correct 280 ms 88520 KB Output is correct
96 Correct 317 ms 91396 KB Output is correct
97 Correct 328 ms 91312 KB Output is correct
98 Correct 170 ms 78020 KB Output is correct
99 Correct 203 ms 82604 KB Output is correct
100 Correct 351 ms 92368 KB Output is correct
101 Correct 409 ms 91108 KB Output is correct
102 Correct 402 ms 95372 KB Output is correct
103 Correct 269 ms 88816 KB Output is correct
104 Correct 337 ms 92732 KB Output is correct
105 Correct 387 ms 96028 KB Output is correct
106 Correct 87 ms 55744 KB Output is correct
107 Correct 82 ms 56212 KB Output is correct
108 Correct 186 ms 98472 KB Output is correct
109 Correct 154 ms 89156 KB Output is correct
110 Correct 203 ms 95612 KB Output is correct
111 Correct 213 ms 95576 KB Output is correct
112 Correct 281 ms 83104 KB Output is correct
113 Correct 303 ms 89192 KB Output is correct
114 Correct 269 ms 92208 KB Output is correct
115 Correct 324 ms 96132 KB Output is correct
116 Correct 201 ms 81032 KB Output is correct
117 Correct 285 ms 91128 KB Output is correct
118 Correct 239 ms 80860 KB Output is correct
119 Correct 221 ms 80300 KB Output is correct
120 Correct 288 ms 91048 KB Output is correct
121 Correct 295 ms 91112 KB Output is correct
122 Correct 278 ms 88840 KB Output is correct
123 Correct 286 ms 91472 KB Output is correct
124 Correct 311 ms 91096 KB Output is correct
125 Correct 247 ms 82652 KB Output is correct
126 Correct 149 ms 91824 KB Output is correct
127 Correct 158 ms 84096 KB Output is correct
128 Correct 182 ms 89420 KB Output is correct
129 Correct 209 ms 85272 KB Output is correct
130 Execution timed out 1098 ms 179564 KB Time limit exceeded
131 Halted 0 ms 0 KB -