oj.uz

Submission #712207

# Submission time Handle Problem Language Result Execution time Memory
712207 2023-03-18T11:42:04 Z Thienu Progression (NOI20_progression) C++17
100 / 100
 2906 ms 117672 KB 
#include <bits/stdc++.h>

using namespace std;

#define u_map unordered_map
#define u_set unordered_set
#define u_multiset unordered_multiset

using ll = long long;
using vvi = vector<vector<int>>;
using vi = vector<int>;
using vvll = vector<vector<long long>>;
using vll = vector<long long>;
using vd = vector<double>;
using vvd = vector<vector<double>>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;

template<typename C> struct rge{C l, r;};
template<typename C> rge<C> range(C i, C j) { return rge<C>{i, j}; }
template<typename C> ostream& operator<<(ostream &os, rge<C> &r) { os << '{'; for(auto it = r.l; it != r.r; it++) os << "," + (it == r.l) << *it; os << '}'; return os; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '{' << p.first << "," << p.second << '}'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ","; return os << '}'; }
void dbg_out() { cerr << ']' << endl; }
template<typename A> void dbg_out(A H) { cerr << H; dbg_out(); }
template<typename A, typename B, typename... C> void dbg_out(A H, B G, C... T) { cerr << H << ","; dbg_out(G, T...); }
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "] = [", dbg_out(__VA_ARGS__)
#else
#define debug(...)
#endif


namespace segtree {
    /**
     * Range set
     * Range query: longest sequence of same numbers
    */
    const ll INF = 4'234'567'890'123'456'789;
    
    struct QueryOut {
        int ans;
        ll lnum, rnum;
        int llen, rlen;
        bool same;
        int len;
        QueryOut(int ans, ll lnum, int llen, ll rnum, int rlen, bool same, int len) : ans(ans), lnum(lnum), llen(llen), rnum(rnum), rlen(rlen), same(same), len(len) {}
        QueryOut() {len = 0;}
    };

    QueryOut combine(QueryOut x, QueryOut y) {
        if(x.len == 0) return y;
        if(y.len == 0) return x;
        int new_ans = max({x.ans, y.ans});
        if(x.rnum == y.lnum) new_ans = max(new_ans, x.rlen + y.llen);
        return QueryOut(
            new_ans,
            x.lnum,
            (x.same && x.rnum == y.lnum) ? x.llen + y.llen : x.llen,
            y.rnum,
            (y.same && x.rnum == y.lnum) ? y.rlen + x.rlen : y.rlen,
            x.same && y.same && x.rnum == y.lnum,
            x.len + y.len
        );
    }

    struct Node {
        Node *l, *r;
        int lo, hi;

        ll mset = -INF;
        ll madd = 0;

        QueryOut qout;

        Node(int lo, int hi, vll &v): lo(lo), hi(hi) {
            if(lo + 1 == hi){
                // same = true;
                // lnum = rnum = v[lo];
                // llen = rlen = 1;
                qout = QueryOut(1, v[lo], 1, v[lo], 1, true, 1);
            } else {
                int mid = lo + (hi - lo) / 2;
                l = new Node(lo, mid, v);
                r = new Node(mid, hi, v);
                update();
            }
        }

        void update() {
            qout = combine(l->qout, r->qout);
        }

        void push() {
            if(mset != -INF) {
                l->set(lo, hi, mset);
                r->set(lo, hi, mset);
                mset = -INF;
            } else if(madd) {
                l->add(lo, hi, madd);
                r->add(lo, hi, madd);
                madd = 0;
            }
        }

        void set(int left, int right, ll val) {
            assert(val != -INF);
            if(right <= lo || hi <= left) return;
            if(left <= lo && hi <= right) {
                mset = val;
                madd = 0;
                qout = QueryOut(hi - lo, val, hi - lo, val, hi - lo, true, hi - lo);
            } else {
                push();
                l->set(left, right, val);
                r->set(left, right, val);
                update();
            }
        }

        void add(int left, int right, ll val) {
            if(right <= lo || hi <= left) return;
            if(left <= lo && hi <= right) {
                if(mset != -INF) {
                    mset += val;
                } else {
                    madd += val;
                }
                qout = QueryOut(qout.ans, qout.lnum + val, qout.llen, qout.rnum + val, qout.rlen, qout.same, hi - lo);
            } else {
                push();
                l->add(left, right, val);
                r->add(left, right, val);
                update();
            }
        }

