oj.uz

Submission #375982

# Submission time Handle Problem Language Result Execution time Memory
375982 2021-03-10T13:24:37 Z usachevd0 New Home (APIO18_new_home) C++14
100 / 100
 4966 ms 765164 KB 
#pragma gcc optimize("Ofast")
#pragma gcc optimize("O3")
#pragma gcc target("avx2")
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) { return y < x ? (x = y, true) : false; }
template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) { return y > x ? (x = y, true) : false; }
void debug_out() { cerr << endl; }
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) { cerr << ' ' << A; debug_out(B...); }
template<typename T> void mdebug_out(T *a, int n) { for (int i = 0; i < n; ++i) cerr << a[i] << ' '; cerr << endl; }
#ifdef DEBUG
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
    #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
    #define debug(...) 1337
    #define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T> &a) { for (auto &x : a) stream << x << ' '; return stream; }
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2> &a) { return stream << a.fi << ' ' << a.se; }

const int INF32 = 0x3f3f3f3f;
const int N = 300005;
int n, types, Q;

struct shop_t
{
    int x, tp, t1, t2;
} s[N];

struct query_t
{
    int x, t;
} qr[N];
int qord[N], whenq[N], ans[N];

struct event_t
{
    int t, tp, idx;

    bool operator < (const event_t& oth) const
    {
        if (t != oth.t) return t < oth.t;
        return tp < oth.tp;
    }
} ev[3 * N];
int events;

map<int, pair<int, pii>> ts[N];

struct ray_t
{
    int x1, x2, w, tp;

    bool operator < (const ray_t &oth) const
    {
        if (x1 != oth.x1) return x1 < oth.x1;
        if (x2 != oth.x2) return x2 < oth.x2;
        if (w != oth.w) return w < oth.w;
        return tp < oth.tp;
    }
};

struct event2_t
{
    int x, tp, val;

    bool operator < (const event2_t& oth) const
    {
        if (x != oth.x) return x < oth.x;
        return tp < oth.tp;
    }
};

struct event3_t
{
    char tp;
    int val;
};

namespace lnk
{
    const int maxV = 60000007;
    int V = 1;
    event3_t val[maxV];
    int nxt[maxV];

    void add(int &i, event3_t x)
    {
        if (V == maxV)
        {
            exit(0);
        }
        val[V] = x;
        nxt[V] = i;
        i = V++;
    }
}

namespace sgt
{
    const int logN = 19;
    const int NN = 1 << logN;
//    vector<event2_t> ev[2][2 * NN];
    int ev[2][2 * NN];

    void add_event(event3_t e, int w, int l, int r)
    {
        for (l += NN, r += NN; l <= r; l >>= 1, r >>= 1)
        {
            if (l & 1)  lnk::add(ev[w][l++], e);
            if (~r & 1) lnk::add(ev[w][r--], e);
        }
    }

    void add_query(event3_t e, int t)
    {
        for (t += NN; t >= 1; t >>= 1)
        {
            lnk::add(ev[0][t], e);
            lnk::add(ev[1][t], e);
        }
    }

    event3_t temp[12 * N];
    void dfs(int v, int vl, int vr)
    {
        {
            int mx = -INF32;
            int sz = 0;
            for (int idx = ev[1][v]; idx; idx = lnk::nxt[idx])
            {
                temp[sz++] = lnk::val[idx];
            }
            reverse(temp, temp + sz);
            for (int i = 0; i < sz; ++i)
            {
                auto &e = temp[i];
                if (e.tp == 0)
                {
                    chkmax(mx, e.val);
                }
                else
                {
                    int j = e.val;
                    auto &q = qr[j];
                    chkmax(ans[j], mx - q.x);
                }
            }
        }
        {
            int mn = INF32;
            for (int idx = ev[0][v]; idx; idx = lnk::nxt[idx])
            {
                auto e = lnk::val[idx];
                if (e.tp == 2)
                {
                    chkmin(mn, e.val);
                }
                else
                {
                    int j = e.val;
                    auto &q = qr[j];
                    chkmax(ans[j], q.x - mn);
                }
            }
        }
        if (vl != vr)
        {
            int vm = (vl + vr) >> 1;
            dfs(v << 1, vl, vm);
            dfs(v << 1 | 1, vm + 1, vr);
        }
    }
}

