답안 #864959

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
864959	2023-10-23T19:28:52 Z	danikoynov	새 집 (APIO18_new_home)	C++14	57 / 100	2163 ms	907096 KB

new_home

    #include<bits/stdc++.h>
    #define endl '\n'
        
    using namespace std;
    typedef long long ll;
        
    const int maxn = 4e5 + 10, inf = 1e9;
        
    struct store
    {
        int x, t, a, b;
    }s[maxn];
        
    struct query
    {
        int l, y, idx;
    }task[maxn];
        
    int n, k, q;
    int readInt () {
        bool minus = false;
        int result = 0;
        char ch;
        ch = getchar();
        while (true) {
            if (ch == '-') break;
            if (ch >= '0' && ch <= '9') break;
            ch = getchar();
        }
        if (ch == '-') minus = true; else result = ch-'0';
        while (true) {
            ch = getchar();
            if (ch < '0' || ch > '9') break;
            result = result*10 + (ch - '0');
        }
        if (minus)
            return -result;
        else
            return result;
    }
    void input()
    {
        n = readInt();
        k = readInt();
        q = readInt();
        ///cin >> n >> k >> q;
        for (int i = 1; i <= n; i ++)
        {
            s[i].x = readInt();
            s[i].t = readInt();
            s[i].a = readInt();
            s[i].b = readInt();
            ///        cin >> s[i].x >> s[i].t >> s[i].a >> s[i].b;
        }
        
        for (int i = 1; i <= q; i ++)
        {
                task[i].l = readInt();
                task[i].y = readInt();
                task[i].idx = i;
            ///cin >> task[i].l >> task[i].y, task[i].idx = i;
        }
    }
        
    unordered_map < int, int > rev;
    int dif, back_to[2 * maxn];
        
     
     
        
    bool cmp_query(query &t1, query &t2)
    {
        return t1.l < t2.l;
    }
        
    struct event
    {
        int type, cor, add, arrive;
        
        event(int _type, int _cor, int _add, int _arrive)
        {
            type = _type;
            cor = _cor;
            add = _add;
            arrive = _arrive;
        }
    };
        
    bool cmp_event(event &e1, event &e2)
    {
        if (e1.arrive != e2.arrive)
            return e1.arrive < e2.arrive;
        
        if (e1.add != e2.add)
            return e1.add < e2.add;
        
        return e1.cor < e2.cor; /// could have dublicates
    }
        
     
        
    multiset < int > act[maxn];
        
    struct interval_ray
    {
        int s, e;
        pair < int, int > ray;
        
        interval_ray(int _s, int _e, pair < int, int > _ray)
        {
            s = _s;
            e = _e;
            ray = _ray;
        }
     
        interval_ray(int &_s, int &_e, pair < int, int > &_ray)
        {
            s = _s;
            e = _e;
            ray = _ray;
        }
    };
     
    vector < interval_ray > seg_left, seg_right;
        struct hash_pair {
        template <class T1, class T2>
        long long operator()(const pair<T1, T2>& p) const
        {
            auto hash1 = hash<T1>{}(p.first);
            auto hash2 = hash<T2>{}(p.second);
            return (hash1 << 16) + hash2;             
        }
    };
     
    unordered_map < pair < int, int >, int, hash_pair > ray_right[maxn], ray_left[maxn];
    vector < int > dat;
    void make_left_segment(int start, int finish, int timer, int type)
    {
        ///cout << "left " << start << " " << finish << " " << timer << endl;
        seg_left.push_back(interval_ray(ray_left[type][{start, finish}], timer - 1, {start, finish}));
        ray_left[type][{start, finish}] = 0;
    }
        
    void make_right_segment(int start, int finish, int timer, int type)
    {
        seg_right.push_back(interval_ray(ray_right[type][{start, finish}], timer - 1, {start, finish}));
        ray_right[type][{start, finish}] = 0;
    }
        
    void add_event(int type, int cor, int timer)
    {
        multiset < int > :: iterator it = act[type].upper_bound(cor);
        int aft = *it;
        int bef = *prev(it);
        
        if (bef == -inf && aft == inf)
        {
            
            make_right_segment(-inf, inf, timer, type);
            ray_left[type][{cor, -inf}] = timer;
            ray_right[type][{cor, +inf}] = timer;
        }
        else
        if (bef == - inf)
        {
            make_left_segment(aft, -inf, timer, type);
            int mid = (cor + aft) / 2;
            ray_right[type][{cor, mid}] = timer;
            ray_left[type][{aft, mid + 1}] = timer;
            ray_left[type][{cor, -inf}] = timer;
        }
        else
        if (aft == inf)
        {
            make_right_segment(bef, inf, timer, type);
            int mid = (bef + cor) / 2;
            ray_left[type][{cor, mid + 1}] = timer;
            ray_right[type][{bef, mid}] = timer;
            ray_right[type][{cor, inf}] = timer;
        }
        else
        {
            int mid = (bef + aft) / 2;
            make_right_segment(bef, mid, timer, type);
            make_left_segment(aft, mid + 1, timer, type);
            int mid_left = (bef + cor) / 2;
            ray_right[type][{bef, mid_left}] = timer;
            ray_left[type][{cor, mid_left + 1}] = timer;
            int mid_right = (cor + aft) / 2;
            ray_right[type][{cor, mid_right}] = timer;
            ray_left[type][{aft, mid_right + 1}] = timer;
        }
        
        act[type].insert(cor);
    }
        
        
    void remove_event(int type, int cor, int timer)
    {
        multiset < int > :: iterator it = act[type].find(cor);
        int aft = *next(it);
        int bef = *prev(it);
        
        if (bef == -inf && aft == inf)
        {
            ///cout << "reverse " << timer << endl;
        
            make_left_segment(cor, -inf, timer, type);
            make_right_segment(cor, +inf, timer, type);
            ray_right[type][{-inf, inf}] = timer;
        
        }
        else
        if (bef == -inf)
        {
        
            ///cout << "step " << timer << endl;
            make_left_segment(cor, -inf, timer, type);
            int mid = (cor + aft) / 2;
            make_right_segment(cor, mid, timer, type);
            make_left_segment(aft, mid + 1, timer, type);
            ray_left[type][{aft, -inf}] = timer;
        
        
        }
        else
        if (aft == inf)
        {
        
            make_right_segment(cor, inf, timer, type);
            int mid = (bef + cor) / 2;
            make_left_segment(cor, mid + 1, timer, type);
            make_right_segment(bef, mid, timer, type);
            ray_right[type][{bef, inf}] = timer;
        }
        else
        {
            int mid = (bef + aft) / 2;
            ///assert((ray_right[type][{bef, mid}]) == 0);
            ///assert((ray_left[type][{aft, mid + 1}]) == 0);
        
            int mid_left = (bef + cor) / 2;
            make_right_segment(bef, mid_left, timer, type);
            make_left_segment(cor, mid_left + 1, timer, type);
            int mid_right = (aft + cor) / 2;
            make_right_segment(cor, mid_right, timer, type);
            make_left_segment(aft, mid_right + 1, timer, type);
        
                    ray_right[type][{bef, mid}] = timer;
            ray_left[type][{aft, mid + 1}] = timer;
        
        }
        
        act[type].erase(it);
    }
        
    int ans[maxn];
        
    vector < interval_ray > tree_left[maxn * 4], tree_right[maxn * 4];
    int pt_lf[4 * maxn], bs_lf[4 * maxn];
    int pt_rf[4 * maxn], bs_rf[4 * maxn];
        
    bool cmp_ray_second(interval_ray r1, interval_ray r2)
    {
        return r1.ray.second < r2.ray.second;
    }
    void update_range(int root, int left, int right, int qleft, int qright, interval_ray &ray, int type)
    {
        if (left > qright || right < qleft)
            return;
        
        if (left >= qleft && right <= qright)
        {
            if (type == -1)
                tree_left[root].push_back(ray);
            else
                tree_right[root].push_back(ray);
            return;
        }
        
        int mid = (left + right) / 2;
        update_range(root * 2, left, mid, qleft, qright, ray, type);
        update_range(root * 2 + 1, mid + 1, right, qleft, qright, ray, type);
        
    }
        
    unordered_map < int, int > event_times;
        
    void answer_queries()
    {
        sort(task + 1, task + q + 1, cmp_query);
        
        vector < event > events;
        for (int i = 1; i <= n; i ++)
        {
            events.push_back(event(s[i].t, s[i].x, 1, s[i].a));
            events.push_back(event(s[i].t, s[i].x, -1, s[i].b + 1));
        }
        
        sort(events.begin(), events.end(), cmp_event);
        
        for (int i = 1; i <= k; i ++)
        {
            act[i].insert(-inf);
            act[i].insert(inf);
            ray_right[i][{-inf, inf}] = 1;
        }
        
        
        int cnt = 0;
        dat.push_back(1);
        dat.push_back(0);
        
        for (event cur : events)
        {
            ///dat.push_back(cur.arrive - 1);
            dat.push_back(cur.arrive);
            ///cout << "event " << cur.arrive << " " << cur.add << " " << cur.cor << " " << cur.type << endl;
            if (cur.add == 1)
                add_event(cur.type, cur.cor, cur.arrive);
            else
                remove_event(cur.type, cur.cor, cur.arrive);
        }
        
        dat.push_back(inf - 1);
        dat.push_back(inf);
        
        for (int i = 1; i <= q; i ++)
            dat.push_back(task[i].y);
        
        sort(dat.begin(), dat.end());
        cnt ++;
        event_times[dat[0]] = cnt;
        for (int i = 1; i < dat.size(); i ++)
        {
            if (dat[i] == dat[i - 1])
                continue;
            cnt ++;
            event_times[dat[i]] = cnt;
        }
        
        
        for (int i = 1; i <= k; i ++)
            for (auto it : ray_right[i])
            {
                ///cout << it -> first.first << " :: " << it -> first.second << " " << it -> second << endl;
                if (it.second != 0)
                    make_right_segment(it.first.first, inf, inf, i);
            }
        
        
        sort(seg_right.begin(), seg_right.end(), cmp_ray_second);
        sort(seg_left.begin(), seg_left.end(), cmp_ray_second);
        for (interval_ray cur : seg_left)
        {
            //assert(event_times[cur.e + 1] != 0);
            update_range(1, 1, cnt, event_times[cur.s], event_times[cur.e + 1] - 1, cur, -1);
        ///    cout << "left ray " << cur.s << " " << cur.e << " " << cur.ray.first << " " << cur.ray.second << endl;
        }
        
        for (interval_ray cur : seg_right)
        {
            //assert(event_times[cur.e + 1] != 0);
            update_range(1, 1, cnt, event_times[cur.s], event_times[cur.e + 1] - 1, cur, 1);
            ///cout << "right ray " << cur.s << " " << cur.e << " " << cur.ray.first << " " << cur.ray.second << endl;
        }
        
        
        for (int i = 1; i <= 4 * cnt; i ++)
        {
            pt_rf[i] = (int)(tree_right[i].size()) - 1;
            bs_rf[i] = inf;
        
            pt_lf[i] = 0;
            bs_lf[i] = -inf;
            ///sort(tree_right[i].begin(), tree_right[i].end(), cmp_ray_second);
            ///sort(tree_left[i].begin(), tree_left[i].end(), cmp_ray_second);
        }
        
        for (int i = q; i > 0; i --)
        {
            int longest = 0;
            int pos = event_times[task[i].y];
            int root = 1, left = 1, right = cnt;
        
            while(true)
            {
        
                while(pt_rf[root] >= 0 && task[i].l <= tree_right[root][pt_rf[root]].ray.second)
                {
                    bs_rf[root] = min(bs_rf[root], tree_right[root][pt_rf[root]].ray.first);
                    pt_rf[root] --;
                }
                longest = max(longest, task[i].l - bs_rf[root]);
        
        
                if (left == right)
                    break;
        
                int mid = (left + right) / 2;
                if (pos <= mid)
                {
                    root *= 2;
                    right = mid;
                }
                else
                {
                    root = root * 2 + 1;
                    left = mid + 1;
                }
            }
        
            ans[task[i].idx] = max(ans[task[i].idx], longest);
        }
        
        for (int i = 1; i <= q; i ++)
        {
            int longest = 0;
            int pos = event_times[task[i].y];
            int root = 1, left = 1, right = cnt;
            while(true)
            {
                ///cout << "step " << root << " " << left << " " << right << endl;
                while(pt_lf[root] < tree_left[root].size() && tree_left[root][pt_lf[root]].ray.second <= task[i].l)
                {
                    bs_lf[root] = max(bs_lf[root], tree_left[root][pt_lf[root]].ray.first);
                    pt_lf[root] ++;
                }
                longest = max(longest, bs_lf[root] - task[i].l);
                /**for (interval_ray cur : tree_left[root])
                {
                    if (task[i].l >= cur.ray.second)
                        longest = max(longest, cur.ray.first - task[i].l);
                }*/
        
        
                if (left == right)
                    break;
        
                int mid = (left + right) / 2;
                if (pos <= mid)
                {
                    root *= 2;
                    right = mid;
                }
                else
                {
                    root = root * 2 + 1;
                    left = mid + 1;
                }
            }
        
            ans[task[i].idx] = max(ans[task[i].idx], longest);
        }
        
        for (int i = 1; i <= q; i ++)
        {
            if (ans[i] > 2e8)
                cout << -1 << endl;
            else
                cout << ans[i] << endl;
        }
    }
    void solve()
    {
        input();
        ///compress_data();
        answer_queries();
    }
        
    void speed()
    {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
    }
    int main()
    {
        
        speed();
        solve();
        return 0;
    }
        
    /**
    2 1 2
    3 1 1 3
    5 1 3 4
    3 3
    3 4
        
        
        
        
    4 2 4
    3 1 1 10
    9 2 2 4
    7 2 5 7
    4 1 8 10
    5 3
    5 6
    5 9
    1 10
        
    2 1 3
    1 1 1 4
    1 1 2 6
    1 3
    1 5
    1 7
        
    1 1 1
    100000000 1 1 1
    1 1
        
        
        
    */

