oj.uz

답안 #864967

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
864967 2023-10-23T20:40:45 Z danikoynov 새 집 (APIO18_new_home) C++14
47 / 100
 4640 ms 1048576 KB 
    #include<bits/stdc++.h>
    #define endl '\n'
        
    using namespace std;
    typedef long long ll;
        
    const int maxn = 6e5 + 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 < int, int > cnt[maxn];
    unordered_map < int, int > 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], timer - 1, {start, finish}));
        ray_left[type][start] = 0;
    }
        
    void make_right_segment(int start, int finish, int timer, int type)
    {
        seg_right.push_back(interval_ray(ray_right[type][start], timer - 1, {start, finish}));
        ray_right[type][start] = 0;
    }
        
    void add_event(int type, int cor, int timer)
    {
        cnt[type][cor] ++;
        if (cnt[type][cor] > 1)
            return;

        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] = timer;
            ray_right[type][cor] = timer;
        }
        else
        if (bef == - inf)
        {
            make_left_segment(aft, -inf, timer, type);
            int mid = (cor + aft) / 2;
            ray_right[type][cor] = timer;
            ray_left[type][aft] = timer;
            ray_left[type][cor] = timer;
        }
        else
        if (aft == inf)
        {
            make_right_segment(bef, inf, timer, type);
            int mid = (bef + cor) / 2;
            ray_left[type][cor] = timer;
            ray_right[type][bef] = timer;
            ray_right[type][cor] = 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] = timer;
            ray_left[type][cor] = timer;
            int mid_right = (cor + aft) / 2;
            ray_right[type][cor] = timer;
            ray_left[type][aft] = timer;
        }
        
        act[type].insert(cor);
    }
        
        
    void remove_event(int type, int cor, int timer)
    {
        cnt[type][cor] --;
        if (cnt[type][cor] > 0)
            return;
        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] = 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] = 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] = 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] = timer;
            ray_left[type][aft] = 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] = 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, 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 add_event(int, int, int)':
new_home.cpp:172:17: warning: unused variable 'mid' [-Wunused-variable]
  172 |             int mid = (cor + aft) / 2;
      |                 ^~~
new_home.cpp:181:17: warning: unused variable 'mid' [-Wunused-variable]
  181 |             int mid = (bef + cor) / 2;
      |                 ^~~
new_home.cpp:191:17: warning: unused variable 'mid_left' [-Wunused-variable]
  191 |             int mid_left = (bef + cor) / 2;
      |                 ^~~~~~~~
new_home.cpp:194:17: warning: unused variable 'mid_right' [-Wunused-variable]
  194 |             int mid_right = (cor + aft) / 2;
      |                 ^~~~~~~~~
new_home.cpp: In function 'void remove_event(int, int, int)':
new_home.cpp:246:17: warning: unused variable 'mid' [-Wunused-variable]
  246 |             int mid = (bef + aft) / 2;
      |                 ^~~
new_home.cpp: In function 'void answer_queries()':
new_home.cpp:342:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  342 |         for (int i = 1; i < dat.size(); i ++)
      |                         ~~^~~~~~~~~~~~
