Submission #864939

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
864939	2023-10-23T18:52:00 Z	danikoynov	New Home (APIO18_new_home)	C++14	57 / 100	5000 ms	947676 KB

new_home

#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;

const int BUFF_SIZE = 2e5;
int buffPos = BUFF_SIZE - 1;
char buff[BUFF_SIZE];

void readChar()
{
    if (++buffPos == BUFF_SIZE) fread(buff, BUFF_SIZE, 1, stdin), buffPos = 0;
}

void readInt(int &num)
{
    num = 0;
    for (; '0' > buff[buffPos] || buff[buffPos] > '9' ; readChar());
    for (; '0' <= buff[buffPos] && buff[buffPos] <= '9' ; readChar())
        num = 10 * num + buff[buffPos] - '0';
}

void input()
{
    readInt(n);
    readInt(k);
    readInt(q);
    ///cin >> n >> k >> q;
    for (int i = 1; i <= n; i ++)
    {
        readInt(s[i].x);
        readInt(s[i].t);
        readInt(s[i].a);
        readInt(s[i].b);
        ///        cin >> s[i].x >> s[i].t >> s[i].a >> s[i].b;
    }
    
    for (int i = 1; i <= q; i ++)
    {
            readInt(task[i].l);
            readInt(task[i].y);
            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];
    
int get_mid(int left, int right)
{
    if (left == right)
        return rev[left];
    
    int lf = rev[left], rf = rev[right];
    while(lf <= rf)
    {
        int mf = (lf + rf) / 2;
        if (abs(left - back_to[mf]) <= abs(right - back_to[mf]))
            lf = mf + 1;
        else
            rf = mf - 1;
    }
    
    return rf;
}
void compress_data()
{
    vector < int > cor;
    for (int i = 1; i <= n; i ++)
        cor.push_back(s[i].x);
    for (int i = 1; i <= q; i ++)
        cor.push_back(task[i].l);
    
    sort(cor.begin(), cor.end());
    int sz = cor.size();
    
    for (int i = 0; i < cor.size(); i ++)
    {
        if (i != 0 || cor[i - 1] != cor[i])
        {
            dif ++;
            rev[cor[i]] = dif;
            back_to[dif] = cor[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;
    }
};
    
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 compress_data()':
new_home.cpp:93:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for (int i = 0; i < cor.size(); i ++)
      |                     ~~^~~~~~~~~~~~
new_home.cpp:91:9: warning: unused variable 'sz' [-Wunused-variable]
   91 |     int sz = cor.size();
      |         ^~
new_home.cpp: In function 'void answer_queries()':
new_home.cpp:353:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  353 |     for (int i = 1; i < dat.size(); i ++)
      |                     ~~^~~~~~~~~~~~
new_home.cpp:453:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<interval_ray>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  453 |             while(pt_lf[root] < tree_left[root].size() && tree_left[root][pt_lf[root]].ray.second <= task[i].l)
      |                   ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp: In function 'void readChar()':
new_home.cpp:27:38: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     if (++buffPos == BUFF_SIZE) fread(buff, BUFF_SIZE, 1, stdin), buffPos = 0;
      |                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	41 ms	211796 KB	Output is correct
2	Correct	42 ms	211804 KB	Output is correct
3	Correct	41 ms	211792 KB	Output is correct
4	Correct	40 ms	211792 KB	Output is correct
5	Correct	42 ms	211792 KB	Output is correct
6	Correct	43 ms	212308 KB	Output is correct
7	Correct	43 ms	212316 KB	Output is correct
8	Correct	43 ms	212316 KB	Output is correct
9	Correct	43 ms	212228 KB	Output is correct
10	Correct	45 ms	212564 KB	Output is correct
11	Correct	43 ms	212216 KB	Output is correct
12	Correct	43 ms	212056 KB	Output is correct
13	Correct	43 ms	212052 KB	Output is correct
14	Correct	43 ms	211896 KB	Output is correct
15	Correct	42 ms	212084 KB	Output is correct
16	Correct	43 ms	212140 KB	Output is correct
17	Correct	43 ms	212316 KB	Output is correct
18	Correct	43 ms	212308 KB	Output is correct
19	Correct	43 ms	212308 KB	Output is correct
20	Correct	44 ms	212288 KB	Output is correct
21	Correct	43 ms	211916 KB	Output is correct
22	Correct	43 ms	212176 KB	Output is correct
23	Correct	44 ms	212316 KB	Output is correct
24	Correct	44 ms	212308 KB	Output is correct
25	Correct	44 ms	212276 KB	Output is correct
26	Correct	43 ms	212024 KB	Output is correct
27	Correct	41 ms	212052 KB	Output is correct
28	Correct	42 ms	212060 KB	Output is correct
29	Correct	43 ms	212060 KB	Output is correct
30	Correct	42 ms	211956 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	41 ms	211796 KB	Output is correct
2	Correct	42 ms	211804 KB	Output is correct
3	Correct	41 ms	211792 KB	Output is correct
4	Correct	40 ms	211792 KB	Output is correct
5	Correct	42 ms	211792 KB	Output is correct
6	Correct	43 ms	212308 KB	Output is correct
7	Correct	43 ms	212316 KB	Output is correct
8	Correct	43 ms	212316 KB	Output is correct
9	Correct	43 ms	212228 KB	Output is correct
10	Correct	45 ms	212564 KB	Output is correct
11	Correct	43 ms	212216 KB	Output is correct
12	Correct	43 ms	212056 KB	Output is correct
13	Correct	43 ms	212052 KB	Output is correct
14	Correct	43 ms	211896 KB	Output is correct
15	Correct	42 ms	212084 KB	Output is correct
16	Correct	43 ms	212140 KB	Output is correct
17	Correct	43 ms	212316 KB	Output is correct
18	Correct	43 ms	212308 KB	Output is correct
19	Correct	43 ms	212308 KB	Output is correct
20	Correct	44 ms	212288 KB	Output is correct
21	Correct	43 ms	211916 KB	Output is correct
22	Correct	43 ms	212176 KB	Output is correct
23	Correct	44 ms	212316 KB	Output is correct
24	Correct	44 ms	212308 KB	Output is correct
25	Correct	44 ms	212276 KB	Output is correct
26	Correct	43 ms	212024 KB	Output is correct
27	Correct	41 ms	212052 KB	Output is correct
28	Correct	42 ms	212060 KB	Output is correct
29	Correct	43 ms	212060 KB	Output is correct
30	Correct	42 ms	211956 KB	Output is correct
31	Correct	1018 ms	364976 KB	Output is correct
32	Correct	123 ms	227872 KB	Output is correct
33	Correct	1039 ms	366008 KB	Output is correct
34	Correct	993 ms	364988 KB	Output is correct
35	Correct	1035 ms	365036 KB	Output is correct
36	Correct	1058 ms	367324 KB	Output is correct
37	Correct	773 ms	351160 KB	Output is correct
38	Correct	795 ms	351784 KB	Output is correct
39	Correct	662 ms	324020 KB	Output is correct
40	Correct	687 ms	331196 KB	Output is correct
41	Correct	736 ms	312700 KB	Output is correct
42	Correct	752 ms	315016 KB	Output is correct
43	Correct	95 ms	225100 KB	Output is correct
44	Correct	753 ms	310772 KB	Output is correct
45	Correct	728 ms	301948 KB	Output is correct
46	Correct	608 ms	284740 KB	Output is correct
47	Correct	413 ms	277884 KB	Output is correct
48	Correct	405 ms	274680 KB	Output is correct
49	Correct	483 ms	289748 KB	Output is correct
50	Correct	566 ms	306368 KB	Output is correct
51	Correct	497 ms	283000 KB	Output is correct

Subtask #3

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1975 ms	871656 KB	Output is correct
2	Correct	1927 ms	881408 KB	Output is correct
3	Correct	1717 ms	879784 KB	Output is correct
4	Correct	1951 ms	862412 KB	Output is correct
5	Correct	1699 ms	881024 KB	Output is correct
6	Correct	1864 ms	849288 KB	Output is correct
7	Correct	1725 ms	900340 KB	Output is correct
8	Correct	2045 ms	898584 KB	Output is correct
9	Correct	2327 ms	855468 KB	Output is correct
10	Correct	2353 ms	901404 KB	Output is correct
11	Correct	1852 ms	854776 KB	Output is correct
12	Correct	2041 ms	872660 KB	Output is correct

Subtask #4

0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	5048 ms	947676 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5

35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	41 ms	211796 KB	Output is correct
2	Correct	42 ms	211804 KB	Output is correct
3	Correct	41 ms	211792 KB	Output is correct
4	Correct	40 ms	211792 KB	Output is correct
5	Correct	42 ms	211792 KB	Output is correct
6	Correct	43 ms	212308 KB	Output is correct
7	Correct	43 ms	212316 KB	Output is correct
8	Correct	43 ms	212316 KB	Output is correct
9	Correct	43 ms	212228 KB	Output is correct
10	Correct	45 ms	212564 KB	Output is correct
11	Correct	43 ms	212216 KB	Output is correct
12	Correct	43 ms	212056 KB	Output is correct
13	Correct	43 ms	212052 KB	Output is correct
14	Correct	43 ms	211896 KB	Output is correct
15	Correct	42 ms	212084 KB	Output is correct
16	Correct	43 ms	212140 KB	Output is correct
17	Correct	43 ms	212316 KB	Output is correct
18	Correct	43 ms	212308 KB	Output is correct
19	Correct	43 ms	212308 KB	Output is correct
20	Correct	44 ms	212288 KB	Output is correct
21	Correct	43 ms	211916 KB	Output is correct
22	Correct	43 ms	212176 KB	Output is correct
23	Correct	44 ms	212316 KB	Output is correct
24	Correct	44 ms	212308 KB	Output is correct
25	Correct	44 ms	212276 KB	Output is correct
26	Correct	43 ms	212024 KB	Output is correct
27	Correct	41 ms	212052 KB	Output is correct
28	Correct	42 ms	212060 KB	Output is correct
29	Correct	43 ms	212060 KB	Output is correct
30	Correct	42 ms	211956 KB	Output is correct
31	Correct	1018 ms	364976 KB	Output is correct
32	Correct	123 ms	227872 KB	Output is correct
33	Correct	1039 ms	366008 KB	Output is correct
34	Correct	993 ms	364988 KB	Output is correct
35	Correct	1035 ms	365036 KB	Output is correct
36	Correct	1058 ms	367324 KB	Output is correct
37	Correct	773 ms	351160 KB	Output is correct
38	Correct	795 ms	351784 KB	Output is correct
39	Correct	662 ms	324020 KB	Output is correct
40	Correct	687 ms	331196 KB	Output is correct
41	Correct	736 ms	312700 KB	Output is correct
42	Correct	752 ms	315016 KB	Output is correct
43	Correct	95 ms	225100 KB	Output is correct
44	Correct	753 ms	310772 KB	Output is correct
45	Correct	728 ms	301948 KB	Output is correct
46	Correct	608 ms	284740 KB	Output is correct
47	Correct	413 ms	277884 KB	Output is correct
48	Correct	405 ms	274680 KB	Output is correct
49	Correct	483 ms	289748 KB	Output is correct
50	Correct	566 ms	306368 KB	Output is correct
51	Correct	497 ms	283000 KB	Output is correct
52	Correct	699 ms	345528 KB	Output is correct
53	Correct	659 ms	347752 KB	Output is correct
54	Correct	877 ms	349008 KB	Output is correct
55	Correct	739 ms	327540 KB	Output is correct
56	Correct	714 ms	332032 KB	Output is correct
57	Correct	800 ms	316940 KB	Output is correct
58	Correct	765 ms	329768 KB	Output is correct
59	Correct	756 ms	335616 KB	Output is correct
60	Correct	814 ms	320080 KB	Output is correct
61	Correct	146 ms	246988 KB	Output is correct
62	Correct	653 ms	355840 KB	Output is correct
63	Correct	741 ms	342836 KB	Output is correct
64	Correct	771 ms	343156 KB	Output is correct
65	Correct	822 ms	339576 KB	Output is correct
66	Correct	801 ms	320400 KB	Output is correct
67	Correct	240 ms	249288 KB	Output is correct

Subtask #6

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	41 ms	211796 KB	Output is correct
2	Correct	42 ms	211804 KB	Output is correct
3	Correct	41 ms	211792 KB	Output is correct
4	Correct	40 ms	211792 KB	Output is correct
5	Correct	42 ms	211792 KB	Output is correct
6	Correct	43 ms	212308 KB	Output is correct
7	Correct	43 ms	212316 KB	Output is correct
8	Correct	43 ms	212316 KB	Output is correct
9	Correct	43 ms	212228 KB	Output is correct
10	Correct	45 ms	212564 KB	Output is correct
11	Correct	43 ms	212216 KB	Output is correct
12	Correct	43 ms	212056 KB	Output is correct
13	Correct	43 ms	212052 KB	Output is correct
14	Correct	43 ms	211896 KB	Output is correct
15	Correct	42 ms	212084 KB	Output is correct
16	Correct	43 ms	212140 KB	Output is correct
17	Correct	43 ms	212316 KB	Output is correct
18	Correct	43 ms	212308 KB	Output is correct
19	Correct	43 ms	212308 KB	Output is correct
20	Correct	44 ms	212288 KB	Output is correct
21	Correct	43 ms	211916 KB	Output is correct
22	Correct	43 ms	212176 KB	Output is correct
23	Correct	44 ms	212316 KB	Output is correct
24	Correct	44 ms	212308 KB	Output is correct
25	Correct	44 ms	212276 KB	Output is correct
26	Correct	43 ms	212024 KB	Output is correct
27	Correct	41 ms	212052 KB	Output is correct
28	Correct	42 ms	212060 KB	Output is correct
29	Correct	43 ms	212060 KB	Output is correct
30	Correct	42 ms	211956 KB	Output is correct
31	Correct	1018 ms	364976 KB	Output is correct
32	Correct	123 ms	227872 KB	Output is correct
33	Correct	1039 ms	366008 KB	Output is correct
34	Correct	993 ms	364988 KB	Output is correct
35	Correct	1035 ms	365036 KB	Output is correct
36	Correct	1058 ms	367324 KB	Output is correct
37	Correct	773 ms	351160 KB	Output is correct
38	Correct	795 ms	351784 KB	Output is correct
39	Correct	662 ms	324020 KB	Output is correct
40	Correct	687 ms	331196 KB	Output is correct
41	Correct	736 ms	312700 KB	Output is correct
42	Correct	752 ms	315016 KB	Output is correct
43	Correct	95 ms	225100 KB	Output is correct
44	Correct	753 ms	310772 KB	Output is correct
45	Correct	728 ms	301948 KB	Output is correct
46	Correct	608 ms	284740 KB	Output is correct
47	Correct	413 ms	277884 KB	Output is correct
48	Correct	405 ms	274680 KB	Output is correct
49	Correct	483 ms	289748 KB	Output is correct
50	Correct	566 ms	306368 KB	Output is correct
51	Correct	497 ms	283000 KB	Output is correct
52	Correct	1975 ms	871656 KB	Output is correct
53	Correct	1927 ms	881408 KB	Output is correct
54	Correct	1717 ms	879784 KB	Output is correct
55	Correct	1951 ms	862412 KB	Output is correct
56	Correct	1699 ms	881024 KB	Output is correct
57	Correct	1864 ms	849288 KB	Output is correct
58	Correct	1725 ms	900340 KB	Output is correct
59	Correct	2045 ms	898584 KB	Output is correct
60	Correct	2327 ms	855468 KB	Output is correct
61	Correct	2353 ms	901404 KB	Output is correct
62	Correct	1852 ms	854776 KB	Output is correct
63	Correct	2041 ms	872660 KB	Output is correct
64	Execution timed out	5048 ms	947676 KB	Time limit exceeded
65	Halted	0 ms	0 KB	-