Compilation message

new_home.cpp: In function 'void answer_queries()':
new_home.cpp:334:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  334 |         for (int i = 1; i < dat.size(); i ++)
      |                         ~~^~~~~~~~~~~~
new_home.cpp:424:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<interval_ray>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  424 |                 while(pt_lf[root] < tree_left[root].size() && tree_left[root][pt_lf[root]].ray.second <= task[i].l)
      |                       ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	152148 KB	Output is correct
2	Correct	31 ms	152280 KB	Output is correct
3	Correct	31 ms	152156 KB	Output is correct
4	Correct	31 ms	152332 KB	Output is correct
5	Correct	32 ms	152400 KB	Output is correct
6	Correct	33 ms	152668 KB	Output is correct
7	Correct	33 ms	153000 KB	Output is correct
8	Correct	32 ms	152660 KB	Output is correct
9	Correct	32 ms	152912 KB	Output is correct
10	Correct	34 ms	152920 KB	Output is correct
11	Correct	33 ms	152512 KB	Output is correct
12	Correct	34 ms	152924 KB	Output is correct
13	Correct	33 ms	152400 KB	Output is correct
14	Correct	31 ms	152388 KB	Output is correct
15	Correct	35 ms	152652 KB	Output is correct
16	Correct	33 ms	152748 KB	Output is correct
17	Correct	33 ms	152660 KB	Output is correct
18	Correct	33 ms	152668 KB	Output is correct
19	Correct	33 ms	152864 KB	Output is correct
20	Correct	34 ms	152668 KB	Output is correct
21	Correct	31 ms	152408 KB	Output is correct
22	Correct	32 ms	152912 KB	Output is correct
23	Correct	33 ms	152668 KB	Output is correct
24	Correct	33 ms	152664 KB	Output is correct
25	Correct	33 ms	152752 KB	Output is correct
26	Correct	33 ms	152740 KB	Output is correct
27	Correct	31 ms	152412 KB	Output is correct
28	Correct	33 ms	152660 KB	Output is correct
29	Correct	34 ms	152668 KB	Output is correct
30	Correct	32 ms	152404 KB	Output is correct

