oj.uz

Submission #864978

# Submission time Handle Problem Language Result Execution time Memory
864978 2023-10-23T21:08:53 Z danikoynov New Home (APIO18_new_home) C++14
80 / 100
 5000 ms 1048576 KB 
    #include<bits/stdc++.h>
    #define endl '\n'
        
    using namespace std;
    typedef long long ll;
        
    const int maxn = 3e5 + 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;
        }
    }
        
     
        
    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;
    
    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);
            assert(ray_right[type][cor] == 0);
            assert(ray_left[type][aft] == 0);
            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 < pair < int, int > > tree_left[maxn * 8], tree_right[maxn * 8];
    int pt_lf[8 * maxn], bs_lf[8 * maxn];
    int pt_rf[8 * maxn], bs_rf[8 * 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, pair < int, int > &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])
            {
                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)
        {
            update_range(1, 1, cnt, event_times[cur.s], event_times[cur.e + 1] - 1, cur.ray, -1);

        }
        
        for (interval_ray cur : seg_right)
        {
            update_range(1, 1, cnt, event_times[cur.s], event_times[cur.e + 1] - 1, cur.ray, 1);
        }
        
        
        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;

        }
        
        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]].second)
                {
                    bs_rf[root] = min(bs_rf[root], tree_right[root][pt_rf[root]].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]].second <= task[i].l)
                {
                    bs_lf[root] = max(bs_lf[root], tree_left[root][pt_lf[root]].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();
        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:159:17: warning: unused variable 'mid' [-Wunused-variable]
  159 |             int mid = (cor + aft) / 2;
      |                 ^~~
new_home.cpp:168:17: warning: unused variable 'mid' [-Wunused-variable]
  168 |             int mid = (bef + cor) / 2;
      |                 ^~~
new_home.cpp:180:17: warning: unused variable 'mid_left' [-Wunused-variable]
  180 |             int mid_left = (bef + cor) / 2;
      |                 ^~~~~~~~
new_home.cpp:183:17: warning: unused variable 'mid_right' [-Wunused-variable]
  183 |             int mid_right = (cor + aft) / 2;
      |                 ^~~~~~~~~
new_home.cpp: In function 'void remove_event(int, int, int)':
new_home.cpp:235:17: warning: unused variable 'mid' [-Wunused-variable]
  235 |             int mid = (bef + aft) / 2;
      |                 ^~~
new_home.cpp: In function 'void answer_queries()':
new_home.cpp:332:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  332 |         for (int i = 1; i < dat.size(); i ++)
      |                         ~~^~~~~~~~~~~~
new_home.cpp:417:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  417 |                 while(pt_lf[root] < tree_left[root].size() && tree_left[root][pt_lf[root]].second <= task[i].l)
      |                       ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 186972 KB Output is correct
2 Correct 38 ms 187184 KB Output is correct
3 Correct 39 ms 186972 KB Output is correct
4 Correct 39 ms 186972 KB Output is correct
5 Correct 43 ms 187476 KB Output is correct
6 Correct 40 ms 187452 KB Output is correct
7 Correct 41 ms 187740 KB Output is correct
8 Correct 41 ms 187484 KB Output is correct
9 Correct 40 ms 187740 KB Output is correct
10 Correct 41 ms 187596 KB Output is correct
11 Correct 40 ms 187388 KB Output is correct
12 Correct 40 ms 187332 KB Output is correct
13 Correct 39 ms 187392 KB Output is correct
14 Correct 40 ms 187224 KB Output is correct
15 Correct 40 ms 187484 KB Output is correct
16 Correct 41 ms 187476 KB Output is correct
17 Correct 44 ms 187476 KB Output is correct
18 Correct 40 ms 187592 KB Output is correct
19 Correct 41 ms 187484 KB Output is correct
20 Correct 43 ms 187728 KB Output is correct
21 Correct 39 ms 187472 KB Output is correct
22 Correct 40 ms 187728 KB Output is correct
23 Correct 41 ms 187484 KB Output is correct
24 Correct 40 ms 187484 KB Output is correct
25 Correct 41 ms 187476 KB Output is correct
26 Correct 40 ms 187484 KB Output is correct
27 Correct 40 ms 187372 KB Output is correct
28 Correct 41 ms 187472 KB Output is correct
29 Correct 40 ms 187220 KB Output is correct
30 Correct 39 ms 187228 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 186972 KB Output is correct
2 Correct 38 ms 187184 KB Output is correct
3 Correct 39 ms 186972 KB Output is correct
4 Correct 39 ms 186972 KB Output is correct
5 Correct 43 ms 187476 KB Output is correct
6 Correct 40 ms 187452 KB Output is correct
7 Correct 41 ms 187740 KB Output is correct
8 Correct 41 ms 187484 KB Output is correct
9 Correct 40 ms 187740 KB Output is correct
10 Correct 41 ms 187596 KB Output is correct
11 Correct 40 ms 187388 KB Output is correct
12 Correct 40 ms 187332 KB Output is correct
13 Correct 39 ms 187392 KB Output is correct
14 Correct 40 ms 187224 KB Output is correct
15 Correct 40 ms 187484 KB Output is correct
16 Correct 41 ms 187476 KB Output is correct
17 Correct 44 ms 187476 KB Output is correct
18 Correct 40 ms 187592 KB Output is correct
19 Correct 41 ms 187484 KB Output is correct
20 Correct 43 ms 187728 KB Output is correct
21 Correct 39 ms 187472 KB Output is correct
22 Correct 40 ms 187728 KB Output is correct
23 Correct 41 ms 187484 KB Output is correct
24 Correct 40 ms 187484 KB Output is correct
25 Correct 41 ms 187476 KB Output is correct
26 Correct 40 ms 187484 KB Output is correct
27 Correct 40 ms 187372 KB Output is correct
28 Correct 41 ms 187472 KB Output is correct
29 Correct 40 ms 187220 KB Output is correct
30 Correct 39 ms 187228 KB Output is correct
31 Correct 827 ms 281572 KB Output is correct
32 Correct 71 ms 190920 KB Output is correct
33 Correct 759 ms 282320 KB Output is correct
34 Correct 768 ms 282520 KB Output is correct
35 Correct 801 ms 280848 KB Output is correct
36 Correct 785 ms 283400 KB Output is correct
37 Correct 585 ms 276984 KB Output is correct
38 Correct 561 ms 275708 KB Output is correct
39 Correct 497 ms 263104 KB Output is correct
40 Correct 513 ms 265240 KB Output is correct
41 Correct 564 ms 254844 KB Output is correct
42 Correct 558 ms 256632 KB Output is correct
43 Correct 63 ms 191348 KB Output is correct
44 Correct 552 ms 254728 KB Output is correct
45 Correct 535 ms 250196 KB Output is correct
46 Correct 446 ms 241016 KB Output is correct
47 Correct 335 ms 237596 KB Output is correct
48 Correct 308 ms 235432 KB Output is correct
49 Correct 375 ms 243916 KB Output is correct
50 Correct 441 ms 253300 KB Output is correct
51 Correct 375 ms 239388 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1750 ms 567404 KB Output is correct
2 Correct 1712 ms 559788 KB Output is correct
3 Correct 1949 ms 721444 KB Output is correct
4 Correct 1883 ms 578812 KB Output is correct
5 Correct 1673 ms 590064 KB Output is correct
6 Correct 1733 ms 579452 KB Output is correct
7 Correct 1971 ms 698496 KB Output is correct
8 Correct 1866 ms 630192 KB Output is correct
9 Correct 1929 ms 560364 KB Output is correct
10 Correct 1879 ms 603736 KB Output is correct
11 Correct 1563 ms 558508 KB Output is correct
12 Correct 1724 ms 541220 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4239 ms 639420 KB Output is correct
2 Correct 185 ms 212008 KB Output is correct
3 Correct 3877 ms 639744 KB Output is correct
4 Correct 3100 ms 748972 KB Output is correct
5 Correct 3676 ms 607504 KB Output is correct
6 Correct 3489 ms 629784 KB Output is correct
7 Correct 3824 ms 629196 KB Output is correct
8 Correct 3839 ms 648344 KB Output is correct
9 Correct 3000 ms 727580 KB Output is correct
10 Correct 3560 ms 642144 KB Output is correct
11 Correct 4192 ms 623712 KB Output is correct
12 Correct 4057 ms 637964 KB Output is correct
13 Correct 2474 ms 572040 KB Output is correct
14 Correct 2438 ms 560288 KB Output is correct
15 Correct 2694 ms 578728 KB Output is correct
16 Correct 2980 ms 599720 KB Output is correct
17 Correct 2777 ms 606940 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 186972 KB Output is correct
2 Correct 38 ms 187184 KB Output is correct
3 Correct 39 ms 186972 KB Output is correct
4 Correct 39 ms 186972 KB Output is correct
5 Correct 43 ms 187476 KB Output is correct
6 Correct 40 ms 187452 KB Output is correct
7 Correct 41 ms 187740 KB Output is correct
8 Correct 41 ms 187484 KB Output is correct
9 Correct 40 ms 187740 KB Output is correct
10 Correct 41 ms 187596 KB Output is correct
11 Correct 40 ms 187388 KB Output is correct
12 Correct 40 ms 187332 KB Output is correct
13 Correct 39 ms 187392 KB Output is correct
14 Correct 40 ms 187224 KB Output is correct
15 Correct 40 ms 187484 KB Output is correct
16 Correct 41 ms 187476 KB Output is correct
17 Correct 44 ms 187476 KB Output is correct
18 Correct 40 ms 187592 KB Output is correct
19 Correct 41 ms 187484 KB Output is correct
20 Correct 43 ms 187728 KB Output is correct
21 Correct 39 ms 187472 KB Output is correct
22 Correct 40 ms 187728 KB Output is correct
23 Correct 41 ms 187484 KB Output is correct
24 Correct 40 ms 187484 KB Output is correct
25 Correct 41 ms 187476 KB Output is correct
26 Correct 40 ms 187484 KB Output is correct
27 Correct 40 ms 187372 KB Output is correct
28 Correct 41 ms 187472 KB Output is correct
29 Correct 40 ms 187220 KB Output is correct
30 Correct 39 ms 187228 KB Output is correct
31 Correct 827 ms 281572 KB Output is correct
32 Correct 71 ms 190920 KB Output is correct
33 Correct 759 ms 282320 KB Output is correct
34 Correct 768 ms 282520 KB Output is correct
35 Correct 801 ms 280848 KB Output is correct
36 Correct 785 ms 283400 KB Output is correct
37 Correct 585 ms 276984 KB Output is correct
38 Correct 561 ms 275708 KB Output is correct
39 Correct 497 ms 263104 KB Output is correct
40 Correct 513 ms 265240 KB Output is correct
41 Correct 564 ms 254844 KB Output is correct
42 Correct 558 ms 256632 KB Output is correct
43 Correct 63 ms 191348 KB Output is correct
44 Correct 552 ms 254728 KB Output is correct
45 Correct 535 ms 250196 KB Output is correct
46 Correct 446 ms 241016 KB Output is correct
47 Correct 335 ms 237596 KB Output is correct
48 Correct 308 ms 235432 KB Output is correct
49 Correct 375 ms 243916 KB Output is correct
50 Correct 441 ms 253300 KB Output is correct
51 Correct 375 ms 239388 KB Output is correct
52 Correct 627 ms 297812 KB Output is correct
53 Correct 578 ms 299640 KB Output is correct
54 Correct 670 ms 282236 KB Output is correct
55 Correct 526 ms 271612 KB Output is correct
56 Correct 535 ms 277936 KB Output is correct
57 Correct 555 ms 260468 KB Output is correct
58 Correct 554 ms 272568 KB Output is correct
59 Correct 573 ms 281008 KB Output is correct
60 Correct 579 ms 263332 KB Output is correct
61 Correct 190 ms 233412 KB Output is correct
62 Correct 608 ms 303536 KB Output is correct
63 Correct 601 ms 283560 KB Output is correct
64 Correct 595 ms 278900 KB Output is correct
65 Correct 600 ms 270216 KB Output is correct
66 Correct 580 ms 259448 KB Output is correct
67 Correct 153 ms 208304 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 186972 KB Output is correct
2 Correct 38 ms 187184 KB Output is correct
3 Correct 39 ms 186972 KB Output is correct
4 Correct 39 ms 186972 KB Output is correct
5 Correct 43 ms 187476 KB Output is correct
6 Correct 40 ms 187452 KB Output is correct
7 Correct 41 ms 187740 KB Output is correct
8 Correct 41 ms 187484 KB Output is correct
9 Correct 40 ms 187740 KB Output is correct
10 Correct 41 ms 187596 KB Output is correct
11 Correct 40 ms 187388 KB Output is correct
12 Correct 40 ms 187332 KB Output is correct
13 Correct 39 ms 187392 KB Output is correct
14 Correct 40 ms 187224 KB Output is correct
15 Correct 40 ms 187484 KB Output is correct
16 Correct 41 ms 187476 KB Output is correct
17 Correct 44 ms 187476 KB Output is correct
18 Correct 40 ms 187592 KB Output is correct
19 Correct 41 ms 187484 KB Output is correct
20 Correct 43 ms 187728 KB Output is correct
21 Correct 39 ms 187472 KB Output is correct
22 Correct 40 ms 187728 KB Output is correct
23 Correct 41 ms 187484 KB Output is correct
24 Correct 40 ms 187484 KB Output is correct
25 Correct 41 ms 187476 KB Output is correct
26 Correct 40 ms 187484 KB Output is correct
27 Correct 40 ms 187372 KB Output is correct
28 Correct 41 ms 187472 KB Output is correct
29 Correct 40 ms 187220 KB Output is correct
30 Correct 39 ms 187228 KB Output is correct
31 Correct 827 ms 281572 KB Output is correct
32 Correct 71 ms 190920 KB Output is correct
33 Correct 759 ms 282320 KB Output is correct
34 Correct 768 ms 282520 KB Output is correct
35 Correct 801 ms 280848 KB Output is correct
36 Correct 785 ms 283400 KB Output is correct
37 Correct 585 ms 276984 KB Output is correct
38 Correct 561 ms 275708 KB Output is correct
39 Correct 497 ms 263104 KB Output is correct
40 Correct 513 ms 265240 KB Output is correct
41 Correct 564 ms 254844 KB Output is correct
42 Correct 558 ms 256632 KB Output is correct
43 Correct 63 ms 191348 KB Output is correct
44 Correct 552 ms 254728 KB Output is correct
45 Correct 535 ms 250196 KB Output is correct
46 Correct 446 ms 241016 KB Output is correct
47 Correct 335 ms 237596 KB Output is correct
48 Correct 308 ms 235432 KB Output is correct
49 Correct 375 ms 243916 KB Output is correct
50 Correct 441 ms 253300 KB Output is correct
51 Correct 375 ms 239388 KB Output is correct
52 Correct 1750 ms 567404 KB Output is correct
53 Correct 1712 ms 559788 KB Output is correct
54 Correct 1949 ms 721444 KB Output is correct
55 Correct 1883 ms 578812 KB Output is correct
56 Correct 1673 ms 590064 KB Output is correct
57 Correct 1733 ms 579452 KB Output is correct
58 Correct 1971 ms 698496 KB Output is correct
59 Correct 1866 ms 630192 KB Output is correct
60 Correct 1929 ms 560364 KB Output is correct
61 Correct 1879 ms 603736 KB Output is correct
62 Correct 1563 ms 558508 KB Output is correct
63 Correct 1724 ms 541220 KB Output is correct
64 Correct 4239 ms 639420 KB Output is correct
65 Correct 185 ms 212008 KB Output is correct
66 Correct 3877 ms 639744 KB Output is correct
67 Correct 3100 ms 748972 KB Output is correct
68 Correct 3676 ms 607504 KB Output is correct
69 Correct 3489 ms 629784 KB Output is correct
70 Correct 3824 ms 629196 KB Output is correct
71 Correct 3839 ms 648344 KB Output is correct
72 Correct 3000 ms 727580 KB Output is correct
73 Correct 3560 ms 642144 KB Output is correct
74 Correct 4192 ms 623712 KB Output is correct
75 Correct 4057 ms 637964 KB Output is correct
76 Correct 2474 ms 572040 KB Output is correct
77 Correct 2438 ms 560288 KB Output is correct
78 Correct 2694 ms 578728 KB Output is correct
79 Correct 2980 ms 599720 KB Output is correct
80 Correct 2777 ms 606940 KB Output is correct
81 Correct 627 ms 297812 KB Output is correct
82 Correct 578 ms 299640 KB Output is correct
83 Correct 670 ms 282236 KB Output is correct
84 Correct 526 ms 271612 KB Output is correct
85 Correct 535 ms 277936 KB Output is correct
86 Correct 555 ms 260468 KB Output is correct
87 Correct 554 ms 272568 KB Output is correct
88 Correct 573 ms 281008 KB Output is correct
89 Correct 579 ms 263332 KB Output is correct
90 Correct 190 ms 233412 KB Output is correct
91 Correct 608 ms 303536 KB Output is correct
92 Correct 601 ms 283560 KB Output is correct
93 Correct 595 ms 278900 KB Output is correct
94 Correct 600 ms 270216 KB Output is correct
95 Correct 580 ms 259448 KB Output is correct
96 Correct 153 ms 208304 KB Output is correct
97 Execution timed out 5184 ms 1048576 KB Time limit exceeded
98 Halted 0 ms 0 KB -