        QueryOut query(int left, int right) {
            if(right <= lo || hi <= left) return QueryOut(-1, -1, -1, -1, -1, false, 0); // dummy
            if(left <= lo && hi <= right){
                return qout;
            } else {
                push();
                return combine(l->query(left, right), r->query(left, right));
            }
        }
    };
}

namespace lichao {
    const ll INF = 2'000'000'000'000'000'005;

    struct Line{
        ll m, c;
        Line(ll _m, ll _c) : m(_m), c(_c) {}

        ll eval(ll x){
            return m * x + c;
        }

        bool nonzero() {
            return m != 0 || c != 0;
        }
    };
    Line operator+(Line &a, Line &b) { return Line(a.m + b.m, a.c + b.c); }

    ostream& operator<<(ostream &os, Line x) { return os << "{m=" << x.m << ", c=" << x.c << '}'; }

    struct Node {
        Node *l = 0, *r = 0;
        int lo, hi; // [lo, hi)
        Line line = Line(0, INF);
        Line madd = Line(0, 0);
        bool mwipe = false;

        Node(int lo, int hi): lo(lo), hi(hi) {}

        void push() {
            assert(lo + 1 < hi);
            if(!l) {
                int mid = lo + (hi - lo) / 2;
                l = new Node(lo, mid);
                r = new Node(mid, hi);
            }
            if(madd.nonzero()) {
                l->add_affine(lo, hi, madd);
                r->add_affine(lo, hi, madd);
                madd = Line(0, 0);
            }
            if(mwipe) {
                l->wipe(lo, hi);
                r->wipe(lo, hi);
                mwipe = false;
            }
        }

        // Reset all lines on [left, right).
        void wipe(int left, int right) {
            if(right <= lo || hi <= left) return;
            if(left <= lo && hi <= right) {
                madd = Line(0, 0);
                mwipe = true;
                line = Line(0, INF);
            } else {
                push();
                l->insert_line(lo, hi, line);
                r->insert_line(lo, hi, line);
                line = Line(0, INF);
                l->wipe(left, right);
                r->wipe(left, right);
            }
        }

        // Insert new_line on [left, right). O(log^2 n) / O(log n) if left=0, right=n.
        void insert_line(int left, int right, Line new_line) {
            if(right <= lo || hi <= left) return;
            if(left <= lo && hi <= right) {
                bool ldiff = line.eval(lo) <= new_line.eval(lo);
                bool rdiff = line.eval(hi - 1) <= new_line.eval(hi - 1);
                if(ldiff && rdiff) return;
                if(!ldiff && !rdiff){
                    line = new_line;
                    return;
                }
                int mid = lo + (hi - lo) / 2;
                bool mdiff = line.eval(mid) <= new_line.eval(mid);
                if(!mdiff){
                    swap(line, new_line);
                }
                push();
                if(ldiff != mdiff){
                    l->insert_line(left, right, new_line);
                } else {
                    r->insert_line(left, right, new_line);
                }
                return;
            }
            push();
            l->insert_line(left, right, new_line);
            r->insert_line(left, right, new_line);
        }

        // Add the value of the line to everything in [left, right). O(log^2 n).
        void add_affine(int left, int right, Line add) {
            if(right <= lo || hi <= left) return;
            if(left <= lo && hi <= right) {
                line = line + add;
                madd = madd + add;
            } else {
                push();
                l->insert_line(lo, hi, line);
                r->insert_line(lo, hi, line);
                line = Line(0, INF);
                l->add_affine(left, right, add);
                r->add_affine(left, right, add);
            }
        }

        // Get min at x. O(log n).
        ll query(int x){
            assert(lo <= x && x < hi);
            if(!l){
                return line.eval(x);
            }
            push();
            ll rec;
            int mid = lo + (hi - lo) / 2;
            if(x >= mid) {
                rec = r->query(x);
            } else {
                rec = l->query(x);
            }
            return min(line.eval(x), rec);
        }