Subtask #2

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	152148 KB	Output is correct
2	Correct	31 ms	152280 KB	Output is correct
3	Correct	31 ms	152156 KB	Output is correct
4	Correct	31 ms	152332 KB	Output is correct
5	Correct	32 ms	152400 KB	Output is correct
6	Correct	33 ms	152668 KB	Output is correct
7	Correct	33 ms	153000 KB	Output is correct
8	Correct	32 ms	152660 KB	Output is correct
9	Correct	32 ms	152912 KB	Output is correct
10	Correct	34 ms	152920 KB	Output is correct
11	Correct	33 ms	152512 KB	Output is correct
12	Correct	34 ms	152924 KB	Output is correct
13	Correct	33 ms	152400 KB	Output is correct
14	Correct	31 ms	152388 KB	Output is correct
15	Correct	35 ms	152652 KB	Output is correct
16	Correct	33 ms	152748 KB	Output is correct
17	Correct	33 ms	152660 KB	Output is correct
18	Correct	33 ms	152668 KB	Output is correct
19	Correct	33 ms	152864 KB	Output is correct
20	Correct	34 ms	152668 KB	Output is correct
21	Correct	31 ms	152408 KB	Output is correct
22	Correct	32 ms	152912 KB	Output is correct
23	Correct	33 ms	152668 KB	Output is correct
24	Correct	33 ms	152664 KB	Output is correct
25	Correct	33 ms	152752 KB	Output is correct
26	Correct	33 ms	152740 KB	Output is correct
27	Correct	31 ms	152412 KB	Output is correct
28	Correct	33 ms	152660 KB	Output is correct
29	Correct	34 ms	152668 KB	Output is correct
30	Correct	32 ms	152404 KB	Output is correct
31	Correct	957 ms	301024 KB	Output is correct
32	Correct	110 ms	169160 KB	Output is correct
33	Correct	925 ms	303800 KB	Output is correct
34	Correct	950 ms	302164 KB	Output is correct
35	Correct	951 ms	303484 KB	Output is correct
36	Correct	960 ms	302888 KB	Output is correct
37	Correct	742 ms	290196 KB	Output is correct
38	Correct	730 ms	290744 KB	Output is correct
39	Correct	598 ms	263860 KB	Output is correct
40	Correct	641 ms	270528 KB	Output is correct
41	Correct	669 ms	251500 KB	Output is correct
42	Correct	670 ms	254580 KB	Output is correct
43	Correct	89 ms	165704 KB	Output is correct
44	Correct	667 ms	250232 KB	Output is correct
45	Correct	647 ms	241532 KB	Output is correct
46	Correct	514 ms	223696 KB	Output is correct
47	Correct	393 ms	220228 KB	Output is correct
48	Correct	362 ms	216444 KB	Output is correct
49	Correct	441 ms	229332 KB	Output is correct
50	Correct	519 ms	246476 KB	Output is correct
51	Correct	433 ms	224572 KB	Output is correct

