oj.uz

Submission #864946

# Submission time Handle Problem Language Result Execution time Memory
864946 2023-10-23T18:57:29 Z danikoynov New Home (APIO18_new_home) C++14
57 / 100
 5000 ms 979352 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;
    
map < pair < int, 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, 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;
    }
    
    map < pair < int, int >, int > :: iterator it;
    for (int i = 1; i <= k; i ++)
        for (it = ray_right[i].begin(); it != ray_right[i].end(); it ++)
        {
            ///cout << it -> first.first << " :: " << it -> first.second << " " << it -> second << endl;
            if (it -> second != 0)
                make_right_segment(it -> first.first, it -> first.second, inf, i);
        }
    
    
    for (int i = 1; i <= k; i ++)
        for (it = ray_left[i].begin(); it != ray_left[i].end(); it ++)
        {
            if (it -> second != 0)
            {
            ///cout << "here " << endl;
                make_left_segment(it -> first.first, it -> first.second, 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:325:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  325 |     for (int i = 1; i < dat.size(); i ++)
      |                     ~~^~~~~~~~~~~~
new_home.cpp:425:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<interval_ray>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  425 |             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

# Verdict Execution time Memory Grader output
1 Correct 40 ms 211804 KB Output is correct
2 Correct 41 ms 211812 KB Output is correct
3 Correct 41 ms 211796 KB Output is correct
4 Correct 41 ms 211800 KB Output is correct
5 Correct 42 ms 211936 KB Output is correct
6 Correct 44 ms 212316 KB Output is correct
7 Correct 43 ms 212168 KB Output is correct
8 Correct 42 ms 212404 KB Output is correct
9 Correct 42 ms 212424 KB Output is correct
10 Correct 44 ms 212308 KB Output is correct
11 Correct 42 ms 212308 KB Output is correct
12 Correct 43 ms 212048 KB Output is correct
13 Correct 42 ms 212060 KB Output is correct
14 Correct 42 ms 212060 KB Output is correct
15 Correct 44 ms 212312 KB Output is correct
16 Correct 43 ms 212316 KB Output is correct
17 Correct 43 ms 212048 KB Output is correct
18 Correct 44 ms 212360 KB Output is correct
19 Correct 43 ms 212280 KB Output is correct
20 Correct 43 ms 212316 KB Output is correct
21 Correct 42 ms 212060 KB Output is correct
22 Correct 42 ms 212336 KB Output is correct
23 Correct 44 ms 212316 KB Output is correct
24 Correct 43 ms 212316 KB Output is correct
25 Correct 43 ms 212316 KB Output is correct
26 Correct 43 ms 212316 KB Output is correct
27 Correct 42 ms 211948 KB Output is correct
28 Correct 43 ms 212056 KB Output is correct
29 Correct 42 ms 212052 KB Output is correct
30 Correct 44 ms 212036 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 211804 KB Output is correct
2 Correct 41 ms 211812 KB Output is correct
3 Correct 41 ms 211796 KB Output is correct
4 Correct 41 ms 211800 KB Output is correct
5 Correct 42 ms 211936 KB Output is correct
6 Correct 44 ms 212316 KB Output is correct
7 Correct 43 ms 212168 KB Output is correct
8 Correct 42 ms 212404 KB Output is correct
9 Correct 42 ms 212424 KB Output is correct
10 Correct 44 ms 212308 KB Output is correct
11 Correct 42 ms 212308 KB Output is correct
12 Correct 43 ms 212048 KB Output is correct
13 Correct 42 ms 212060 KB Output is correct
14 Correct 42 ms 212060 KB Output is correct
15 Correct 44 ms 212312 KB Output is correct
16 Correct 43 ms 212316 KB Output is correct
17 Correct 43 ms 212048 KB Output is correct
18 Correct 44 ms 212360 KB Output is correct
19 Correct 43 ms 212280 KB Output is correct
20 Correct 43 ms 212316 KB Output is correct
21 Correct 42 ms 212060 KB Output is correct
22 Correct 42 ms 212336 KB Output is correct
23 Correct 44 ms 212316 KB Output is correct
24 Correct 43 ms 212316 KB Output is correct
25 Correct 43 ms 212316 KB Output is correct
26 Correct 43 ms 212316 KB Output is correct
27 Correct 42 ms 211948 KB Output is correct
28 Correct 43 ms 212056 KB Output is correct
29 Correct 42 ms 212052 KB Output is correct
30 Correct 44 ms 212036 KB Output is correct
31 Correct 1045 ms 365064 KB Output is correct
32 Correct 126 ms 227964 KB Output is correct
33 Correct 1040 ms 367284 KB Output is correct
34 Correct 1014 ms 365776 KB Output is correct
35 Correct 1071 ms 364360 KB Output is correct
36 Correct 1105 ms 365936 KB Output is correct
37 Correct 774 ms 350648 KB Output is correct
38 Correct 794 ms 353168 KB Output is correct
39 Correct 676 ms 326144 KB Output is correct
40 Correct 693 ms 331516 KB Output is correct
41 Correct 763 ms 313252 KB Output is correct
42 Correct 743 ms 315204 KB Output is correct
43 Correct 94 ms 225088 KB Output is correct
44 Correct 741 ms 311120 KB Output is correct
45 Correct 753 ms 301768 KB Output is correct
46 Correct 609 ms 285016 KB Output is correct
47 Correct 412 ms 277884 KB Output is correct
48 Correct 391 ms 274560 KB Output is correct
49 Correct 502 ms 289788 KB Output is correct
50 Correct 558 ms 306352 KB Output is correct
51 Correct 499 ms 282780 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1944 ms 843660 KB Output is correct
2 Correct 1934 ms 879904 KB Output is correct
3 Correct 1727 ms 902860 KB Output is correct
4 Correct 1975 ms 926920 KB Output is correct
5 Correct 1682 ms 912016 KB Output is correct
6 Correct 1881 ms 885824 KB Output is correct
7 Correct 1697 ms 884564 KB Output is correct
8 Correct 1945 ms 854820 KB Output is correct
9 Correct 2081 ms 857776 KB Output is correct
10 Correct 2167 ms 856260 KB Output is correct
11 Correct 1727 ms 878572 KB Output is correct
12 Correct 1970 ms 877576 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4978 ms 948912 KB Output is correct
2 Correct 414 ms 291244 KB Output is correct
3 Correct 4914 ms 962384 KB Output is correct
4 Correct 2839 ms 951464 KB Output is correct
5 Correct 3968 ms 878876 KB Output is correct
6 Correct 3768 ms 858116 KB Output is correct
7 Correct 4628 ms 979352 KB Output is correct
8 Correct 4893 ms 962164 KB Output is correct
9 Correct 2746 ms 943424 KB Output is correct
10 Correct 3727 ms 908164 KB Output is correct
11 Correct 4648 ms 937576 KB Output is correct
12 Execution timed out 5070 ms 975300 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 211804 KB Output is correct
2 Correct 41 ms 211812 KB Output is correct
3 Correct 41 ms 211796 KB Output is correct
4 Correct 41 ms 211800 KB Output is correct
5 Correct 42 ms 211936 KB Output is correct
6 Correct 44 ms 212316 KB Output is correct
7 Correct 43 ms 212168 KB Output is correct
8 Correct 42 ms 212404 KB Output is correct
9 Correct 42 ms 212424 KB Output is correct
10 Correct 44 ms 212308 KB Output is correct
11 Correct 42 ms 212308 KB Output is correct
12 Correct 43 ms 212048 KB Output is correct
13 Correct 42 ms 212060 KB Output is correct
14 Correct 42 ms 212060 KB Output is correct
15 Correct 44 ms 212312 KB Output is correct
16 Correct 43 ms 212316 KB Output is correct
17 Correct 43 ms 212048 KB Output is correct
18 Correct 44 ms 212360 KB Output is correct
19 Correct 43 ms 212280 KB Output is correct
20 Correct 43 ms 212316 KB Output is correct
21 Correct 42 ms 212060 KB Output is correct
22 Correct 42 ms 212336 KB Output is correct
23 Correct 44 ms 212316 KB Output is correct
24 Correct 43 ms 212316 KB Output is correct
25 Correct 43 ms 212316 KB Output is correct
26 Correct 43 ms 212316 KB Output is correct
27 Correct 42 ms 211948 KB Output is correct
28 Correct 43 ms 212056 KB Output is correct
29 Correct 42 ms 212052 KB Output is correct
30 Correct 44 ms 212036 KB Output is correct
31 Correct 1045 ms 365064 KB Output is correct
32 Correct 126 ms 227964 KB Output is correct
33 Correct 1040 ms 367284 KB Output is correct
34 Correct 1014 ms 365776 KB Output is correct
35 Correct 1071 ms 364360 KB Output is correct
36 Correct 1105 ms 365936 KB Output is correct
37 Correct 774 ms 350648 KB Output is correct
38 Correct 794 ms 353168 KB Output is correct
39 Correct 676 ms 326144 KB Output is correct
40 Correct 693 ms 331516 KB Output is correct
41 Correct 763 ms 313252 KB Output is correct
42 Correct 743 ms 315204 KB Output is correct
43 Correct 94 ms 225088 KB Output is correct
44 Correct 741 ms 311120 KB Output is correct
45 Correct 753 ms 301768 KB Output is correct
46 Correct 609 ms 285016 KB Output is correct
47 Correct 412 ms 277884 KB Output is correct
48 Correct 391 ms 274560 KB Output is correct
49 Correct 502 ms 289788 KB Output is correct
50 Correct 558 ms 306352 KB Output is correct
51 Correct 499 ms 282780 KB Output is correct
52 Correct 623 ms 345212 KB Output is correct
53 Correct 621 ms 348296 KB Output is correct
54 Correct 797 ms 349980 KB Output is correct
55 Correct 660 ms 328168 KB Output is correct
56 Correct 615 ms 333312 KB Output is correct
57 Correct 728 ms 317740 KB Output is correct
58 Correct 693 ms 329716 KB Output is correct
59 Correct 664 ms 335304 KB Output is correct
60 Correct 725 ms 319376 KB Output is correct
61 Correct 139 ms 248008 KB Output is correct
62 Correct 583 ms 355636 KB Output is correct
63 Correct 650 ms 342788 KB Output is correct
64 Correct 694 ms 344680 KB Output is correct
65 Correct 743 ms 338596 KB Output is correct
66 Correct 772 ms 320504 KB Output is correct
67 Correct 217 ms 248908 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 211804 KB Output is correct
2 Correct 41 ms 211812 KB Output is correct
3 Correct 41 ms 211796 KB Output is correct
4 Correct 41 ms 211800 KB Output is correct
5 Correct 42 ms 211936 KB Output is correct
6 Correct 44 ms 212316 KB Output is correct
7 Correct 43 ms 212168 KB Output is correct
8 Correct 42 ms 212404 KB Output is correct
9 Correct 42 ms 212424 KB Output is correct
10 Correct 44 ms 212308 KB Output is correct
11 Correct 42 ms 212308 KB Output is correct
12 Correct 43 ms 212048 KB Output is correct
13 Correct 42 ms 212060 KB Output is correct
14 Correct 42 ms 212060 KB Output is correct
15 Correct 44 ms 212312 KB Output is correct
16 Correct 43 ms 212316 KB Output is correct
17 Correct 43 ms 212048 KB Output is correct
18 Correct 44 ms 212360 KB Output is correct
19 Correct 43 ms 212280 KB Output is correct
20 Correct 43 ms 212316 KB Output is correct
21 Correct 42 ms 212060 KB Output is correct
22 Correct 42 ms 212336 KB Output is correct
23 Correct 44 ms 212316 KB Output is correct
24 Correct 43 ms 212316 KB Output is correct
25 Correct 43 ms 212316 KB Output is correct
26 Correct 43 ms 212316 KB Output is correct
27 Correct 42 ms 211948 KB Output is correct
28 Correct 43 ms 212056 KB Output is correct
29 Correct 42 ms 212052 KB Output is correct
30 Correct 44 ms 212036 KB Output is correct
31 Correct 1045 ms 365064 KB Output is correct
32 Correct 126 ms 227964 KB Output is correct
33 Correct 1040 ms 367284 KB Output is correct
34 Correct 1014 ms 365776 KB Output is correct
35 Correct 1071 ms 364360 KB Output is correct
36 Correct 1105 ms 365936 KB Output is correct
37 Correct 774 ms 350648 KB Output is correct
38 Correct 794 ms 353168 KB Output is correct
39 Correct 676 ms 326144 KB Output is correct
40 Correct 693 ms 331516 KB Output is correct
41 Correct 763 ms 313252 KB Output is correct
42 Correct 743 ms 315204 KB Output is correct
43 Correct 94 ms 225088 KB Output is correct
44 Correct 741 ms 311120 KB Output is correct
45 Correct 753 ms 301768 KB Output is correct
46 Correct 609 ms 285016 KB Output is correct
47 Correct 412 ms 277884 KB Output is correct
48 Correct 391 ms 274560 KB Output is correct
49 Correct 502 ms 289788 KB Output is correct
50 Correct 558 ms 306352 KB Output is correct
51 Correct 499 ms 282780 KB Output is correct
52 Correct 1944 ms 843660 KB Output is correct
53 Correct 1934 ms 879904 KB Output is correct
54 Correct 1727 ms 902860 KB Output is correct
55 Correct 1975 ms 926920 KB Output is correct
56 Correct 1682 ms 912016 KB Output is correct
57 Correct 1881 ms 885824 KB Output is correct
58 Correct 1697 ms 884564 KB Output is correct
59 Correct 1945 ms 854820 KB Output is correct
60 Correct 2081 ms 857776 KB Output is correct
61 Correct 2167 ms 856260 KB Output is correct
62 Correct 1727 ms 878572 KB Output is correct
63 Correct 1970 ms 877576 KB Output is correct
64 Correct 4978 ms 948912 KB Output is correct
65 Correct 414 ms 291244 KB Output is correct
66 Correct 4914 ms 962384 KB Output is correct
67 Correct 2839 ms 951464 KB Output is correct
68 Correct 3968 ms 878876 KB Output is correct
69 Correct 3768 ms 858116 KB Output is correct
70 Correct 4628 ms 979352 KB Output is correct
71 Correct 4893 ms 962164 KB Output is correct
72 Correct 2746 ms 943424 KB Output is correct
73 Correct 3727 ms 908164 KB Output is correct
74 Correct 4648 ms 937576 KB Output is correct
75 Execution timed out 5070 ms 975300 KB Time limit exceeded
76 Halted 0 ms 0 KB -