new_home.cpp:432:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<interval_ray>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  432 |                 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 55 ms 254804 KB Output is correct
2 Correct 52 ms 254684 KB Output is correct
3 Correct 52 ms 254904 KB Output is correct
4 Correct 53 ms 254916 KB Output is correct
5 Correct 54 ms 254872 KB Output is correct
6 Correct 56 ms 255572 KB Output is correct
7 Correct 61 ms 255572 KB Output is correct
8 Correct 55 ms 255312 KB Output is correct
9 Correct 54 ms 255572 KB Output is correct
10 Correct 54 ms 255316 KB Output is correct
11 Correct 54 ms 255264 KB Output is correct
12 Correct 53 ms 255056 KB Output is correct
13 Correct 53 ms 255056 KB Output is correct
14 Correct 54 ms 255060 KB Output is correct
15 Correct 55 ms 255312 KB Output is correct
16 Correct 55 ms 255512 KB Output is correct
17 Correct 54 ms 255316 KB Output is correct
18 Correct 54 ms 255316 KB Output is correct
19 Correct 56 ms 255404 KB Output is correct
20 Correct 54 ms 255212 KB Output is correct
21 Correct 53 ms 255060 KB Output is correct
22 Correct 54 ms 255568 KB Output is correct
23 Correct 54 ms 255320 KB Output is correct
24 Correct 54 ms 255316 KB Output is correct
25 Correct 54 ms 255316 KB Output is correct
26 Correct 53 ms 255060 KB Output is correct
27 Correct 54 ms 255068 KB Output is correct
28 Correct 54 ms 255056 KB Output is correct
29 Correct 54 ms 255068 KB Output is correct
30 Correct 56 ms 255280 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 254804 KB Output is correct
2 Correct 52 ms 254684 KB Output is correct
3 Correct 52 ms 254904 KB Output is correct
4 Correct 53 ms 254916 KB Output is correct
5 Correct 54 ms 254872 KB Output is correct
6 Correct 56 ms 255572 KB Output is correct
7 Correct 61 ms 255572 KB Output is correct
8 Correct 55 ms 255312 KB Output is correct
9 Correct 54 ms 255572 KB Output is correct
10 Correct 54 ms 255316 KB Output is correct
11 Correct 54 ms 255264 KB Output is correct
12 Correct 53 ms 255056 KB Output is correct
13 Correct 53 ms 255056 KB Output is correct
14 Correct 54 ms 255060 KB Output is correct
15 Correct 55 ms 255312 KB Output is correct
16 Correct 55 ms 255512 KB Output is correct
17 Correct 54 ms 255316 KB Output is correct
18 Correct 54 ms 255316 KB Output is correct
19 Correct 56 ms 255404 KB Output is correct
20 Correct 54 ms 255212 KB Output is correct
21 Correct 53 ms 255060 KB Output is correct
22 Correct 54 ms 255568 KB Output is correct
23 Correct 54 ms 255320 KB Output is correct
24 Correct 54 ms 255316 KB Output is correct
25 Correct 54 ms 255316 KB Output is correct
26 Correct 53 ms 255060 KB Output is correct
27 Correct 54 ms 255068 KB Output is correct
28 Correct 54 ms 255056 KB Output is correct
29 Correct 54 ms 255068 KB Output is correct
30 Correct 56 ms 255280 KB Output is correct
31 Correct 944 ms 393916 KB Output is correct
32 Correct 86 ms 260480 KB Output is correct
33 Correct 849 ms 395972 KB Output is correct
34 Correct 871 ms 396228 KB Output is correct
35 Correct 937 ms 394004 KB Output is correct
36 Correct 887 ms 398008 KB Output is correct
37 Correct 662 ms 383700 KB Output is correct
38 Correct 645 ms 381876 KB Output is correct
39 Correct 594 ms 355260 KB Output is correct
40 Correct 574 ms 362560 KB Output is correct
41 Correct 651 ms 346720 KB Output is correct
42 Correct 664 ms 349820 KB Output is correct
43 Correct 79 ms 261324 KB Output is correct
44 Correct 642 ms 345444 KB Output is correct
45 Correct 611 ms 336504 KB Output is correct
46 Correct 493 ms 319012 KB Output is correct
47 Correct 411 ms 314896 KB Output is correct
48 Correct 348 ms 310780 KB Output is correct
49 Correct 447 ms 324988 KB Output is correct
50 Correct 499 ms 342396 KB Output is correct
51 Correct 421 ms 318120 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1958 ms 881028 KB Output is correct
2 Correct 1899 ms 886052 KB Output is correct
3 Correct 2140 ms 985440 KB Output is correct
4 Correct 2061 ms 943060 KB Output is correct
5 Correct 1895 ms 864100 KB Output is correct
6 Correct 1923 ms 888160 KB Output is correct
7 Runtime error 1334 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4640 ms 945800 KB Output is correct
2 Correct 194 ms 284844 KB Output is correct
3 Correct 4202 ms 948652 KB Output is correct
4 Runtime error 2232 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 254804 KB Output is correct
2 Correct 52 ms 254684 KB Output is correct
3 Correct 52 ms 254904 KB Output is correct
4 Correct 53 ms 254916 KB Output is correct
5 Correct 54 ms 254872 KB Output is correct
6 Correct 56 ms 255572 KB Output is correct
7 Correct 61 ms 255572 KB Output is correct
8 Correct 55 ms 255312 KB Output is correct
9 Correct 54 ms 255572 KB Output is correct
10 Correct 54 ms 255316 KB Output is correct
11 Correct 54 ms 255264 KB Output is correct
12 Correct 53 ms 255056 KB Output is correct
13 Correct 53 ms 255056 KB Output is correct
14 Correct 54 ms 255060 KB Output is correct
15 Correct 55 ms 255312 KB Output is correct
16 Correct 55 ms 255512 KB Output is correct
17 Correct 54 ms 255316 KB Output is correct
18 Correct 54 ms 255316 KB Output is correct
19 Correct 56 ms 255404 KB Output is correct
20 Correct 54 ms 255212 KB Output is correct
21 Correct 53 ms 255060 KB Output is correct
22 Correct 54 ms 255568 KB Output is correct
23 Correct 54 ms 255320 KB Output is correct
24 Correct 54 ms 255316 KB Output is correct
25 Correct 54 ms 255316 KB Output is correct
26 Correct 53 ms 255060 KB Output is correct
27 Correct 54 ms 255068 KB Output is correct
28 Correct 54 ms 255056 KB Output is correct
29 Correct 54 ms 255068 KB Output is correct
30 Correct 56 ms 255280 KB Output is correct
31 Correct 944 ms 393916 KB Output is correct
32 Correct 86 ms 260480 KB Output is correct
33 Correct 849 ms 395972 KB Output is correct
34 Correct 871 ms 396228 KB Output is correct
35 Correct 937 ms 394004 KB Output is correct
36 Correct 887 ms 398008 KB Output is correct
37 Correct 662 ms 383700 KB Output is correct
38 Correct 645 ms 381876 KB Output is correct
39 Correct 594 ms 355260 KB Output is correct
40 Correct 574 ms 362560 KB Output is correct
41 Correct 651 ms 346720 KB Output is correct
42 Correct 664 ms 349820 KB Output is correct
43 Correct 79 ms 261324 KB Output is correct
44 Correct 642 ms 345444 KB Output is correct
45 Correct 611 ms 336504 KB Output is correct
46 Correct 493 ms 319012 KB Output is correct
47 Correct 411 ms 314896 KB Output is correct
48 Correct 348 ms 310780 KB Output is correct
49 Correct 447 ms 324988 KB Output is correct
50 Correct 499 ms 342396 KB Output is correct
51 Correct 421 ms 318120 KB Output is correct
52 Correct 687 ms 404084 KB Output is correct
53 Correct 666 ms 406404 KB Output is correct
54 Correct 759 ms 391980 KB Output is correct
55 Correct 626 ms 370524 KB Output is correct
56 Correct 627 ms 378740 KB Output is correct
57 Correct 631 ms 353888 KB Output is correct
58 Correct 642 ms 372852 KB Output is correct
59 Correct 672 ms 382400 KB Output is correct
60 Correct 670 ms 357752 KB Output is correct
61 Correct 221 ms 305856 KB Output is correct
62 Correct 688 ms 414732 KB Output is correct
63 Correct 718 ms 390140 KB Output is correct
64 Correct 710 ms 386420 KB Output is correct
65 Correct 691 ms 373624 KB Output is correct
66 Correct 665 ms 355192 KB Output is correct
67 Correct 183 ms 285084 KB Output is correct

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 254804 KB Output is correct
2 Correct 52 ms 254684 KB Output is correct
3 Correct 52 ms 254904 KB Output is correct
4 Correct 53 ms 254916 KB Output is correct
5 Correct 54 ms 254872 KB Output is correct
6 Correct 56 ms 255572 KB Output is correct
7 Correct 61 ms 255572 KB Output is correct
8 Correct 55 ms 255312 KB Output is correct
9 Correct 54 ms 255572 KB Output is correct
10 Correct 54 ms 255316 KB Output is correct
11 Correct 54 ms 255264 KB Output is correct
12 Correct 53 ms 255056 KB Output is correct
13 Correct 53 ms 255056 KB Output is correct
14 Correct 54 ms 255060 KB Output is correct
15 Correct 55 ms 255312 KB Output is correct
16 Correct 55 ms 255512 KB Output is correct
17 Correct 54 ms 255316 KB Output is correct
18 Correct 54 ms 255316 KB Output is correct
19 Correct 56 ms 255404 KB Output is correct
20 Correct 54 ms 255212 KB Output is correct
21 Correct 53 ms 255060 KB Output is correct
22 Correct 54 ms 255568 KB Output is correct
23 Correct 54 ms 255320 KB Output is correct
24 Correct 54 ms 255316 KB Output is correct
25 Correct 54 ms 255316 KB Output is correct
26 Correct 53 ms 255060 KB Output is correct
27 Correct 54 ms 255068 KB Output is correct
28 Correct 54 ms 255056 KB Output is correct
29 Correct 54 ms 255068 KB Output is correct
30 Correct 56 ms 255280 KB Output is correct
31 Correct 944 ms 393916 KB Output is correct
32 Correct 86 ms 260480 KB Output is correct
33 Correct 849 ms 395972 KB Output is correct
34 Correct 871 ms 396228 KB Output is correct
35 Correct 937 ms 394004 KB Output is correct
36 Correct 887 ms 398008 KB Output is correct
37 Correct 662 ms 383700 KB Output is correct
38 Correct 645 ms 381876 KB Output is correct
39 Correct 594 ms 355260 KB Output is correct
40 Correct 574 ms 362560 KB Output is correct
41 Correct 651 ms 346720 KB Output is correct
42 Correct 664 ms 349820 KB Output is correct
43 Correct 79 ms 261324 KB Output is correct
44 Correct 642 ms 345444 KB Output is correct
45 Correct 611 ms 336504 KB Output is correct
46 Correct 493 ms 319012 KB Output is correct
47 Correct 411 ms 314896 KB Output is correct
48 Correct 348 ms 310780 KB Output is correct
49 Correct 447 ms 324988 KB Output is correct
50 Correct 499 ms 342396 KB Output is correct
51 Correct 421 ms 318120 KB Output is correct
52 Correct 1958 ms 881028 KB Output is correct
53 Correct 1899 ms 886052 KB Output is correct
54 Correct 2140 ms 985440 KB Output is correct
55 Correct 2061 ms 943060 KB Output is correct
56 Correct 1895 ms 864100 KB Output is correct
57 Correct 1923 ms 888160 KB Output is correct
58 Runtime error 1334 ms 1048576 KB Execution killed with signal 9
59 Halted 0 ms 0 KB -