oj.uz

답안 #107437

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
107437 2019-04-24T10:14:24 Z lyc 새 집 (APIO18_new_home) C++14
100 / 100
 4925 ms 198256 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

#define int ll

const int MAXN = 3e5+10;
const int MAXK = 3e5+10;
const int MAXQ = 3e5+10;

const int MX_X = 1e8+10;
const int MX_Y = 1e8+10;

// Input Data
struct Store {
    int i, x, t, a, b;
} stores[MAXN];
struct Query {
    int i, l, y, ans;
} queries[MAXQ];

//
struct StoreEvent {
    int x, y, type;
    // type: 0 (open), 1 (close) };
};

vector<StoreEvent> events[MAXK];

struct OpenStore {
    int cnt, negRay, posRay;

    OpenStore(): cnt(1) {}
};

struct Ray {
    int h, xh, xi, a, b;

    Ray(int x1, int x2, int m, int y) {
        a = y; b = -1;
        h = (x2-x1)/2;
        if (m > 0) xi = x1;
        else xi = x2;
        xh = xi + h*m;
    }

    void close(int y) { b = y-1; }
};

struct Seg {
    int s, e, m, v[2];
    Seg *l, *r;
    Seg(int _s, int _e): s(_s), e(_e), m((_s+_e)/2), l(nullptr), r(nullptr) {
        v[0] = v[1] = -MX_X * 2;
        if (s != e) {
            l = new Seg(s, m);
            r = new Seg(m+1, e);
        }
    }

    void update(int x, int y, int val, int t) {
        //cout << "UPDATE " << x << " " << y << " of " << s << " " << e << endl;
        if (y < x) return;

        if (s == x and e == y) v[t] = max(v[t], val);
        else if (y <= m) l->update(x, y, val, t);
        else if (x >  m) r->update(x, y, val, t);
        else l->update(x, m, val, t), r->update(m+1, y, val, t);
    } 

    int query(int x, int t) {
        if (s == e) return v[t];
        else if (x <= m) return max(v[t], l->query(x, t));
        else return max(v[t], r->query(x, t));
    }
} *root;

