oj.uz

답안 #107440

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
107440 2019-04-24T10:21:12 Z lyc 새 집 (APIO18_new_home) C++14
100 / 100
 3743 ms 109996 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)

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;

int 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;
    }
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 11 ms 7424 KB Output is correct
3 Correct 9 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 12 ms 7424 KB Output is correct
6 Correct 14 ms 7552 KB Output is correct
7 Correct 11 ms 7552 KB Output is correct
8 Correct 10 ms 7552 KB Output is correct
9 Correct 10 ms 7552 KB Output is correct
10 Correct 11 ms 7552 KB Output is correct
11 Correct 9 ms 7552 KB Output is correct
12 Correct 11 ms 7552 KB Output is correct
13 Correct 11 ms 7552 KB Output is correct
14 Correct 11 ms 7424 KB Output is correct
15 Correct 11 ms 7552 KB Output is correct
16 Correct 11 ms 7552 KB Output is correct
17 Correct 13 ms 7552 KB Output is correct
18 Correct 10 ms 7552 KB Output is correct
19 Correct 10 ms 7552 KB Output is correct
20 Correct 10 ms 7552 KB Output is correct
21 Correct 9 ms 7552 KB Output is correct
22 Correct 11 ms 7552 KB Output is correct
23 Correct 10 ms 7552 KB Output is correct
24 Correct 13 ms 7552 KB Output is correct
25 Correct 12 ms 7680 KB Output is correct
26 Correct 11 ms 7552 KB Output is correct
27 Correct 11 ms 7552 KB Output is correct
28 Correct 12 ms 7552 KB Output is correct
29 Correct 10 ms 7552 KB Output is correct
30 Correct 11 ms 7552 KB Output is correct
31 Correct 528 ms 28180 KB Output is correct
32 Correct 152 ms 12464 KB Output is correct
33 Correct 481 ms 27300 KB Output is correct
34 Correct 498 ms 28076 KB Output is correct
35 Correct 500 ms 27304 KB Output is correct
36 Correct 502 ms 27360 KB Output is correct
37 Correct 399 ms 27412 KB Output is correct
38 Correct 376 ms 27020 KB Output is correct
39 Correct 329 ms 27052 KB Output is correct
40 Correct 329 ms 26952 KB Output is correct
41 Correct 419 ms 27316 KB Output is correct
42 Correct 463 ms 27744 KB Output is correct
43 Correct 143 ms 15096 KB Output is correct
44 Correct 492 ms 27824 KB Output is correct
45 Correct 420 ms 27560 KB Output is correct
46 Correct 459 ms 27324 KB Output is correct
47 Correct 247 ms 26784 KB Output is correct
48 Correct 250 ms 26516 KB Output is correct
49 Correct 253 ms 26856 KB Output is correct
50 Correct 281 ms 27856 KB Output is correct
51 Correct 279 ms 26960 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2037 ms 101868 KB Output is correct
2 Correct 2199 ms 95052 KB Output is correct
3 Correct 2091 ms 109936 KB Output is correct
4 Correct 1911 ms 102936 KB Output is correct
5 Correct 2535 ms 94212 KB Output is correct
6 Correct 2213 ms 94988 KB Output is correct
7 Correct 1905 ms 109996 KB Output is correct
8 Correct 1910 ms 102172 KB Output is correct
9 Correct 1875 ms 99596 KB Output is correct
10 Correct 1950 ms 96632 KB Output is correct
11 Correct 1633 ms 94288 KB Output is correct
12 Correct 1481 ms 96580 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2941 ms 98028 KB Output is correct
2 Correct 666 ms 32716 KB Output is correct
3 Correct 3010 ms 94916 KB Output is correct
4 Correct 3139 ms 107984 KB Output is correct
5 Correct 2934 ms 99464 KB Output is correct
6 Correct 3069 ms 100832 KB Output is correct
7 Correct 3415 ms 94172 KB Output is correct
8 Correct 2759 ms 94956 KB Output is correct
9 Correct 2398 ms 109200 KB Output is correct
10 Correct 2630 ms 101464 KB Output is correct
11 Correct 2560 ms 98540 KB Output is correct
12 Correct 2465 ms 95908 KB Output is correct
13 Correct 1578 ms 93052 KB Output is correct
14 Correct 1507 ms 92312 KB Output is correct
15 Correct 1626 ms 93936 KB Output is correct
16 Correct 1742 ms 95700 KB Output is correct
17 Correct 1742 ms 93284 KB Output is correct