const int MAXRAYS = 10 * N;
ray_t rays[MAXRAYS];
int rays_t1[MAXRAYS];
int rays_cnt;

pair<event2_t, pii> ep[2 * MAXRAYS];
int ep_sz;

signed main()
{
#ifdef DEBUG
    freopen("in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> types >> Q;
    for (int i = 0; i < n; ++i)
    {
        auto &e = s[i];
        cin >> e.x >> e.tp >> e.t1 >> e.t2;
        --e.tp;
        ev[events++] = {e.t1, 0, i};
        ev[events++] = {e.t2, 2, i};
    }
    for (int j = 0; j < Q; ++j)
    {
        auto &q = qr[j];
        cin >> q.x >> q.t;
        ev[events++] = {q.t, 1, j};
    }

    sort(ev, ev + events);
    int T = 0;

    auto add_ray_ev = [&](ray_t ray, int t1, int t2)
    {
        if (t1 <= t2)
        {
            if (ray.w == 0)
            {
                ep[ep_sz++] = {{ray.x2, 2, ray.x1}, {t1, t2}};
            }
            else
            {
                ep[ep_sz++] = {{ray.x1, 0, ray.x2}, {t1, t2}};
            }
        }
    };

    auto add = [&](int x1, int x2, int w, int ri, int tp)
    {
        ray_t ray = {x1, x2, w, tp};
        rays[ri] = ray;
        rays_t1[ri] = T;
    };
    auto add2 = [&](int x1, int x2, int r0, int r1, int tp)
    {
//        cerr << "add2 " << x1 << ' ' << x2 << ' ' << r0 << ' ' << r1 << endl;
        int xm = (x1 + x2) / 2;
        add(x1, xm, 0, r0, tp);
        add(xm + 1, x2, 1, r1, tp);
    };
    auto rem = [&](int ri)
    {   
//        cerr << "rem " << ri << endl;
        add_ray_ev(rays[ri], rays_t1[ri], T - 1);
        rays_t1[ri] = -1;
    };

    rays_cnt = 0;
    for (int tp = 0; tp < types; ++tp)
    {
        ts[tp].insert({-INF32, {1, {-1, rays_cnt}}});
        ts[tp].insert({INF32, {1, {rays_cnt + 1, -1}}});
        add2(-INF32, INF32, rays_cnt, rays_cnt + 1, tp);
        rays_cnt += 2;
    }

    for (int ei = 0; ei < events; ++ei)
    {
        auto& e = ev[ei];
        if (e.tp == 0)
        {
            int i = e.idx;
            auto &f = s[i];
            auto &S = ts[f.tp];
            if (S.find(f.x) != S.end())
                ++S[f.x].fi;
            else
            {
                S.insert({f.x, {1, {rays_cnt + 1, rays_cnt + 2}}});
                auto Y = S.find(f.x);
                auto Z = next(Y);
                auto X = prev(Y);
                rem(X->se.se.se);
                rem(Z->se.se.fi);
                X->se.se.se = rays_cnt;
                Z->se.se.fi = rays_cnt + 3;
                add2(X->fi, Y->fi, rays_cnt, rays_cnt + 1, f.tp);
                add2(Y->fi, Z->fi, rays_cnt + 2, rays_cnt + 3, f.tp);
                rays_cnt += 4;
                assert(rays_cnt < MAXRAYS);
            }
        }
        else if (e.tp == 2)
        {
            int i = e.idx;
            auto &f = s[i];
            auto &S = ts[f.tp];
            if (--S[f.x].fi == 0)
            {
                auto Y = S.find(f.x);
                auto Z = next(Y);
                auto X = prev(Y);
                rem(X->se.se.se);
                rem(Y->se.se.fi);
                rem(Y->se.se.se);
                rem(Z->se.se.fi);
                add2(X->fi, Z->fi, rays_cnt, rays_cnt + 1, f.tp);
                X->se.se.se = rays_cnt;
                Z->se.se.fi = rays_cnt + 1;
                rays_cnt += 2;
                assert(rays_cnt < MAXRAYS);
                S.erase(Y);
            }
        }
        else
        {
            qord[T] = e.idx;
            whenq[e.idx] = T;
            ++T;
        }
    }
    for (int ri = 0; ri < rays_cnt; ++ri)
    {
        if (rays_t1[ri] == -1) continue;
        add_ray_ev(rays[ri], rays_t1[ri], T - 1);
    }

    for (int j = 0; j < Q; ++j)
    {
        auto &q = qr[j];
        ep[ep_sz++] = {{q.x, 1, j}, {whenq[j], -1}};
    }
    sort(ep, ep + ep_sz);
    debug(clock() * 1.0 / CLOCKS_PER_SEC);
    for (int ep_i = 0; ep_i < ep_sz; ++ep_i)
    {
        auto &el = ep[ep_i];
        auto &e = el.fi;
        int t1 = el.se.fi;
        int t2 = el.se.se;
        if (t2 != -1)
        {
            sgt::add_event({e.tp, e.val}, e.tp == 2 ? 0 : 1, t1, t2);
        }
        else
        {
            sgt::add_query({e.tp, e.val}, t1);
        }
    }
    debug(clock() * 1.0 / CLOCKS_PER_SEC);
    fill(ans, ans + Q, -INF32);
    sgt::dfs(1, 0, sgt::NN - 1);
    for (int j = 0; j < Q; ++j)
        cout << (ans[j] >= INF32 / 2 ? -1 : ans[j]) << '\n';
    debug(clock() * 1.0 / CLOCKS_PER_SEC);

    return 0;
}

Compilation message

new_home.cpp:1: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    1 | #pragma gcc optimize("Ofast")
      | 
new_home.cpp:2: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    2 | #pragma gcc optimize("O3")
      | 
new_home.cpp:3: warning: ignoring #pragma gcc target [-Wunknown-pragmas]
    3 | #pragma gcc target("avx2")
      | 
new_home.cpp: In function 'int main()':
new_home.cpp:29:24: warning: statement has no effect [-Wunused-value]
   29 |     #define debug(...) 1337
      |                        ^~~~
new_home.cpp:336:5: note: in expansion of macro 'debug'
  336 |     debug(clock() * 1.0 / CLOCKS_PER_SEC);
      |     ^~~~~
new_home.cpp:345:31: warning: narrowing conversion of 'e.event2_t::tp' from 'int' to 'char' [-Wnarrowing]
  345 |             sgt::add_event({e.tp, e.val}, e.tp == 2 ? 0 : 1, t1, t2);
      |                             ~~^~
new_home.cpp:349:31: warning: narrowing conversion of 'e.event2_t::tp' from 'int' to 'char' [-Wnarrowing]
  349 |             sgt::add_query({e.tp, e.val}, t1);
      |                             ~~^~
new_home.cpp:29:24: warning: statement has no effect [-Wunused-value]
   29 |     #define debug(...) 1337
      |                        ^~~~
new_home.cpp:352:5: note: in expansion of macro 'debug'
  352 |     debug(clock() * 1.0 / CLOCKS_PER_SEC);
      |     ^~~~~
new_home.cpp:29:24: warning: statement has no effect [-Wunused-value]
   29 |     #define debug(...) 1337
      |                        ^~~~
new_home.cpp:357:5: note: in expansion of macro 'debug'
  357 |     debug(clock() * 1.0 / CLOCKS_PER_SEC);
      |     ^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 14572 KB Output is correct
2 Correct 17 ms 14572 KB Output is correct
3 Correct 17 ms 14572 KB Output is correct
4 Correct 18 ms 14572 KB Output is correct
5 Correct 19 ms 14956 KB Output is correct
6 Correct 19 ms 15084 KB Output is correct
7 Correct 19 ms 15212 KB Output is correct
8 Correct 19 ms 15212 KB Output is correct
9 Correct 21 ms 15340 KB Output is correct
10 Correct 19 ms 15212 KB Output is correct
11 Correct 19 ms 15084 KB Output is correct
12 Correct 19 ms 15084 KB Output is correct
13 Correct 18 ms 14956 KB Output is correct
14 Correct 21 ms 14956 KB Output is correct
15 Correct 21 ms 15212 KB Output is correct
16 Correct 19 ms 15212 KB Output is correct
17 Correct 23 ms 15084 KB Output is correct
18 Correct 19 ms 15212 KB Output is correct
19 Correct 19 ms 15232 KB Output is correct
20 Correct 20 ms 15084 KB Output is correct
21 Correct 18 ms 15084 KB Output is correct
22 Correct 19 ms 15340 KB Output is correct
23 Correct 19 ms 15340 KB Output is correct
24 Correct 20 ms 15212 KB Output is correct
25 Correct 19 ms 15084 KB Output is correct
26 Correct 19 ms 15084 KB Output is correct
27 Correct 23 ms 15212 KB Output is correct
28 Correct 18 ms 15016 KB Output is correct
29 Correct 19 ms 15080 KB Output is correct
30 Correct 18 ms 14956 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 14572 KB Output is correct
2 Correct 17 ms 14572 KB Output is correct
3 Correct 17 ms 14572 KB Output is correct
4 Correct 18 ms 14572 KB Output is correct
5 Correct 19 ms 14956 KB Output is correct
6 Correct 19 ms 15084 KB Output is correct
7 Correct 19 ms 15212 KB Output is correct
8 Correct 19 ms 15212 KB Output is correct
9 Correct 21 ms 15340 KB Output is correct
10 Correct 19 ms 15212 KB Output is correct
11 Correct 19 ms 15084 KB Output is correct
12 Correct 19 ms 15084 KB Output is correct
13 Correct 18 ms 14956 KB Output is correct
14 Correct 21 ms 14956 KB Output is correct
15 Correct 21 ms 15212 KB Output is correct
16 Correct 19 ms 15212 KB Output is correct
17 Correct 23 ms 15084 KB Output is correct
18 Correct 19 ms 15212 KB Output is correct
19 Correct 19 ms 15232 KB Output is correct
20 Correct 20 ms 15084 KB Output is correct
21 Correct 18 ms 15084 KB Output is correct
22 Correct 19 ms 15340 KB Output is correct
23 Correct 19 ms 15340 KB Output is correct
24 Correct 20 ms 15212 KB Output is correct
25 Correct 19 ms 15084 KB Output is correct
26 Correct 19 ms 15084 KB Output is correct
27 Correct 23 ms 15212 KB Output is correct
28 Correct 18 ms 15016 KB Output is correct
29 Correct 19 ms 15080 KB Output is correct
30 Correct 18 ms 14956 KB Output is correct
31 Correct 703 ms 122680 KB Output is correct
32 Correct 134 ms 50796 KB Output is correct
33 Correct 636 ms 114924 KB Output is correct
34 Correct 638 ms 115308 KB Output is correct
35 Correct 718 ms 122324 KB Output is correct
36 Correct 726 ms 122112 KB Output is correct
37 Correct 465 ms 104044 KB Output is correct
38 Correct 475 ms 103788 KB Output is correct
39 Correct 341 ms 90092 KB Output is correct
40 Correct 376 ms 93000 KB Output is correct
41 Correct 429 ms 98540 KB Output is correct
42 Correct 430 ms 99584 KB Output is correct
43 Correct 119 ms 52844 KB Output is correct
44 Correct 414 ms 97260 KB Output is correct
45 Correct 369 ms 89836 KB Output is correct
46 Correct 311 ms 77292 KB Output is correct
47 Correct 239 ms 77164 KB Output is correct
48 Correct 226 ms 73452 KB Output is correct
49 Correct 291 ms 81900 KB Output is correct
50 Correct 345 ms 96020 KB Output is correct
51 Correct 259 ms 78060 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1943 ms 354284 KB Output is correct
2 Correct 2182 ms 327844 KB Output is correct
3 Correct 1802 ms 450284 KB Output is correct
4 Correct 1988 ms 370096 KB Output is correct
5 Correct 2251 ms 327048 KB Output is correct
6 Correct 2164 ms 327916 KB Output is correct
7 Correct 1625 ms 450284 KB Output is correct
8 Correct 1671 ms 370128 KB Output is correct
9 Correct 1664 ms 342236 KB Output is correct
10 Correct 1744 ms 329104 KB Output is correct
11 Correct 1334 ms 324944 KB Output is correct
12 Correct 1388 ms 328172 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3302 ms 449404 KB Output is correct
2 Correct 576 ms 194540 KB Output is correct
3 Correct 3409 ms 444348 KB Output is correct
4 Correct 3089 ms 579356 KB Output is correct
5 Correct 3353 ms 473836 KB Output is correct
6 Correct 3303 ms 491788 KB Output is correct
7 Correct 3509 ms 443452 KB Output is correct
8 Correct 3466 ms 444080 KB Output is correct
9 Correct 2854 ms 579116 KB Output is correct
10 Correct 3143 ms 486352 KB Output is correct
11 Correct 3221 ms 457212 KB Output is correct
12 Correct 3189 ms 445424 KB Output is correct
13 Correct 1601 ms 372960 KB Output is correct
14 Correct 1585 ms 368876 KB Output is correct
15 Correct 1865 ms 396080 KB Output is correct
16 Correct 2059 ms 413244 KB Output is correct
17 Correct 2029 ms 405384 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 14572 KB Output is correct
2 Correct 17 ms 14572 KB Output is correct
3 Correct 17 ms 14572 KB Output is correct
4 Correct 18 ms 14572 KB Output is correct
5 Correct 19 ms 14956 KB Output is correct
6 Correct 19 ms 15084 KB Output is correct
7 Correct 19 ms 15212 KB Output is correct
8 Correct 19 ms 15212 KB Output is correct
9 Correct 21 ms 15340 KB Output is correct
10 Correct 19 ms 15212 KB Output is correct
11 Correct 19 ms 15084 KB Output is correct
12 Correct 19 ms 15084 KB Output is correct
13 Correct 18 ms 14956 KB Output is correct
14 Correct 21 ms 14956 KB Output is correct
15 Correct 21 ms 15212 KB Output is correct
16 Correct 19 ms 15212 KB Output is correct
17 Correct 23 ms 15084 KB Output is correct
18 Correct 19 ms 15212 KB Output is correct
19 Correct 19 ms 15232 KB Output is correct
20 Correct 20 ms 15084 KB Output is correct
21 Correct 18 ms 15084 KB Output is correct
22 Correct 19 ms 15340 KB Output is correct
23 Correct 19 ms 15340 KB Output is correct
24 Correct 20 ms 15212 KB Output is correct
25 Correct 19 ms 15084 KB Output is correct
26 Correct 19 ms 15084 KB Output is correct
27 Correct 23 ms 15212 KB Output is correct
28 Correct 18 ms 15016 KB Output is correct
29 Correct 19 ms 15080 KB Output is correct
30 Correct 18 ms 14956 KB Output is correct
31 Correct 703 ms 122680 KB Output is correct
32 Correct 134 ms 50796 KB Output is correct
33 Correct 636 ms 114924 KB Output is correct
34 Correct 638 ms 115308 KB Output is correct
35 Correct 718 ms 122324 KB Output is correct
36 Correct 726 ms 122112 KB Output is correct
37 Correct 465 ms 104044 KB Output is correct
38 Correct 475 ms 103788 KB Output is correct
39 Correct 341 ms 90092 KB Output is correct
40 Correct 376 ms 93000 KB Output is correct
41 Correct 429 ms 98540 KB Output is correct
42 Correct 430 ms 99584 KB Output is correct
43 Correct 119 ms 52844 KB Output is correct
44 Correct 414 ms 97260 KB Output is correct
45 Correct 369 ms 89836 KB Output is correct
46 Correct 311 ms 77292 KB Output is correct
47 Correct 239 ms 77164 KB Output is correct
48 Correct 226 ms 73452 KB Output is correct
49 Correct 291 ms 81900 KB Output is correct
50 Correct 345 ms 96020 KB Output is correct
51 Correct 259 ms 78060 KB Output is correct
52 Correct 646 ms 151056 KB Output is correct
53 Correct 600 ms 143504 KB Output is correct
54 Correct 694 ms 132956 KB Output is correct
55 Correct 529 ms 116588 KB Output is correct
56 Correct 577 ms 125292 KB Output is correct
57 Correct 454 ms 104044 KB Output is correct
58 Correct 524 ms 117740 KB Output is correct
59 Correct 557 ms 126716 KB Output is correct
60 Correct 450 ms 105040 KB Output is correct
61 Correct 223 ms 98412 KB Output is correct
62 Correct 655 ms 152220 KB Output is correct
63 Correct 704 ms 137836 KB Output is correct
64 Correct 693 ms 132348 KB Output is correct
65 Correct 639 ms 120588 KB Output is correct
66 Correct 460 ms 104044 KB Output is correct
67 Correct 337 ms 114284 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 14572 KB Output is correct
2 Correct 17 ms 14572 KB Output is correct
3 Correct 17 ms 14572 KB Output is correct
4 Correct 18 ms 14572 KB Output is correct
5 Correct 19 ms 14956 KB Output is correct
6 Correct 19 ms 15084 KB Output is correct
7 Correct 19 ms 15212 KB Output is correct
8 Correct 19 ms 15212 KB Output is correct
9 Correct 21 ms 15340 KB Output is correct
10 Correct 19 ms 15212 KB Output is correct
11 Correct 19 ms 15084 KB Output is correct
12 Correct 19 ms 15084 KB Output is correct
13 Correct 18 ms 14956 KB Output is correct
14 Correct 21 ms 14956 KB Output is correct
15 Correct 21 ms 15212 KB Output is correct
16 Correct 19 ms 15212 KB Output is correct
17 Correct 23 ms 15084 KB Output is correct
18 Correct 19 ms 15212 KB Output is correct
19 Correct 19 ms 15232 KB Output is correct
20 Correct 20 ms 15084 KB Output is correct
21 Correct 18 ms 15084 KB Output is correct
22 Correct 19 ms 15340 KB Output is correct
23 Correct 19 ms 15340 KB Output is correct
24 Correct 20 ms 15212 KB Output is correct
25 Correct 19 ms 15084 KB Output is correct
26 Correct 19 ms 15084 KB Output is correct
27 Correct 23 ms 15212 KB Output is correct
28 Correct 18 ms 15016 KB Output is correct
29 Correct 19 ms 15080 KB Output is correct
30 Correct 18 ms 14956 KB Output is correct
31 Correct 703 ms 122680 KB Output is correct
32 Correct 134 ms 50796 KB Output is correct
33 Correct 636 ms 114924 KB Output is correct
34 Correct 638 ms 115308 KB Output is correct
35 Correct 718 ms 122324 KB Output is correct
36 Correct 726 ms 122112 KB Output is correct
37 Correct 465 ms 104044 KB Output is correct
38 Correct 475 ms 103788 KB Output is correct
39 Correct 341 ms 90092 KB Output is correct
40 Correct 376 ms 93000 KB Output is correct
41 Correct 429 ms 98540 KB Output is correct
42 Correct 430 ms 99584 KB Output is correct
43 Correct 119 ms 52844 KB Output is correct
44 Correct 414 ms 97260 KB Output is correct
45 Correct 369 ms 89836 KB Output is correct
46 Correct 311 ms 77292 KB Output is correct
47 Correct 239 ms 77164 KB Output is correct
48 Correct 226 ms 73452 KB Output is correct
49 Correct 291 ms 81900 KB Output is correct
50 Correct 345 ms 96020 KB Output is correct
51 Correct 259 ms 78060 KB Output is correct
52 Correct 1943 ms 354284 KB Output is correct
53 Correct 2182 ms 327844 KB Output is correct
54 Correct 1802 ms 450284 KB Output is correct
55 Correct 1988 ms 370096 KB Output is correct
56 Correct 2251 ms 327048 KB Output is correct
57 Correct 2164 ms 327916 KB Output is correct
58 Correct 1625 ms 450284 KB Output is correct
59 Correct 1671 ms 370128 KB Output is correct
60 Correct 1664 ms 342236 KB Output is correct
61 Correct 1744 ms 329104 KB Output is correct
62 Correct 1334 ms 324944 KB Output is correct
63 Correct 1388 ms 328172 KB Output is correct
64 Correct 3302 ms 449404 KB Output is correct
65 Correct 576 ms 194540 KB Output is correct
66 Correct 3409 ms 444348 KB Output is correct
67 Correct 3089 ms 579356 KB Output is correct
68 Correct 3353 ms 473836 KB Output is correct
69 Correct 3303 ms 491788 KB Output is correct
70 Correct 3509 ms 443452 KB Output is correct
71 Correct 3466 ms 444080 KB Output is correct
72 Correct 2854 ms 579116 KB Output is correct
73 Correct 3143 ms 486352 KB Output is correct
74 Correct 3221 ms 457212 KB Output is correct
75 Correct 3189 ms 445424 KB Output is correct
76 Correct 1601 ms 372960 KB Output is correct
77 Correct 1585 ms 368876 KB Output is correct
78 Correct 1865 ms 396080 KB Output is correct
79 Correct 2059 ms 413244 KB Output is correct
80 Correct 2029 ms 405384 KB Output is correct
81 Correct 646 ms 151056 KB Output is correct
82 Correct 600 ms 143504 KB Output is correct
83 Correct 694 ms 132956 KB Output is correct
84 Correct 529 ms 116588 KB Output is correct
85 Correct 577 ms 125292 KB Output is correct
86 Correct 454 ms 104044 KB Output is correct
87 Correct 524 ms 117740 KB Output is correct
88 Correct 557 ms 126716 KB Output is correct
89 Correct 450 ms 105040 KB Output is correct
90 Correct 223 ms 98412 KB Output is correct
91 Correct 655 ms 152220 KB Output is correct
92 Correct 704 ms 137836 KB Output is correct
93 Correct 693 ms 132348 KB Output is correct
94 Correct 639 ms 120588 KB Output is correct
95 Correct 460 ms 104044 KB Output is correct
96 Correct 337 ms 114284 KB Output is correct
97 Correct 4281 ms 760564 KB Output is correct
98 Correct 634 ms 195164 KB Output is correct
99 Correct 4541 ms 564028 KB Output is correct
100 Correct 4008 ms 723072 KB Output is correct
101 Correct 4869 ms 660524 KB Output is correct
102 Correct 4966 ms 600456 KB Output is correct
103 Correct 3156 ms 509468 KB Output is correct
104 Correct 3152 ms 509292 KB Output is correct
105 Correct 1997 ms 438372 KB Output is correct
106 Correct 2240 ms 453628 KB Output is correct
107 Correct 3351 ms 553396 KB Output is correct
108 Correct 3565 ms 600244 KB Output is correct
109 Correct 2860 ms 487984 KB Output is correct
110 Correct 3326 ms 567720 KB Output is correct
111 Correct 3542 ms 619288 KB Output is correct
112 Correct 2878 ms 494916 KB Output is correct
113 Correct 976 ms 449004 KB Output is correct
114 Correct 4282 ms 765164 KB Output is correct
115 Correct 4525 ms 687340 KB Output is correct
116 Correct 4675 ms 656876 KB Output is correct
117 Correct 4308 ms 595452 KB Output is correct
118 Correct 3200 ms 510348 KB Output is correct
119 Correct 2041 ms 562532 KB Output is correct
120 Correct 1070 ms 310712 KB Output is correct
121 Correct 1179 ms 330272 KB Output is correct
122 Correct 1109 ms 311032 KB Output is correct
123 Correct 1352 ms 352492 KB Output is correct
124 Correct 1746 ms 423792 KB Output is correct
125 Correct 1347 ms 333896 KB Output is correct
126 Correct 1984 ms 470980 KB Output is correct