main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k, q; cin >> n >> k >> q;
    FOR(i,0,n-1){
        stores[i].i = i;
        cin >> stores[i].x >> stores[i].t >> stores[i].a >> stores[i].b;
    }

    vector<int> times;
    FOR(i,0,q-1){
        queries[i].i = i;
        queries[i].ans = -1;
        cin >> queries[i].l >> queries[i].y;

        times.push_back(queries[i].y);
    }

    times.push_back(0);
    times.push_back(MX_Y);
    // Discretize time
    sort(ALL(times));
    times.resize(unique(ALL(times))-times.begin());
    FOR(i,0,n-1){
        stores[i].a = lower_bound(ALL(times), stores[i].a) - times.begin();     // earliest ok
        stores[i].b = upper_bound(ALL(times), stores[i].b) - times.begin() - 1; // last ok
    }
    FOR(i,0,q-1){
        queries[i].y = lower_bound(ALL(times), queries[i].y) - times.begin();   // find its index
    }

    // Construct and sort all the store events by time for each type
    FOR(i,0,n-1){
        if (stores[i].b < stores[i].a) continue;

        events[stores[i].t].push_back({stores[i].x, stores[i].a, 0});
        events[stores[i].t].push_back({stores[i].x, stores[i].b+1, 1});
    }
    FOR(i,1,k){
        sort(ALL(events[i]), [](const StoreEvent &a, const StoreEvent &b) {
                    if (a.y == b.y) return a.type > b.type; // closing first
                    return a.y < b.y;
                });
    }
    //cout << "maybe" << endl;
    //FOR(i,1,k){
    //    for (StoreEvent e : events[i]) {
    //        cout << e.x << " " << e.y << " :: " << e.type << endl;
    //    }
    //    cout << endl;
    //}

    // Build the max function for each type, preserving each ray's time interval
    vector<Ray> negRays, posRays;   // stores all the rays
    FOR(i,1,k){
        map<int, OpenStore> openStores;
        openStores[-MX_X] = OpenStore();
        openStores[2*MX_X]= OpenStore();

        openStores[-MX_X].posRay = (int)posRays.size();
        posRays.push_back( Ray(-MX_X, 2*MX_X, 1, 0) );

        openStores[2*MX_X].negRay = (int)negRays.size();
        negRays.push_back( Ray(-MX_X, 2*MX_X, -1, 0) );
        //cout << "OK " << i << " :: " << negRays.size() << " " << posRays.size() << endl;

        for (StoreEvent e : events[i]) {
            auto it = openStores.lower_bound(e.x);
            //cout << "PROCESS " << e.x << " " << e.y << " type " << e.type << endl;

            //cout << "At time " << e.y << endl;
            //cout << '\t';
            //for (auto x : openStores) { cout << x.fi << " "; } cout << endl;
            if (e.type == 0) { // opening event
                if (it->fi == e.x) {
                    // store already exist. just increment counter
                    ++it->sc.cnt;
                } else {
                    assert(it != openStores.begin());   auto prv = prev(it);
                    assert(it != openStores.end());     auto nxt = it;

                    // no stores open here yet. create one
                    openStores[e.x] =  OpenStore();

                    openStores[e.x].negRay = (int)negRays.size();
                    negRays.push_back( Ray(prv->fi, e.x, -1, e.y) );
                    openStores[e.x].posRay = (int)posRays.size();
                    posRays.push_back( Ray(e.x, nxt->fi, 1, e.y) );

                    negRays[nxt->sc.negRay].close(e.y);
                    //cout << "CLOSE " << e.y << " NEG " << nxt->sc.negRay << endl;
                    nxt->sc.negRay = (int)negRays.size();
                    negRays.push_back( Ray(e.x, nxt->fi, -1, e.y) );

                    posRays[prv->sc.posRay].close(e.y);
                    //cout << "CLOSE " << e.y << " POS " << prv->sc.posRay << endl;
                    prv->sc.posRay = (int)posRays.size();
                    posRays.push_back( Ray(prv->fi, e.x, 1, e.y) );
                }
            } else {
                assert(it->fi == e.x);  // a store should exist
                if (it->sc.cnt > 1) {
                    // won't delete any rays
                    --it->sc.cnt;
                } else {
                    assert(it != openStores.begin());   auto prv = prev(it);
                    assert(next(it) != openStores.end());     auto nxt = next(it);

                    // get rid of the store here
                    negRays[it->sc.negRay].close(e.y);
                    posRays[it->sc.posRay].close(e.y);
                    //cout << "CLOSE " << e.y << " HERE NEG " << it->sc.negRay << endl;
                    //cout << "CLOSE " << e.y << " HERE POS " << it->sc.posRay << endl;

                    openStores.erase(it);

                    negRays[nxt->sc.negRay].close(e.y);
                    //cout << "CLOSE " << e.y << " NEG " << nxt->sc.negRay << endl;
                    nxt->sc.negRay = (int)negRays.size();
                    negRays.push_back( Ray(prv->fi, nxt->fi, -1, e.y) );

                    posRays[prv->sc.posRay].close(e.y);
                    //cout << "CLOSE " << e.y << " POS " << prv->sc.posRay << endl;
                    prv->sc.posRay = (int)posRays.size();
                    posRays.push_back( Ray(prv->fi, nxt->fi, 1, e.y) );
                }
            }
        }

        //cout << "CLOSE " << times.size()-1 << " POS " << openStores[-MX_X].posRay << endl;
        //cout << "CLOSE " << times.size()-1 << " NEG " << openStores[2*MX_X].negRay << endl;
        posRays[openStores[-MX_X].posRay].close((int)times.size()-1);
        negRays[openStores[2*MX_X].negRay].close((int)times.size()-1);
        //cout << openStores.size() << endl;
        //cout << "SHOULD CLOSE UP TO " << negRays.size() << " " << posRays.size() << endl;
    }

    // Now process the queries
    root = new Seg(0, (int)times.size()-1);
    sort(ALL(negRays), [](const Ray &a, const Ray &b) { return a.xh < b.xh; });
    sort(queries, queries+q, [](const Query &a, const Query &b) { return a.l < b.l; });

    //for (Ray r : negRays) {
    //    cout << "neg ray " << r.xh << " " << r.xi << " from time " << r.a << " to " << r.b << endl;
    //}
    //for (Ray r : posRays) {
    //    cout << "pos ray " << r.xh << " " << r.xi << " from time " << r.a << " to " << r.b << endl;
    //}

    auto it = negRays.begin();
    FOR(i,0,q-1){
        while (it != negRays.end() && it->xh <= queries[i].l) {
            if (it->a <= it->b) {
                //cout << "UPDATE TIME " << it->a << " - " << it->b << " by " << it->xi << endl;
                root->update(it->a, it->b, it->xi, 0);
            }
            ++it;
        }
        //cout << "QUERY " << queries[i].y << " RAY " << root->query(queries[i].y, 0) << endl;
        queries[i].ans = root->query(queries[i].y, 0) - queries[i].l;
    }

    sort(ALL(posRays), [](const Ray &a, const Ray &b) { return a.xh > b.xh; });
    sort(queries, queries+q, [](const Query &a, const Query &b) { return a.l > b.l; });

    it = posRays.begin();
    FOR(i,0,q-1){
        while (it != posRays.end() && it->xh >= queries[i].l) {
            if (it->a <= it->b) {
                root->update(it->a, it->b, -it->xi, 1);
            }
            ++it;
        }
        queries[i].ans = max(queries[i].ans, queries[i].l + root->query(queries[i].y, 1));
    }

    sort(queries, queries+q, [](const Query &a, const Query &b) { return a.i < b.i; });
    FOR(i,0,q-1){
        cout << (queries[i].ans < MX_X ? queries[i].ans : -1) << endl;
    }
}