Subtask #5
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 11 ms 7424 KB Output is correct
3 Correct 9 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 12 ms 7424 KB Output is correct
6 Correct 14 ms 7552 KB Output is correct
7 Correct 11 ms 7552 KB Output is correct
8 Correct 10 ms 7552 KB Output is correct
9 Correct 10 ms 7552 KB Output is correct
10 Correct 11 ms 7552 KB Output is correct
11 Correct 9 ms 7552 KB Output is correct
12 Correct 11 ms 7552 KB Output is correct
13 Correct 11 ms 7552 KB Output is correct
14 Correct 11 ms 7424 KB Output is correct
15 Correct 11 ms 7552 KB Output is correct
16 Correct 11 ms 7552 KB Output is correct
17 Correct 13 ms 7552 KB Output is correct
18 Correct 10 ms 7552 KB Output is correct
19 Correct 10 ms 7552 KB Output is correct
20 Correct 10 ms 7552 KB Output is correct
21 Correct 9 ms 7552 KB Output is correct
22 Correct 11 ms 7552 KB Output is correct
23 Correct 10 ms 7552 KB Output is correct
24 Correct 13 ms 7552 KB Output is correct
25 Correct 12 ms 7680 KB Output is correct
26 Correct 11 ms 7552 KB Output is correct
27 Correct 11 ms 7552 KB Output is correct
28 Correct 12 ms 7552 KB Output is correct
29 Correct 10 ms 7552 KB Output is correct
30 Correct 11 ms 7552 KB Output is correct
31 Correct 528 ms 28180 KB Output is correct
32 Correct 152 ms 12464 KB Output is correct
33 Correct 481 ms 27300 KB Output is correct
34 Correct 498 ms 28076 KB Output is correct
35 Correct 500 ms 27304 KB Output is correct
36 Correct 502 ms 27360 KB Output is correct
37 Correct 399 ms 27412 KB Output is correct
38 Correct 376 ms 27020 KB Output is correct
39 Correct 329 ms 27052 KB Output is correct
40 Correct 329 ms 26952 KB Output is correct
41 Correct 419 ms 27316 KB Output is correct
42 Correct 463 ms 27744 KB Output is correct
43 Correct 143 ms 15096 KB Output is correct
44 Correct 492 ms 27824 KB Output is correct
45 Correct 420 ms 27560 KB Output is correct
46 Correct 459 ms 27324 KB Output is correct
47 Correct 247 ms 26784 KB Output is correct
48 Correct 250 ms 26516 KB Output is correct
49 Correct 253 ms 26856 KB Output is correct
50 Correct 281 ms 27856 KB Output is correct
51 Correct 279 ms 26960 KB Output is correct
52 Correct 425 ms 29328 KB Output is correct
53 Correct 495 ms 29224 KB Output is correct
54 Correct 510 ms 27820 KB Output is correct
55 Correct 433 ms 27968 KB Output is correct
56 Correct 358 ms 28568 KB Output is correct
57 Correct 474 ms 27176 KB Output is correct
58 Correct 391 ms 28148 KB Output is correct
59 Correct 394 ms 28204 KB Output is correct
60 Correct 414 ms 27488 KB Output is correct
61 Correct 179 ms 24264 KB Output is correct
62 Correct 442 ms 29444 KB Output is correct
63 Correct 452 ms 28368 KB Output is correct
64 Correct 400 ms 27944 KB Output is correct
65 Correct 438 ms 27668 KB Output is correct
66 Correct 428 ms 27440 KB Output is correct
67 Correct 188 ms 20680 KB Output is correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 11 ms 7424 KB Output is correct
3 Correct 9 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 12 ms 7424 KB Output is correct
6 Correct 14 ms 7552 KB Output is correct
7 Correct 11 ms 7552 KB Output is correct
8 Correct 10 ms 7552 KB Output is correct
9 Correct 10 ms 7552 KB Output is correct
10 Correct 11 ms 7552 KB Output is correct
11 Correct 9 ms 7552 KB Output is correct
12 Correct 11 ms 7552 KB Output is correct
13 Correct 11 ms 7552 KB Output is correct
14 Correct 11 ms 7424 KB Output is correct
15 Correct 11 ms 7552 KB Output is correct
16 Correct 11 ms 7552 KB Output is correct
17 Correct 13 ms 7552 KB Output is correct
18 Correct 10 ms 7552 KB Output is correct
19 Correct 10 ms 7552 KB Output is correct
20 Correct 10 ms 7552 KB Output is correct
21 Correct 9 ms 7552 KB Output is correct
22 Correct 11 ms 7552 KB Output is correct
23 Correct 10 ms 7552 KB Output is correct
24 Correct 13 ms 7552 KB Output is correct
25 Correct 12 ms 7680 KB Output is correct
26 Correct 11 ms 7552 KB Output is correct
27 Correct 11 ms 7552 KB Output is correct
28 Correct 12 ms 7552 KB Output is correct
29 Correct 10 ms 7552 KB Output is correct
30 Correct 11 ms 7552 KB Output is correct
31 Correct 528 ms 28180 KB Output is correct
32 Correct 152 ms 12464 KB Output is correct
33 Correct 481 ms 27300 KB Output is correct
34 Correct 498 ms 28076 KB Output is correct
35 Correct 500 ms 27304 KB Output is correct
36 Correct 502 ms 27360 KB Output is correct
37 Correct 399 ms 27412 KB Output is correct
38 Correct 376 ms 27020 KB Output is correct
39 Correct 329 ms 27052 KB Output is correct
40 Correct 329 ms 26952 KB Output is correct
41 Correct 419 ms 27316 KB Output is correct
42 Correct 463 ms 27744 KB Output is correct
43 Correct 143 ms 15096 KB Output is correct
44 Correct 492 ms 27824 KB Output is correct
45 Correct 420 ms 27560 KB Output is correct
46 Correct 459 ms 27324 KB Output is correct
47 Correct 247 ms 26784 KB Output is correct
48 Correct 250 ms 26516 KB Output is correct
49 Correct 253 ms 26856 KB Output is correct
50 Correct 281 ms 27856 KB Output is correct
51 Correct 279 ms 26960 KB Output is correct
52 Correct 2037 ms 101868 KB Output is correct
53 Correct 2199 ms 95052 KB Output is correct
54 Correct 2091 ms 109936 KB Output is correct
55 Correct 1911 ms 102936 KB Output is correct
56 Correct 2535 ms 94212 KB Output is correct
57 Correct 2213 ms 94988 KB Output is correct
58 Correct 1905 ms 109996 KB Output is correct
59 Correct 1910 ms 102172 KB Output is correct
60 Correct 1875 ms 99596 KB Output is correct
61 Correct 1950 ms 96632 KB Output is correct
62 Correct 1633 ms 94288 KB Output is correct
63 Correct 1481 ms 96580 KB Output is correct
64 Correct 2941 ms 98028 KB Output is correct
65 Correct 666 ms 32716 KB Output is correct
66 Correct 3010 ms 94916 KB Output is correct
67 Correct 3139 ms 107984 KB Output is correct
68 Correct 2934 ms 99464 KB Output is correct
69 Correct 3069 ms 100832 KB Output is correct
70 Correct 3415 ms 94172 KB Output is correct
71 Correct 2759 ms 94956 KB Output is correct
72 Correct 2398 ms 109200 KB Output is correct
73 Correct 2630 ms 101464 KB Output is correct
74 Correct 2560 ms 98540 KB Output is correct
75 Correct 2465 ms 95908 KB Output is correct
76 Correct 1578 ms 93052 KB Output is correct
77 Correct 1507 ms 92312 KB Output is correct
78 Correct 1626 ms 93936 KB Output is correct
79 Correct 1742 ms 95700 KB Output is correct
80 Correct 1742 ms 93284 KB Output is correct
81 Correct 425 ms 29328 KB Output is correct
82 Correct 495 ms 29224 KB Output is correct
83 Correct 510 ms 27820 KB Output is correct
84 Correct 433 ms 27968 KB Output is correct
85 Correct 358 ms 28568 KB Output is correct
86 Correct 474 ms 27176 KB Output is correct
87 Correct 391 ms 28148 KB Output is correct
88 Correct 394 ms 28204 KB Output is correct
89 Correct 414 ms 27488 KB Output is correct
90 Correct 179 ms 24264 KB Output is correct
91 Correct 442 ms 29444 KB Output is correct
92 Correct 452 ms 28368 KB Output is correct
93 Correct 400 ms 27944 KB Output is correct
94 Correct 438 ms 27668 KB Output is correct
95 Correct 428 ms 27440 KB Output is correct
96 Correct 188 ms 20680 KB Output is correct
97 Correct 3414 ms 106732 KB Output is correct
98 Correct 696 ms 32572 KB Output is correct
99 Correct 3527 ms 94004 KB Output is correct
100 Correct 3743 ms 106792 KB Output is correct
101 Correct 3737 ms 99804 KB Output is correct
102 Correct 3445 ms 94060 KB Output is correct
103 Correct 2463 ms 93868 KB Output is correct
104 Correct 2731 ms 93168 KB Output is correct
105 Correct 1873 ms 93496 KB Output is correct
106 Correct 1812 ms 93068 KB Output is correct
107 Correct 2908 ms 99336 KB Output is correct
108 Correct 2575 ms 102080 KB Output is correct
109 Correct 3042 ms 97496 KB Output is correct
110 Correct 3590 ms 99068 KB Output is correct
111 Correct 3383 ms 101052 KB Output is correct
112 Correct 3263 ms 96296 KB Output is correct
113 Correct 952 ms 93184 KB Output is correct
114 Correct 3269 ms 106540 KB Output is correct
115 Correct 3195 ms 101548 KB Output is correct
116 Correct 2898 ms 98844 KB Output is correct
117 Correct 3616 ms 97568 KB Output is correct
118 Correct 3271 ms 96888 KB Output is correct
119 Correct 1075 ms 68492 KB Output is correct
120 Correct 1346 ms 89612 KB Output is correct
121 Correct 1362 ms 90420 KB Output is correct
122 Correct 1210 ms 89632 KB Output is correct
123 Correct 1308 ms 90884 KB Output is correct
124 Correct 1770 ms 92772 KB Output is correct
125 Correct 1564 ms 91348 KB Output is correct
126 Correct 1646 ms 95252 KB Output is correct