Subtask #3

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2019 ms	805228 KB	Output is correct
2	Correct	2035 ms	805068 KB	Output is correct
3	Correct	2004 ms	907096 KB	Output is correct
4	Correct	1964 ms	824836 KB	Output is correct
5	Correct	2032 ms	781044 KB	Output is correct
6	Correct	2109 ms	790240 KB	Output is correct
7	Correct	2033 ms	866780 KB	Output is correct
8	Correct	1925 ms	823972 KB	Output is correct
9	Correct	2101 ms	786624 KB	Output is correct
10	Correct	2163 ms	836848 KB	Output is correct
11	Correct	1839 ms	773864 KB	Output is correct
12	Correct	1941 ms	813520 KB	Output is correct

Subtask #4

0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	1834 ms	606092 KB	Execution killed with signal 6
2	Halted	0 ms	0 KB	-

Subtask #5

35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	152148 KB	Output is correct
2	Correct	31 ms	152280 KB	Output is correct
3	Correct	31 ms	152156 KB	Output is correct
4	Correct	31 ms	152332 KB	Output is correct
5	Correct	32 ms	152400 KB	Output is correct
6	Correct	33 ms	152668 KB	Output is correct
7	Correct	33 ms	153000 KB	Output is correct
8	Correct	32 ms	152660 KB	Output is correct
9	Correct	32 ms	152912 KB	Output is correct
10	Correct	34 ms	152920 KB	Output is correct
11	Correct	33 ms	152512 KB	Output is correct
12	Correct	34 ms	152924 KB	Output is correct
13	Correct	33 ms	152400 KB	Output is correct
14	Correct	31 ms	152388 KB	Output is correct
15	Correct	35 ms	152652 KB	Output is correct
16	Correct	33 ms	152748 KB	Output is correct
17	Correct	33 ms	152660 KB	Output is correct
18	Correct	33 ms	152668 KB	Output is correct
19	Correct	33 ms	152864 KB	Output is correct
20	Correct	34 ms	152668 KB	Output is correct
21	Correct	31 ms	152408 KB	Output is correct
22	Correct	32 ms	152912 KB	Output is correct
23	Correct	33 ms	152668 KB	Output is correct
24	Correct	33 ms	152664 KB	Output is correct
25	Correct	33 ms	152752 KB	Output is correct
26	Correct	33 ms	152740 KB	Output is correct
27	Correct	31 ms	152412 KB	Output is correct
28	Correct	33 ms	152660 KB	Output is correct
29	Correct	34 ms	152668 KB	Output is correct
30	Correct	32 ms	152404 KB	Output is correct
31	Correct	957 ms	301024 KB	Output is correct
32	Correct	110 ms	169160 KB	Output is correct
33	Correct	925 ms	303800 KB	Output is correct
34	Correct	950 ms	302164 KB	Output is correct
35	Correct	951 ms	303484 KB	Output is correct
36	Correct	960 ms	302888 KB	Output is correct
37	Correct	742 ms	290196 KB	Output is correct
38	Correct	730 ms	290744 KB	Output is correct
39	Correct	598 ms	263860 KB	Output is correct
40	Correct	641 ms	270528 KB	Output is correct
41	Correct	669 ms	251500 KB	Output is correct
42	Correct	670 ms	254580 KB	Output is correct
43	Correct	89 ms	165704 KB	Output is correct
44	Correct	667 ms	250232 KB	Output is correct
45	Correct	647 ms	241532 KB	Output is correct
46	Correct	514 ms	223696 KB	Output is correct
47	Correct	393 ms	220228 KB	Output is correct
48	Correct	362 ms	216444 KB	Output is correct
49	Correct	441 ms	229332 KB	Output is correct
50	Correct	519 ms	246476 KB	Output is correct
51	Correct	433 ms	224572 KB	Output is correct
52	Correct	678 ms	296052 KB	Output is correct
53	Correct	608 ms	297856 KB	Output is correct
54	Correct	774 ms	290252 KB	Output is correct
55	Correct	625 ms	269512 KB	Output is correct
56	Correct	614 ms	277888 KB	Output is correct
57	Correct	646 ms	256628 KB	Output is correct
58	Correct	649 ms	273976 KB	Output is correct
59	Correct	644 ms	279832 KB	Output is correct
60	Correct	682 ms	260620 KB	Output is correct
61	Correct	183 ms	197952 KB	Output is correct
62	Correct	663 ms	306524 KB	Output is correct
63	Correct	684 ms	287464 KB	Output is correct
64	Correct	688 ms	285396 KB	Output is correct
65	Correct	702 ms	277520 KB	Output is correct
66	Correct	699 ms	259796 KB	Output is correct
67	Correct	208 ms	188420 KB	Output is correct