Compilation message

new_home.cpp:92:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 11 ms 7296 KB Output is correct
4 Correct 8 ms 7424 KB Output is correct
5 Correct 11 ms 7552 KB Output is correct
6 Correct 12 ms 7680 KB Output is correct
7 Correct 11 ms 7680 KB Output is correct
8 Correct 13 ms 7680 KB Output is correct
9 Correct 11 ms 7652 KB Output is correct
10 Correct 10 ms 7680 KB Output is correct
11 Correct 10 ms 7680 KB Output is correct
12 Correct 11 ms 7680 KB Output is correct
13 Correct 13 ms 7552 KB Output is correct
14 Correct 10 ms 7640 KB Output is correct
15 Correct 10 ms 7680 KB Output is correct
16 Correct 11 ms 7680 KB Output is correct
17 Correct 12 ms 7652 KB Output is correct
18 Correct 11 ms 7680 KB Output is correct
19 Correct 10 ms 7680 KB Output is correct
20 Correct 10 ms 7680 KB Output is correct
21 Correct 10 ms 7680 KB Output is correct
22 Correct 11 ms 7680 KB Output is correct
23 Correct 10 ms 7680 KB Output is correct
24 Correct 10 ms 7680 KB Output is correct
25 Correct 12 ms 7680 KB Output is correct
26 Correct 12 ms 7600 KB Output is correct
27 Correct 11 ms 7680 KB Output is correct
28 Correct 13 ms 7680 KB Output is correct
29 Correct 11 ms 7680 KB Output is correct
30 Correct 12 ms 7680 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 11 ms 7296 KB Output is correct
4 Correct 8 ms 7424 KB Output is correct
5 Correct 11 ms 7552 KB Output is correct
6 Correct 12 ms 7680 KB Output is correct
7 Correct 11 ms 7680 KB Output is correct
8 Correct 13 ms 7680 KB Output is correct
9 Correct 11 ms 7652 KB Output is correct
10 Correct 10 ms 7680 KB Output is correct
11 Correct 10 ms 7680 KB Output is correct
12 Correct 11 ms 7680 KB Output is correct
13 Correct 13 ms 7552 KB Output is correct
14 Correct 10 ms 7640 KB Output is correct
15 Correct 10 ms 7680 KB Output is correct
16 Correct 11 ms 7680 KB Output is correct
17 Correct 12 ms 7652 KB Output is correct
18 Correct 11 ms 7680 KB Output is correct
19 Correct 10 ms 7680 KB Output is correct
20 Correct 10 ms 7680 KB Output is correct
21 Correct 10 ms 7680 KB Output is correct
22 Correct 11 ms 7680 KB Output is correct
23 Correct 10 ms 7680 KB Output is correct
24 Correct 10 ms 7680 KB Output is correct
25 Correct 12 ms 7680 KB Output is correct
26 Correct 12 ms 7600 KB Output is correct
27 Correct 11 ms 7680 KB Output is correct
28 Correct 13 ms 7680 KB Output is correct
29 Correct 11 ms 7680 KB Output is correct
30 Correct 12 ms 7680 KB Output is correct
31 Correct 744 ms 41680 KB Output is correct
32 Correct 173 ms 16488 KB Output is correct
33 Correct 611 ms 40364 KB Output is correct
34 Correct 607 ms 41656 KB Output is correct
35 Correct 624 ms 40364 KB Output is correct
36 Correct 606 ms 40356 KB Output is correct
37 Correct 459 ms 40300 KB Output is correct
38 Correct 457 ms 39728 KB Output is correct
39 Correct 339 ms 39668 KB Output is correct
40 Correct 396 ms 39732 KB Output is correct
41 Correct 524 ms 40188 KB Output is correct
42 Correct 473 ms 40812 KB Output is correct
43 Correct 154 ms 20092 KB Output is correct
44 Correct 636 ms 40728 KB Output is correct
45 Correct 482 ms 40428 KB Output is correct
46 Correct 393 ms 40080 KB Output is correct
47 Correct 274 ms 39288 KB Output is correct
48 Correct 255 ms 38436 KB Output is correct
49 Correct 275 ms 39568 KB Output is correct
50 Correct 332 ms 40772 KB Output is correct
51 Correct 321 ms 39392 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2420 ms 165988 KB Output is correct
2 Correct 2343 ms 155632 KB Output is correct
3 Correct 2471 ms 184320 KB Output is correct
4 Correct 2333 ms 168696 KB Output is correct
5 Correct 3015 ms 154488 KB Output is correct
6 Correct 2520 ms 155300 KB Output is correct
7 Correct 2650 ms 184320 KB Output is correct
8 Correct 2273 ms 167104 KB Output is correct
9 Correct 1970 ms 163324 KB Output is correct
10 Correct 2266 ms 157428 KB Output is correct
11 Correct 1609 ms 153648 KB Output is correct
12 Correct 1688 ms 157824 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3852 ms 160644 KB Output is correct
2 Correct 693 ms 49684 KB Output is correct
3 Correct 3386 ms 155544 KB Output is correct
4 Correct 3621 ms 182384 KB Output is correct
5 Correct 3373 ms 164372 KB Output is correct
6 Correct 3437 ms 166896 KB Output is correct
7 Correct 3729 ms 154568 KB Output is correct
8 Correct 3399 ms 155396 KB Output is correct
9 Correct 3256 ms 183500 KB Output is correct
10 Correct 2669 ms 166888 KB Output is correct
11 Correct 3016 ms 161896 KB Output is correct
12 Correct 2962 ms 156848 KB Output is correct
13 Correct 1774 ms 151808 KB Output is correct
14 Correct 1683 ms 151080 KB Output is correct
15 Correct 2031 ms 153756 KB Output is correct
16 Correct 2005 ms 157696 KB Output is correct
17 Correct 2084 ms 153524 KB Output is correct