        void print_state(string prefix=""){
            #ifdef DEBUG
            cerr << prefix << "Node" << endl;
            cerr << prefix << lo << ' ' << hi << endl;
            cerr << prefix << "line: " << line << " madd: " << madd << " mwipe: " << mwipe << endl;
            if(l) {
                cerr << prefix << "Left:" << endl;
                l->print_state(prefix + " | ");
                cerr << prefix << "Right:" << endl;
                r->print_state(prefix + " | ");
            }
            #else
            #endif
        }
    };
}

void solve(){
    int n, q;
    cin >> n >> q;
    vi v(n);
    for(int i = 0; i < n; i++) cin >> v[i];
    vll diff(n-1);
    for(int i = 0; i < n-1; i++) {
        diff[i] = v[i+1] - v[i];
    }

    // breaks at n=1 for some reason lmao
    if(n == 1){
        while(q--){
            int t;
            cin >> t;
            if(t == 1 || t == 2){
                int l, r; ll s, c;
                cin >> l >> r >> s >> c;
            } else {
                int l, r;
                cin >> l >> r;
                cout << 1 << endl;
            }
        }
        return;
    }
    
    lichao::Node* lct = new lichao::Node(0, n);
    for(int i = 0; i < n; i++){
        lct->insert_line(i, i+1, lichao::Line(0, v[i]));
    }
    segtree::Node* st = new segtree::Node(0, n-1, diff);
    
    while(q--){
        int t;
        cin >> t;
        if(t == 1){
            int l, r; ll s, c;
            cin >> l >> r >> s >> c;
            l--;
            lichao::Line ln = lichao::Line(c, s - c * l);
            debug("add", ln, l, r);
            lct->add_affine(l, r, ln);
            st->add(l, r, c);
            // debug(lct->query(r) - lct->query(r-1));
            if(l > 0) {
                st->set(l-1, l, lct->query(l) - lct->query(l-1));
            }
            if(r < n) {
                st->set(r-1, r, lct->query(r) - lct->query(r-1));
            }
            lct->print_state();
        }else if(t == 2){
            int l, r; ll s, c;
            cin >> l >> r >> s >> c;
            l--;
            lichao::Line ln = lichao::Line(c, s - c * l);
            debug("replace", ln, l, r);
            lct->wipe(l, r);
            debug("wiping done");
            lct->print_state();
            lct->insert_line(l, r, ln);
            st->set(l, r, c);
            if(l > 0) {
                st->set(l-1, l, lct->query(l) - lct->query(l-1));
            }
            if(r < n) {
                debug(lct->query(r), lct->query(r-1));
                st->set(r-1, r, lct->query(r) - lct->query(r-1));
            }
            lct->print_state();
        }else{
            int l, r;
            cin >> l >> r;
            l--;
            if(l + 1 == r){
                cout << 1 << endl;
            } else {
                segtree::QueryOut qout = st->query(l, r-1);
                debug(qout.ans, qout.lnum, qout.llen, qout.rnum, qout.rlen, qout.same);
                cout << qout.ans + 1 << endl;
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

Compilation message

Progression.cpp: In constructor 'segtree::QueryOut::QueryOut(int, ll, int, ll, int, bool, int)':
Progression.cpp:44:13: warning: 'segtree::QueryOut::llen' will be initialized after [-Wreorder]
   44 |         int llen, rlen;
      |             ^~~~
Progression.cpp:43:18: warning:   'll segtree::QueryOut::rnum' [-Wreorder]
   43 |         ll lnum, rnum;
      |                  ^~~~
Progression.cpp:47:9: warning:   when initialized here [-Wreorder]
   47 |         QueryOut(int ans, ll lnum, int llen, ll rnum, int rlen, bool same, int len) : ans(ans), lnum(lnum), llen(llen), rnum(rnum), rlen(rlen), same(same), len(len) {}
      |         ^~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 115760 KB Output is correct
2 Correct 228 ms 3484 KB Output is correct
3 Correct 222 ms 3536 KB Output is correct
4 Correct 222 ms 3532 KB Output is correct
5 Correct 230 ms 3556 KB Output is correct
6 Correct 232 ms 3560 KB Output is correct
7 Correct 216 ms 3524 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 392 ms 115828 KB Output is correct
12 Correct 402 ms 115800 KB Output is correct
13 Correct 398 ms 116044 KB Output is correct
14 Correct 442 ms 116052 KB Output is correct
15 Correct 426 ms 115920 KB Output is correct
16 Correct 422 ms 115656 KB Output is correct
17 Correct 382 ms 115736 KB Output is correct
18 Correct 417 ms 115676 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 596 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 4 ms 596 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 3 ms 588 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 4 ms 596 KB Output is correct
13 Correct 5 ms 588 KB Output is correct
14 Correct 4 ms 596 KB Output is correct
15 Correct 5 ms 588 KB Output is correct
16 Correct 4 ms 596 KB Output is correct
17 Correct 4 ms 596 KB Output is correct
18 Correct 4 ms 596 KB Output is correct
19 Correct 2 ms 340 KB Output is correct
20 Correct 2 ms 212 KB Output is correct
21 Correct 2 ms 328 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 912 ms 114376 KB Output is correct
2 Correct 424 ms 3148 KB Output is correct
3 Correct 424 ms 2896 KB Output is correct
4 Correct 432 ms 2888 KB Output is correct
5 Correct 448 ms 3212 KB Output is correct
6 Correct 430 ms 3092 KB Output is correct
7 Correct 428 ms 3112 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 916 ms 112848 KB Output is correct
12 Correct 959 ms 114152 KB Output is correct
13 Correct 1063 ms 112780 KB Output is correct
14 Correct 1103 ms 112780 KB Output is correct
15 Correct 925 ms 114060 KB Output is correct
16 Correct 1010 ms 114780 KB Output is correct
17 Correct 1079 ms 114680 KB Output is correct
18 Correct 1035 ms 114760 KB Output is correct
19 Correct 924 ms 114144 KB Output is correct
20 Correct 901 ms 114108 KB Output is correct
21 Correct 924 ms 114100 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1849 ms 116940 KB Output is correct
2 Correct 383 ms 3536 KB Output is correct
3 Correct 366 ms 3536 KB Output is correct
4 Correct 359 ms 3640 KB Output is correct
5 Correct 384 ms 3584 KB Output is correct
6 Correct 419 ms 3632 KB Output is correct
7 Correct 370 ms 3664 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 1803 ms 113680 KB Output is correct
12 Correct 1794 ms 116984 KB Output is correct
13 Correct 1833 ms 113640 KB Output is correct
14 Correct 1852 ms 113740 KB Output is correct
15 Correct 1983 ms 116948 KB Output is correct
16 Correct 1801 ms 117032 KB Output is correct
17 Correct 1938 ms 117096 KB Output is correct
18 Correct 2145 ms 117172 KB Output is correct
19 Correct 1923 ms 116948 KB Output is correct
20 Correct 1692 ms 116928 KB Output is correct
21 Correct 1835 ms 116912 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 912 ms 114376 KB Output is correct
2 Correct 424 ms 3148 KB Output is correct
3 Correct 424 ms 2896 KB Output is correct
4 Correct 432 ms 2888 KB Output is correct
5 Correct 448 ms 3212 KB Output is correct
6 Correct 430 ms 3092 KB Output is correct
7 Correct 428 ms 3112 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 916 ms 112848 KB Output is correct
12 Correct 959 ms 114152 KB Output is correct
13 Correct 1063 ms 112780 KB Output is correct
14 Correct 1103 ms 112780 KB Output is correct
15 Correct 925 ms 114060 KB Output is correct
16 Correct 1010 ms 114780 KB Output is correct
17 Correct 1079 ms 114680 KB Output is correct
18 Correct 1035 ms 114760 KB Output is correct
19 Correct 924 ms 114144 KB Output is correct
20 Correct 901 ms 114108 KB Output is correct
21 Correct 924 ms 114100 KB Output is correct
22 Correct 2520 ms 116352 KB Output is correct
23 Correct 530 ms 3524 KB Output is correct
24 Correct 505 ms 3424 KB Output is correct
25 Correct 496 ms 3544 KB Output is correct
26 Correct 554 ms 3456 KB Output is correct
27 Correct 535 ms 3508 KB Output is correct
28 Correct 431 ms 3492 KB Output is correct
29 Correct 2 ms 340 KB Output is correct
30 Correct 2 ms 340 KB Output is correct
31 Correct 3 ms 212 KB Output is correct
32 Correct 2157 ms 113620 KB Output is correct
33 Correct 2349 ms 116388 KB Output is correct
34 Correct 2250 ms 113684 KB Output is correct
35 Correct 2334 ms 113688 KB Output is correct
36 Correct 1912 ms 113508 KB Output is correct
37 Correct 1752 ms 113416 KB Output is correct
38 Correct 1697 ms 113532 KB Output is correct
39 Correct 1991 ms 116368 KB Output is correct
40 Correct 1808 ms 116620 KB Output is correct
41 Correct 1949 ms 116612 KB Output is correct
42 Correct 1978 ms 116420 KB Output is correct
43 Correct 1833 ms 116408 KB Output is correct
44 Correct 1882 ms 116612 KB Output is correct
45 Correct 1761 ms 116396 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 115760 KB Output is correct
2 Correct 228 ms 3484 KB Output is correct
3 Correct 222 ms 3536 KB Output is correct
4 Correct 222 ms 3532 KB Output is correct
5 Correct 230 ms 3556 KB Output is correct
6 Correct 232 ms 3560 KB Output is correct
7 Correct 216 ms 3524 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 392 ms 115828 KB Output is correct
12 Correct 402 ms 115800 KB Output is correct
13 Correct 398 ms 116044 KB Output is correct
14 Correct 442 ms 116052 KB Output is correct
15 Correct 426 ms 115920 KB Output is correct
16 Correct 422 ms 115656 KB Output is correct
17 Correct 382 ms 115736 KB Output is correct
18 Correct 417 ms 115676 KB Output is correct
19 Correct 4 ms 596 KB Output is correct
20 Correct 2 ms 332 KB Output is correct
21 Correct 2 ms 212 KB Output is correct
22 Correct 3 ms 340 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 324 KB Output is correct
25 Correct 2 ms 336 KB Output is correct
26 Correct 4 ms 596 KB Output is correct
27 Correct 3 ms 596 KB Output is correct
28 Correct 3 ms 588 KB Output is correct
29 Correct 3 ms 596 KB Output is correct
30 Correct 4 ms 596 KB Output is correct
31 Correct 5 ms 588 KB Output is correct
32 Correct 4 ms 596 KB Output is correct
33 Correct 5 ms 588 KB Output is correct
34 Correct 4 ms 596 KB Output is correct
35 Correct 4 ms 596 KB Output is correct
36 Correct 4 ms 596 KB Output is correct
37 Correct 2 ms 340 KB Output is correct
38 Correct 2 ms 212 KB Output is correct
39 Correct 2 ms 328 KB Output is correct
40 Correct 912 ms 114376 KB Output is correct
41 Correct 424 ms 3148 KB Output is correct
42 Correct 424 ms 2896 KB Output is correct
43 Correct 432 ms 2888 KB Output is correct
44 Correct 448 ms 3212 KB Output is correct
45 Correct 430 ms 3092 KB Output is correct
46 Correct 428 ms 3112 KB Output is correct
47 Correct 2 ms 212 KB Output is correct
48 Correct 2 ms 212 KB Output is correct
49 Correct 2 ms 212 KB Output is correct
50 Correct 916 ms 112848 KB Output is correct
51 Correct 959 ms 114152 KB Output is correct
52 Correct 1063 ms 112780 KB Output is correct
53 Correct 1103 ms 112780 KB Output is correct
54 Correct 925 ms 114060 KB Output is correct
55 Correct 1010 ms 114780 KB Output is correct
56 Correct 1079 ms 114680 KB Output is correct
57 Correct 1035 ms 114760 KB Output is correct
58 Correct 924 ms 114144 KB Output is correct
59 Correct 901 ms 114108 KB Output is correct
60 Correct 924 ms 114100 KB Output is correct
61 Correct 1849 ms 116940 KB Output is correct
62 Correct 383 ms 3536 KB Output is correct
63 Correct 366 ms 3536 KB Output is correct
64 Correct 359 ms 3640 KB Output is correct
65 Correct 384 ms 3584 KB Output is correct
66 Correct 419 ms 3632 KB Output is correct
67 Correct 370 ms 3664 KB Output is correct
68 Correct 1 ms 212 KB Output is correct
69 Correct 2 ms 212 KB Output is correct
70 Correct 2 ms 212 KB Output is correct
71 Correct 1803 ms 113680 KB Output is correct
72 Correct 1794 ms 116984 KB Output is correct
73 Correct 1833 ms 113640 KB Output is correct
74 Correct 1852 ms 113740 KB Output is correct
75 Correct 1983 ms 116948 KB Output is correct
76 Correct 1801 ms 117032 KB Output is correct
77 Correct 1938 ms 117096 KB Output is correct
78 Correct 2145 ms 117172 KB Output is correct
79 Correct 1923 ms 116948 KB Output is correct
80 Correct 1692 ms 116928 KB Output is correct
81 Correct 1835 ms 116912 KB Output is correct
82 Correct 2520 ms 116352 KB Output is correct
83 Correct 530 ms 3524 KB Output is correct
84 Correct 505 ms 3424 KB Output is correct
85 Correct 496 ms 3544 KB Output is correct
86 Correct 554 ms 3456 KB Output is correct
87 Correct 535 ms 3508 KB Output is correct
88 Correct 431 ms 3492 KB Output is correct
89 Correct 2 ms 340 KB Output is correct
90 Correct 2 ms 340 KB Output is correct
91 Correct 3 ms 212 KB Output is correct
92 Correct 2157 ms 113620 KB Output is correct
93 Correct 2349 ms 116388 KB Output is correct
94 Correct 2250 ms 113684 KB Output is correct
95 Correct 2334 ms 113688 KB Output is correct
96 Correct 1912 ms 113508 KB Output is correct
97 Correct 1752 ms 113416 KB Output is correct
98 Correct 1697 ms 113532 KB Output is correct
99 Correct 1991 ms 116368 KB Output is correct
100 Correct 1808 ms 116620 KB Output is correct
101 Correct 1949 ms 116612 KB Output is correct
102 Correct 1978 ms 116420 KB Output is correct
103 Correct 1833 ms 116408 KB Output is correct
104 Correct 1882 ms 116612 KB Output is correct
105 Correct 1761 ms 116396 KB Output is correct
106 Correct 2180 ms 117388 KB Output is correct
107 Correct 387 ms 3660 KB Output is correct
108 Correct 412 ms 3676 KB Output is correct
109 Correct 394 ms 3780 KB Output is correct
110 Correct 2 ms 212 KB Output is correct
111 Correct 2 ms 212 KB Output is correct
112 Correct 1 ms 212 KB Output is correct
113 Correct 2084 ms 116424 KB Output is correct
114 Correct 2050 ms 116532 KB Output is correct
115 Correct 2065 ms 116408 KB Output is correct
116 Correct 2063 ms 116312 KB Output is correct
117 Correct 2382 ms 117404 KB Output is correct
118 Correct 1879 ms 116348 KB Output is correct
119 Correct 2172 ms 116424 KB Output is correct
120 Correct 997 ms 115016 KB Output is correct
121 Correct 973 ms 114904 KB Output is correct
122 Correct 1022 ms 115004 KB Output is correct
123 Correct 896 ms 114316 KB Output is correct
124 Correct 1010 ms 114100 KB Output is correct
125 Correct 859 ms 114124 KB Output is correct
126 Correct 2736 ms 113972 KB Output is correct
127 Correct 2503 ms 114080 KB Output is correct
128 Correct 2906 ms 117384 KB Output is correct
129 Correct 2777 ms 114068 KB Output is correct
130 Correct 1899 ms 114120 KB Output is correct
131 Correct 1730 ms 114148 KB Output is correct
132 Correct 1585 ms 114156 KB Output is correct
133 Correct 2146 ms 117504 KB Output is correct
134 Correct 2128 ms 117432 KB Output is correct
135 Correct 2122 ms 117672 KB Output is correct
136 Correct 398 ms 3684 KB Output is correct
137 Correct 395 ms 3720 KB Output is correct
138 Correct 400 ms 3664 KB Output is correct