Subtask #6

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	152148 KB	Output is correct
2	Correct	31 ms	152280 KB	Output is correct
3	Correct	31 ms	152156 KB	Output is correct
4	Correct	31 ms	152332 KB	Output is correct
5	Correct	32 ms	152400 KB	Output is correct
6	Correct	33 ms	152668 KB	Output is correct
7	Correct	33 ms	153000 KB	Output is correct
8	Correct	32 ms	152660 KB	Output is correct
9	Correct	32 ms	152912 KB	Output is correct
10	Correct	34 ms	152920 KB	Output is correct
11	Correct	33 ms	152512 KB	Output is correct
12	Correct	34 ms	152924 KB	Output is correct
13	Correct	33 ms	152400 KB	Output is correct
14	Correct	31 ms	152388 KB	Output is correct
15	Correct	35 ms	152652 KB	Output is correct
16	Correct	33 ms	152748 KB	Output is correct
17	Correct	33 ms	152660 KB	Output is correct
18	Correct	33 ms	152668 KB	Output is correct
19	Correct	33 ms	152864 KB	Output is correct
20	Correct	34 ms	152668 KB	Output is correct
21	Correct	31 ms	152408 KB	Output is correct
22	Correct	32 ms	152912 KB	Output is correct
23	Correct	33 ms	152668 KB	Output is correct
24	Correct	33 ms	152664 KB	Output is correct
25	Correct	33 ms	152752 KB	Output is correct
26	Correct	33 ms	152740 KB	Output is correct
27	Correct	31 ms	152412 KB	Output is correct
28	Correct	33 ms	152660 KB	Output is correct
29	Correct	34 ms	152668 KB	Output is correct
30	Correct	32 ms	152404 KB	Output is correct
31	Correct	957 ms	301024 KB	Output is correct
32	Correct	110 ms	169160 KB	Output is correct
33	Correct	925 ms	303800 KB	Output is correct
34	Correct	950 ms	302164 KB	Output is correct
35	Correct	951 ms	303484 KB	Output is correct
36	Correct	960 ms	302888 KB	Output is correct
37	Correct	742 ms	290196 KB	Output is correct
38	Correct	730 ms	290744 KB	Output is correct
39	Correct	598 ms	263860 KB	Output is correct
40	Correct	641 ms	270528 KB	Output is correct
41	Correct	669 ms	251500 KB	Output is correct
42	Correct	670 ms	254580 KB	Output is correct
43	Correct	89 ms	165704 KB	Output is correct
44	Correct	667 ms	250232 KB	Output is correct
45	Correct	647 ms	241532 KB	Output is correct
46	Correct	514 ms	223696 KB	Output is correct
47	Correct	393 ms	220228 KB	Output is correct
48	Correct	362 ms	216444 KB	Output is correct
49	Correct	441 ms	229332 KB	Output is correct
50	Correct	519 ms	246476 KB	Output is correct
51	Correct	433 ms	224572 KB	Output is correct
52	Correct	2019 ms	805228 KB	Output is correct
53	Correct	2035 ms	805068 KB	Output is correct
54	Correct	2004 ms	907096 KB	Output is correct
55	Correct	1964 ms	824836 KB	Output is correct
56	Correct	2032 ms	781044 KB	Output is correct
57	Correct	2109 ms	790240 KB	Output is correct
58	Correct	2033 ms	866780 KB	Output is correct
59	Correct	1925 ms	823972 KB	Output is correct
60	Correct	2101 ms	786624 KB	Output is correct
61	Correct	2163 ms	836848 KB	Output is correct
62	Correct	1839 ms	773864 KB	Output is correct
63	Correct	1941 ms	813520 KB	Output is correct
64	Runtime error	1834 ms	606092 KB	Execution killed with signal 6
65	Halted	0 ms	0 KB	-