Subtask #5
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 11 ms 7296 KB Output is correct
4 Correct 8 ms 7424 KB Output is correct
5 Correct 11 ms 7552 KB Output is correct
6 Correct 12 ms 7680 KB Output is correct
7 Correct 11 ms 7680 KB Output is correct
8 Correct 13 ms 7680 KB Output is correct
9 Correct 11 ms 7652 KB Output is correct
10 Correct 10 ms 7680 KB Output is correct
11 Correct 10 ms 7680 KB Output is correct
12 Correct 11 ms 7680 KB Output is correct
13 Correct 13 ms 7552 KB Output is correct
14 Correct 10 ms 7640 KB Output is correct
15 Correct 10 ms 7680 KB Output is correct
16 Correct 11 ms 7680 KB Output is correct
17 Correct 12 ms 7652 KB Output is correct
18 Correct 11 ms 7680 KB Output is correct
19 Correct 10 ms 7680 KB Output is correct
20 Correct 10 ms 7680 KB Output is correct
21 Correct 10 ms 7680 KB Output is correct
22 Correct 11 ms 7680 KB Output is correct
23 Correct 10 ms 7680 KB Output is correct
24 Correct 10 ms 7680 KB Output is correct
25 Correct 12 ms 7680 KB Output is correct
26 Correct 12 ms 7600 KB Output is correct
27 Correct 11 ms 7680 KB Output is correct
28 Correct 13 ms 7680 KB Output is correct
29 Correct 11 ms 7680 KB Output is correct
30 Correct 12 ms 7680 KB Output is correct
31 Correct 744 ms 41680 KB Output is correct
32 Correct 173 ms 16488 KB Output is correct
33 Correct 611 ms 40364 KB Output is correct
34 Correct 607 ms 41656 KB Output is correct
35 Correct 624 ms 40364 KB Output is correct
36 Correct 606 ms 40356 KB Output is correct
37 Correct 459 ms 40300 KB Output is correct
38 Correct 457 ms 39728 KB Output is correct
39 Correct 339 ms 39668 KB Output is correct
40 Correct 396 ms 39732 KB Output is correct
41 Correct 524 ms 40188 KB Output is correct
42 Correct 473 ms 40812 KB Output is correct
43 Correct 154 ms 20092 KB Output is correct
44 Correct 636 ms 40728 KB Output is correct
45 Correct 482 ms 40428 KB Output is correct
46 Correct 393 ms 40080 KB Output is correct
47 Correct 274 ms 39288 KB Output is correct
48 Correct 255 ms 38436 KB Output is correct
49 Correct 275 ms 39568 KB Output is correct
50 Correct 332 ms 40772 KB Output is correct
51 Correct 321 ms 39392 KB Output is correct
52 Correct 645 ms 45480 KB Output is correct
53 Correct 622 ms 45412 KB Output is correct
54 Correct 614 ms 42312 KB Output is correct
55 Correct 477 ms 42740 KB Output is correct
56 Correct 471 ms 43632 KB Output is correct
57 Correct 429 ms 40816 KB Output is correct
58 Correct 479 ms 42456 KB Output is correct
59 Correct 461 ms 43312 KB Output is correct
60 Correct 555 ms 41404 KB Output is correct
61 Correct 236 ms 38124 KB Output is correct
62 Correct 463 ms 45548 KB Output is correct
63 Correct 496 ms 43216 KB Output is correct
64 Correct 595 ms 42212 KB Output is correct
65 Correct 606 ms 41696 KB Output is correct
66 Correct 642 ms 41184 KB Output is correct
67 Correct 234 ms 32636 KB Output is correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 11 ms 7296 KB Output is correct
4 Correct 8 ms 7424 KB Output is correct
5 Correct 11 ms 7552 KB Output is correct
6 Correct 12 ms 7680 KB Output is correct
7 Correct 11 ms 7680 KB Output is correct
8 Correct 13 ms 7680 KB Output is correct
9 Correct 11 ms 7652 KB Output is correct
10 Correct 10 ms 7680 KB Output is correct
11 Correct 10 ms 7680 KB Output is correct
12 Correct 11 ms 7680 KB Output is correct
13 Correct 13 ms 7552 KB Output is correct
14 Correct 10 ms 7640 KB Output is correct
15 Correct 10 ms 7680 KB Output is correct
16 Correct 11 ms 7680 KB Output is correct
17 Correct 12 ms 7652 KB Output is correct
18 Correct 11 ms 7680 KB Output is correct
19 Correct 10 ms 7680 KB Output is correct
20 Correct 10 ms 7680 KB Output is correct
21 Correct 10 ms 7680 KB Output is correct
22 Correct 11 ms 7680 KB Output is correct
23 Correct 10 ms 7680 KB Output is correct
24 Correct 10 ms 7680 KB Output is correct
25 Correct 12 ms 7680 KB Output is correct
26 Correct 12 ms 7600 KB Output is correct
27 Correct 11 ms 7680 KB Output is correct
28 Correct 13 ms 7680 KB Output is correct
29 Correct 11 ms 7680 KB Output is correct
30 Correct 12 ms 7680 KB Output is correct
31 Correct 744 ms 41680 KB Output is correct
32 Correct 173 ms 16488 KB Output is correct
33 Correct 611 ms 40364 KB Output is correct
34 Correct 607 ms 41656 KB Output is correct
35 Correct 624 ms 40364 KB Output is correct
36 Correct 606 ms 40356 KB Output is correct
37 Correct 459 ms 40300 KB Output is correct
38 Correct 457 ms 39728 KB Output is correct
39 Correct 339 ms 39668 KB Output is correct
40 Correct 396 ms 39732 KB Output is correct
41 Correct 524 ms 40188 KB Output is correct
42 Correct 473 ms 40812 KB Output is correct
43 Correct 154 ms 20092 KB Output is correct
44 Correct 636 ms 40728 KB Output is correct
45 Correct 482 ms 40428 KB Output is correct
46 Correct 393 ms 40080 KB Output is correct
47 Correct 274 ms 39288 KB Output is correct
48 Correct 255 ms 38436 KB Output is correct
49 Correct 275 ms 39568 KB Output is correct
50 Correct 332 ms 40772 KB Output is correct
51 Correct 321 ms 39392 KB Output is correct
52 Correct 2420 ms 165988 KB Output is correct
53 Correct 2343 ms 155632 KB Output is correct
54 Correct 2471 ms 184320 KB Output is correct
55 Correct 2333 ms 168696 KB Output is correct
56 Correct 3015 ms 154488 KB Output is correct
57 Correct 2520 ms 155300 KB Output is correct
58 Correct 2650 ms 184320 KB Output is correct
59 Correct 2273 ms 167104 KB Output is correct
60 Correct 1970 ms 163324 KB Output is correct
61 Correct 2266 ms 157428 KB Output is correct
62 Correct 1609 ms 153648 KB Output is correct
63 Correct 1688 ms 157824 KB Output is correct
64 Correct 3852 ms 160644 KB Output is correct
65 Correct 693 ms 49684 KB Output is correct
66 Correct 3386 ms 155544 KB Output is correct
67 Correct 3621 ms 182384 KB Output is correct
68 Correct 3373 ms 164372 KB Output is correct
69 Correct 3437 ms 166896 KB Output is correct
70 Correct 3729 ms 154568 KB Output is correct
71 Correct 3399 ms 155396 KB Output is correct
72 Correct 3256 ms 183500 KB Output is correct
73 Correct 2669 ms 166888 KB Output is correct
74 Correct 3016 ms 161896 KB Output is correct
75 Correct 2962 ms 156848 KB Output is correct
76 Correct 1774 ms 151808 KB Output is correct
77 Correct 1683 ms 151080 KB Output is correct
78 Correct 2031 ms 153756 KB Output is correct
79 Correct 2005 ms 157696 KB Output is correct
80 Correct 2084 ms 153524 KB Output is correct
81 Correct 645 ms 45480 KB Output is correct
82 Correct 622 ms 45412 KB Output is correct
83 Correct 614 ms 42312 KB Output is correct
84 Correct 477 ms 42740 KB Output is correct
85 Correct 471 ms 43632 KB Output is correct
86 Correct 429 ms 40816 KB Output is correct
87 Correct 479 ms 42456 KB Output is correct
88 Correct 461 ms 43312 KB Output is correct
89 Correct 555 ms 41404 KB Output is correct
90 Correct 236 ms 38124 KB Output is correct
91 Correct 463 ms 45548 KB Output is correct
92 Correct 496 ms 43216 KB Output is correct
93 Correct 595 ms 42212 KB Output is correct
94 Correct 606 ms 41696 KB Output is correct
95 Correct 642 ms 41184 KB Output is correct
96 Correct 234 ms 32636 KB Output is correct
97 Correct 4925 ms 197616 KB Output is correct
98 Correct 802 ms 57352 KB Output is correct
99 Correct 3912 ms 169804 KB Output is correct
100 Correct 4348 ms 197688 KB Output is correct
101 Correct 4279 ms 181972 KB Output is correct
102 Correct 4053 ms 170212 KB Output is correct
103 Correct 3135 ms 170112 KB Output is correct
104 Correct 3228 ms 168740 KB Output is correct
105 Correct 1996 ms 169288 KB Output is correct
106 Correct 2146 ms 168904 KB Output is correct
107 Correct 3357 ms 181820 KB Output is correct
108 Correct 3118 ms 190964 KB Output is correct
109 Correct 3944 ms 176056 KB Output is correct
110 Correct 3964 ms 181608 KB Output is correct
111 Correct 3748 ms 192036 KB Output is correct
112 Correct 3941 ms 175636 KB Output is correct
113 Correct 1160 ms 189660 KB Output is correct
114 Correct 3649 ms 198256 KB Output is correct
115 Correct 4176 ms 192692 KB Output is correct
116 Correct 4411 ms 181304 KB Output is correct
117 Correct 3937 ms 179192 KB Output is correct
118 Correct 3579 ms 176460 KB Output is correct
119 Correct 1117 ms 132336 KB Output is correct
120 Correct 1495 ms 162736 KB Output is correct
121 Correct 1526 ms 165208 KB Output is correct
122 Correct 1486 ms 164828 KB Output is correct
123 Correct 1887 ms 167192 KB Output is correct
124 Correct 1985 ms 171348 KB Output is correct
125 Correct 1886 ms 168072 KB Output is correct
126 Correct 2171 ms 175460 KB Output is correct