답안 #732031

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
732031	2023-04-28T09:09:09 Z	minhcool	새 집 (APIO18_new_home)	C++17	57 / 100	5000 ms	158552 KB

new_home

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma,sse,sse2,sse3,sse4,bmi,abm")
#include<bits/stdc++.h>
using namespace std;
 
//#define int long long
#define fi first
#define se second
#define pb push_back
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 3e5 + 5;
const int mod = 1e9 + 7, oo = 1e9 + 7;
 
/*
Algo (Ig)
*/
 
int n, k, q;
 
int a[N], b[N], x[N], t[N];
 
int l[N], y[N];
 
vector<int> times;
 
vector<ii> opes[1048576];
vector<int> asks[N];
multiset<int> mls[N];
 
int mini[1048576], maxi[1048576];
 
vector<int> ask_pos;
 
// get position to add/erase
ii get_pos(int l, int r){
    assert(l <= r);
    int temp1 = lower_bound(ask_pos.begin(), ask_pos.end(), l) - ask_pos.begin();
    int temp2 = upper_bound(ask_pos.begin(), ask_pos.end(), r) - ask_pos.begin();
    temp2--;
    if(temp2 < temp1){
    //	cout << "OK\n";
    //	exit(0);
	}
    //assert(temp2 >= temp1);
    return {temp1, temp2};
}
 
void build(int id, int l, int r){
    mini[id] = oo;
    maxi[id] = -oo;
    if(l == r) return;
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
}
 
iii ope[10000005];
 
int tol = 0, itr = 0;
 
// update the minimum & maximum
void add(int id, int l, int r, int L, int R, int val, int type){
    if(l > R || r < L) return;
    if(l >= L && r <= R){
        if(!type){
        	if(mini[id] <= val) return;
        	tol++;
        	itr++;
        	ope[itr] = {{id, 0}, mini[id]};
        	mini[id] = val;
		}
        else{
        	if(maxi[id] >= val) return;
        	tol++;
        	itr++;
        	ope[itr] = {{id, 1}, maxi[id]};
        	maxi[id] = val;
		}
        //tol++;
        return;
    }
    int mid = (l + r) >> 1;
    add(id << 1, l, mid, L, R, val, type);
    add(id << 1 | 1, mid + 1, r, L, R, val, type);
}
 
// erase the lasest changes
 
 /*
void er(int id, int l, int r, int L, int R, int type){
    if(l > R || r < L || l > r) return;
    if(l >= L && r <= R){
        if(!type){
//            assert(mini[id].size());
            mini[id].pop_back();
        }
        else{
  //          assert(maxi[id].size());
            maxi[id].pop_back();
        }
        return;
    }
    int mid = (l + r) >> 1;
    er(id << 1, l, mid, L, R, type);
    er(id << 1 | 1, mid + 1, r, L, R, type);
}*/
 
int answer[N];
 
ii ans_que = {oo, -oo};
 
// easy query stuff
 
void que(int id, int l, int r, int pos){
    ans_que.fi = min(ans_que.fi, mini[id]);
    ans_que.se = max(ans_que.se, maxi[id]);
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(pos <= mid) que(id << 1, l, mid, pos);
    else que(id << 1 | 1, mid + 1, r, pos);
}
 
// for persistent segment tree
 
void upd(int id, int l, int r, int L, int R, ii v){
    if(l > R || r < L) return;
    if(l >= L && r <= R){
        opes[id].pb(v);
        return;
    }
    int mid = (l + r) >> 1;
    upd(id << 1, l, mid, L, R, v);
    upd(id << 1 | 1, mid + 1, r, L, R, v);
}
 
map<ii, int> answ;// b/c i'm lazy
 
void trav(int id, int l, int r){
    //cout << id << " " << l << " " << r << "\n";
    tol = 0;
    for(auto it : opes[id]){
       // cout << id << " " << l << " " << r << " " << it.fi << " " << it.se << "\n";
      if(mls[it.se].size() == 1){
            add(1, 1, ask_pos.size() - 1, 1, ask_pos.size() - 1, -oo, 0);
            add(1, 1, ask_pos.size() - 1, 1, ask_pos.size() - 1, oo, 1);
            mls[it.se].clear();
            continue;
      }
        multiset<int>::iterator itt = mls[it.se].lower_bound(it.fi), itt2 = itt, itt3;
//        mls[it.se].erase(itt);
  //      continue;
  //       if(itt == mls[it.se].end()) exit(0);
    //    assert(itt != mls[it.se].end());
        itt2++;
        bool ck1 = (itt == mls[it.se].begin()), ck2 = (itt2 == mls[it.se].end());
        if(ck1){// the left side is missing
            int pos = lower_bound(ask_pos.begin(), ask_pos.end(), (*itt2)) - ask_pos.begin();
            pos--;
            if(pos) add(1, 1, ask_pos.size() - 1, 1, pos, (*itt2), 1);
        }
        else if(ck2){// the right side is missing
            itt2--;
            itt2--;
            int pos = lower_bound(ask_pos.begin(), ask_pos.end(), (*itt2)) - ask_pos.begin();
            if(pos < ask_pos.size()) add(1, 1, ask_pos.size() - 1, pos, ask_pos.size() - 1, (*itt2), 0);
        }
        else{
            itt2 = itt3 = itt;
            itt2++; itt3--;
            int md = ((*itt2) + (*itt3)) / 2;
            int pos1 = lower_bound(ask_pos.begin(), ask_pos.end(), (*itt3)) - ask_pos.begin();
            int pos2 = upper_bound(ask_pos.begin(), ask_pos.end(), md) - ask_pos.begin();
            int pos3 = upper_bound(ask_pos.begin(), ask_pos.end(), (*itt2)) - ask_pos.begin();
            pos2--;
            pos3--;
            if(pos1 <= pos2) add(1, 1, ask_pos.size() - 1, pos1, pos2, (*itt3), 0);
            if(pos2 < pos3) add(1, 1, ask_pos.size() - 1, pos2 + 1, pos3, (*itt2), 1);
        }
        mls[it.se].erase(itt);
    }
    int temp = tol;
    if(l == r){
        for(auto it : asks[l]){
            ans_que = {oo, -oo};
            int temp = lower_bound(ask_pos.begin(), ask_pos.end(), it) - ask_pos.begin();
            que(1, 1, ask_pos.size() - 1, temp);
            answ[{times[l], it}] = max(it - ans_que.fi, ans_que.se - it);
        }
    }
    else{
        int mid = (l + r) >> 1;
        trav(id << 1, l, mid);
        trav(id << 1 | 1, mid + 1, r);
    }
    assert(itr >= temp);
    for(auto it : opes[id]) mls[it.se].insert(it.fi);
    for(int i = 1; i <= temp; i++){
    	if(!ope[itr].fi.se) mini[ope[itr].fi.fi] = ope[itr].se;
    	else maxi[ope[itr].fi.fi] = ope[itr].se;
    	itr--;
    	assert(itr >= 0);
	}
    /*
    reverse(opes[id].begin(), opes[id].end());
    for(auto it : opes[id]){
        mls[it.se].insert(it.fi);
        multiset<int>::iterator itt = mls[it.se].lower_bound(it.fi), itt2 = itt, itt3;
        assert(itt != mls[it.se].end());
        itt2++;
        bool ck1 = (itt == mls[it.se].begin()), ck2 = (itt2 == mls[it.se].end());
        if(ck1 && ck2){
            er(1, 1, ask_pos.size() - 1,  1, ask_pos.size() - 1, 0);
            er(1, 1, ask_pos.size() - 1, 1, ask_pos.size() - 1, 1);
            continue;
        }
        else if(ck1){
            int pos = lower_bound(ask_pos.begin(), ask_pos.end(), (*itt2)) - ask_pos.begin();
            pos--;
            if(pos) er(1, 1, ask_pos.size() - 1, 1, pos, 1);
        }
        else if(ck2){
            itt2--;
            itt2--;
            int pos = lower_bound(ask_pos.begin(), ask_pos.end(), (*itt2)) - ask_pos.begin();
            if(pos < ask_pos.size()) er(1, 1, ask_pos.size() - 1, pos, ask_pos.size() - 1, 0);
        }
        else{
            itt2 = itt3 = itt;
            itt2++; itt3--;
            int md = ((*itt2) + (*itt3)) / 2;
            int pos1 = lower_bound(ask_pos.begin(), ask_pos.end(), (*itt3)) - ask_pos.begin();
            int pos2 = upper_bound(ask_pos.begin(), ask_pos.end(), md) - ask_pos.begin();
            int pos3 = upper_bound(ask_pos.begin(), ask_pos.end(), (*itt2)) - ask_pos.begin();
            pos2--;
            pos3--;
            if(pos1 <= pos2) er(1, 1, ask_pos.size() - 1, pos1, pos2, 0);
            if(pos2 < pos3) er(1, 1, ask_pos.size() - 1, pos2 + 1, pos3, 1);
        }
        //mls[it.se].insert(it.fi);
    }*/
}
 
void process(){
    cin >> n >> k >> q;
    for(int i = 1; i <= n; i++) cin >> x[i] >> t[i] >> a[i] >> b[i];
    for(int i = 1; i <= q; i++){
        cin >> l[i] >> y[i];
        ask_pos.pb(l[i]);
    }
    times.pb(0);
    times.pb(1);
    times.pb(1e8);
    /*
    for(int i = 1; i <= n; i++){
        if(a[i] > 2) times.pb(a[i] - 1);
        if((b[i] + 1) < 1e8) times.pb(b[i] + 1);
    }*/
    ask_pos.pb(0);
    sort(ask_pos.begin(), ask_pos.end());
    ask_pos.resize(unique(ask_pos.begin(), ask_pos.end()) - ask_pos.begin());
    // push the erase operations
    for(int i = 1; i <= q; i++) times.pb(y[i]);
    sort(times.begin(), times.end());
    times.resize(unique(times.begin(), times.end()) - times.begin());
    for(int i = 1; i <= n; i++){
        if(a[i] > 1){
            int le = 1, ri = lower_bound(times.begin(), times.end(), a[i]) - times.begin();
            ri--;
            if(le <= ri) upd(1, 1, times.size() - 1, le, ri, {x[i], t[i]});
        }
        if((b[i] + 1 < 1e8)){
            int le = lower_bound(times.begin(), times.end(), b[i] + 1) - times.begin(), ri = times.size() - 1;
            upd(1, 1, times.size() - 1, le, ri, {x[i], t[i]});
        }
    }
    //exit(0);
    // insert the queries
    for(int i = 1; i <= q; i++){
        int temp = lower_bound(times.begin(), times.end(), y[i]) - times.begin();
        asks[temp].pb(l[i]);
    }
    // initialize (not erase anything)
    for(int i = 1; i <= n; i++) mls[t[i]].insert(x[i]);
   // cout << ask_pos.size() - 1 << "\n";
//    exit(0);
    build(1, 1, ask_pos.size() - 1);
    for(int i = 1; i <= k; i++){
        if(!mls[i].size()){
            add(1, 1, ask_pos.size() - 1,  1, ask_pos.size() - 1, -oo, 0);
            add(1, 1, ask_pos.size() - 1, 1, ask_pos.size() - 1, oo, 1);
            continue;
        }
        //continue;
        int lst = -oo;
        int cnt = 0;
        for(multiset<int>::iterator it = mls[i].begin(); it != mls[i].end(); it++){
            int le = 1, ri = 1e8;
            if(it != mls[i].begin()){
                multiset<int>::iterator it2 = it;
                it2--;
                le = ((*it) + (*it2)) / 2 + 1;
            }
            multiset<int>::iterator it2 = it;
            it2++;
            if(it2 != mls[i].end()) ri = ((*it) + (*it2)) / 2;
 //           if(le > ri || le == ask_pos.size()) continue;
            if(le > ri) continue;
            if(le > ask_pos.back()) continue;
            ii temp = get_pos(le, ri);
            if(temp.fi > temp.se) continue;
            temp.se = min(temp.se, (int)ask_pos.size() - 1);
            if(temp.fi > temp.se) continue;
            int posi = lower_bound(ask_pos.begin(), ask_pos.end(), (*it)) - ask_pos.begin();
            if(temp.fi < posi) add(1, 1, ask_pos.size() - 1, temp.fi, posi - 1, (*it), 1);
            if(posi <= temp.se) add(1, 1, ask_pos.size() - 1, posi, temp.se, (*it), 0);
        }
    }
    //cout << (double)clock() / (double)CLOCKS_PER_SEC << "\n";
    //exit(0);
    trav(1, 1, times.size() - 1);
    //cout << (double)clock() / (double)CLOCKS_PER_SEC << "\n";
    for(int i = 1; i <= q; i++) cout << (answ[{y[i], l[i]}] <= 1e8 ? answ[{y[i], l[i]}] : -1) << "\n";
    //cout << (double)clock() / (double)CLOCKS_PER_SEC << "\n";
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    //freopen("test_input.txt", "r", stdin);
    //freopen("test_output.txt", "w", stdout);
    cin.tie(0);
    process();
}

Compilation message

new_home.cpp: In function 'void trav(int, int, int)':
new_home.cpp:170:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |             if(pos < ask_pos.size()) add(1, 1, ask_pos.size() - 1, pos, ask_pos.size() - 1, (*itt2), 0);
      |                ~~~~^~~~~~~~~~~~~~~~
new_home.cpp: In function 'void process()':
new_home.cpp:299:13: warning: unused variable 'lst' [-Wunused-variable]
  299 |         int lst = -oo;
      |             ^~~
new_home.cpp:300:13: warning: unused variable 'cnt' [-Wunused-variable]
  300 |         int cnt = 0;
      |             ^~~

Subtask #1

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	46132 KB	Output is correct
2	Correct	24 ms	46088 KB	Output is correct
3	Correct	26 ms	46096 KB	Output is correct
4	Correct	30 ms	46132 KB	Output is correct
5	Correct	27 ms	46216 KB	Output is correct
6	Correct	30 ms	46284 KB	Output is correct
7	Correct	27 ms	46228 KB	Output is correct
8	Correct	27 ms	46216 KB	Output is correct
9	Correct	28 ms	46292 KB	Output is correct
10	Correct	28 ms	46244 KB	Output is correct
11	Correct	27 ms	46212 KB	Output is correct
12	Correct	28 ms	46292 KB	Output is correct
13	Correct	26 ms	46248 KB	Output is correct
14	Correct	26 ms	46252 KB	Output is correct
15	Correct	26 ms	46200 KB	Output is correct
16	Correct	27 ms	46316 KB	Output is correct
17	Correct	30 ms	46308 KB	Output is correct
18	Correct	28 ms	46224 KB	Output is correct
19	Correct	27 ms	46208 KB	Output is correct
20	Correct	30 ms	46284 KB	Output is correct
21	Correct	26 ms	46108 KB	Output is correct
22	Correct	28 ms	46304 KB	Output is correct
23	Correct	28 ms	46284 KB	Output is correct
24	Correct	29 ms	46292 KB	Output is correct
25	Correct	29 ms	46280 KB	Output is correct
26	Correct	28 ms	46196 KB	Output is correct
27	Correct	26 ms	46236 KB	Output is correct
28	Correct	27 ms	46244 KB	Output is correct
29	Correct	27 ms	46292 KB	Output is correct
30	Correct	27 ms	46232 KB	Output is correct

Subtask #2

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	46132 KB	Output is correct
2	Correct	24 ms	46088 KB	Output is correct
3	Correct	26 ms	46096 KB	Output is correct
4	Correct	30 ms	46132 KB	Output is correct
5	Correct	27 ms	46216 KB	Output is correct
6	Correct	30 ms	46284 KB	Output is correct
7	Correct	27 ms	46228 KB	Output is correct
8	Correct	27 ms	46216 KB	Output is correct
9	Correct	28 ms	46292 KB	Output is correct
10	Correct	28 ms	46244 KB	Output is correct
11	Correct	27 ms	46212 KB	Output is correct
12	Correct	28 ms	46292 KB	Output is correct
13	Correct	26 ms	46248 KB	Output is correct
14	Correct	26 ms	46252 KB	Output is correct
15	Correct	26 ms	46200 KB	Output is correct
16	Correct	27 ms	46316 KB	Output is correct
17	Correct	30 ms	46308 KB	Output is correct
18	Correct	28 ms	46224 KB	Output is correct
19	Correct	27 ms	46208 KB	Output is correct
20	Correct	30 ms	46284 KB	Output is correct
21	Correct	26 ms	46108 KB	Output is correct
22	Correct	28 ms	46304 KB	Output is correct
23	Correct	28 ms	46284 KB	Output is correct
24	Correct	29 ms	46292 KB	Output is correct
25	Correct	29 ms	46280 KB	Output is correct
26	Correct	28 ms	46196 KB	Output is correct
27	Correct	26 ms	46236 KB	Output is correct
28	Correct	27 ms	46244 KB	Output is correct
29	Correct	27 ms	46292 KB	Output is correct
30	Correct	27 ms	46232 KB	Output is correct
31	Correct	1415 ms	76244 KB	Output is correct
32	Correct	183 ms	53964 KB	Output is correct
33	Correct	1349 ms	75560 KB	Output is correct
34	Correct	1360 ms	76792 KB	Output is correct
35	Correct	1379 ms	76136 KB	Output is correct
36	Correct	1367 ms	74984 KB	Output is correct
37	Correct	1167 ms	76404 KB	Output is correct
38	Correct	1105 ms	74444 KB	Output is correct
39	Correct	962 ms	75048 KB	Output is correct
40	Correct	970 ms	74504 KB	Output is correct
41	Correct	973 ms	76816 KB	Output is correct
42	Correct	1036 ms	76076 KB	Output is correct
43	Correct	69 ms	53828 KB	Output is correct
44	Correct	1008 ms	76840 KB	Output is correct
45	Correct	1121 ms	76692 KB	Output is correct
46	Correct	1196 ms	75276 KB	Output is correct
47	Correct	698 ms	74604 KB	Output is correct
48	Correct	727 ms	73848 KB	Output is correct
49	Correct	757 ms	75264 KB	Output is correct
50	Correct	744 ms	76888 KB	Output is correct
51	Correct	869 ms	74592 KB	Output is correct

Subtask #3

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1454 ms	128164 KB	Output is correct
2	Correct	1289 ms	120476 KB	Output is correct
3	Correct	1291 ms	120552 KB	Output is correct
4	Correct	1359 ms	127520 KB	Output is correct
5	Correct	1170 ms	112656 KB	Output is correct
6	Correct	1156 ms	117960 KB	Output is correct
7	Correct	1116 ms	120432 KB	Output is correct
8	Correct	1177 ms	127608 KB	Output is correct
9	Correct	1349 ms	129036 KB	Output is correct
10	Correct	1279 ms	128652 KB	Output is correct
11	Correct	782 ms	122812 KB	Output is correct
12	Correct	866 ms	127972 KB	Output is correct

Subtask #4

0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	5048 ms	158552 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5

35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	46132 KB	Output is correct
2	Correct	24 ms	46088 KB	Output is correct
3	Correct	26 ms	46096 KB	Output is correct
4	Correct	30 ms	46132 KB	Output is correct
5	Correct	27 ms	46216 KB	Output is correct
6	Correct	30 ms	46284 KB	Output is correct
7	Correct	27 ms	46228 KB	Output is correct
8	Correct	27 ms	46216 KB	Output is correct
9	Correct	28 ms	46292 KB	Output is correct
10	Correct	28 ms	46244 KB	Output is correct
11	Correct	27 ms	46212 KB	Output is correct
12	Correct	28 ms	46292 KB	Output is correct
13	Correct	26 ms	46248 KB	Output is correct
14	Correct	26 ms	46252 KB	Output is correct
15	Correct	26 ms	46200 KB	Output is correct
16	Correct	27 ms	46316 KB	Output is correct
17	Correct	30 ms	46308 KB	Output is correct
18	Correct	28 ms	46224 KB	Output is correct
19	Correct	27 ms	46208 KB	Output is correct
20	Correct	30 ms	46284 KB	Output is correct
21	Correct	26 ms	46108 KB	Output is correct
22	Correct	28 ms	46304 KB	Output is correct
23	Correct	28 ms	46284 KB	Output is correct
24	Correct	29 ms	46292 KB	Output is correct
25	Correct	29 ms	46280 KB	Output is correct
26	Correct	28 ms	46196 KB	Output is correct
27	Correct	26 ms	46236 KB	Output is correct
28	Correct	27 ms	46244 KB	Output is correct
29	Correct	27 ms	46292 KB	Output is correct
30	Correct	27 ms	46232 KB	Output is correct
31	Correct	1415 ms	76244 KB	Output is correct
32	Correct	183 ms	53964 KB	Output is correct
33	Correct	1349 ms	75560 KB	Output is correct
34	Correct	1360 ms	76792 KB	Output is correct
35	Correct	1379 ms	76136 KB	Output is correct
36	Correct	1367 ms	74984 KB	Output is correct
37	Correct	1167 ms	76404 KB	Output is correct
38	Correct	1105 ms	74444 KB	Output is correct
39	Correct	962 ms	75048 KB	Output is correct
40	Correct	970 ms	74504 KB	Output is correct
41	Correct	973 ms	76816 KB	Output is correct
42	Correct	1036 ms	76076 KB	Output is correct
43	Correct	69 ms	53828 KB	Output is correct
44	Correct	1008 ms	76840 KB	Output is correct
45	Correct	1121 ms	76692 KB	Output is correct
46	Correct	1196 ms	75276 KB	Output is correct
47	Correct	698 ms	74604 KB	Output is correct
48	Correct	727 ms	73848 KB	Output is correct
49	Correct	757 ms	75264 KB	Output is correct
50	Correct	744 ms	76888 KB	Output is correct
51	Correct	869 ms	74592 KB	Output is correct
52	Correct	387 ms	72216 KB	Output is correct
53	Correct	359 ms	72860 KB	Output is correct
54	Correct	664 ms	73920 KB	Output is correct
55	Correct	717 ms	75412 KB	Output is correct
56	Correct	629 ms	73288 KB	Output is correct
57	Correct	914 ms	76392 KB	Output is correct
58	Correct	792 ms	76068 KB	Output is correct
59	Correct	675 ms	74760 KB	Output is correct
60	Correct	936 ms	76212 KB	Output is correct
61	Correct	72 ms	53968 KB	Output is correct
62	Correct	322 ms	71956 KB	Output is correct
63	Correct	535 ms	73920 KB	Output is correct
64	Correct	588 ms	74552 KB	Output is correct
65	Correct	786 ms	76504 KB	Output is correct
66	Correct	981 ms	76780 KB	Output is correct
67	Correct	193 ms	55848 KB	Output is correct

Subtask #6

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	46132 KB	Output is correct
2	Correct	24 ms	46088 KB	Output is correct
3	Correct	26 ms	46096 KB	Output is correct
4	Correct	30 ms	46132 KB	Output is correct
5	Correct	27 ms	46216 KB	Output is correct
6	Correct	30 ms	46284 KB	Output is correct
7	Correct	27 ms	46228 KB	Output is correct
8	Correct	27 ms	46216 KB	Output is correct
9	Correct	28 ms	46292 KB	Output is correct
10	Correct	28 ms	46244 KB	Output is correct
11	Correct	27 ms	46212 KB	Output is correct
12	Correct	28 ms	46292 KB	Output is correct
13	Correct	26 ms	46248 KB	Output is correct
14	Correct	26 ms	46252 KB	Output is correct
15	Correct	26 ms	46200 KB	Output is correct
16	Correct	27 ms	46316 KB	Output is correct
17	Correct	30 ms	46308 KB	Output is correct
18	Correct	28 ms	46224 KB	Output is correct
19	Correct	27 ms	46208 KB	Output is correct
20	Correct	30 ms	46284 KB	Output is correct
21	Correct	26 ms	46108 KB	Output is correct
22	Correct	28 ms	46304 KB	Output is correct
23	Correct	28 ms	46284 KB	Output is correct
24	Correct	29 ms	46292 KB	Output is correct
25	Correct	29 ms	46280 KB	Output is correct
26	Correct	28 ms	46196 KB	Output is correct
27	Correct	26 ms	46236 KB	Output is correct
28	Correct	27 ms	46244 KB	Output is correct
29	Correct	27 ms	46292 KB	Output is correct
30	Correct	27 ms	46232 KB	Output is correct
31	Correct	1415 ms	76244 KB	Output is correct
32	Correct	183 ms	53964 KB	Output is correct
33	Correct	1349 ms	75560 KB	Output is correct
34	Correct	1360 ms	76792 KB	Output is correct
35	Correct	1379 ms	76136 KB	Output is correct
36	Correct	1367 ms	74984 KB	Output is correct
37	Correct	1167 ms	76404 KB	Output is correct
38	Correct	1105 ms	74444 KB	Output is correct
39	Correct	962 ms	75048 KB	Output is correct
40	Correct	970 ms	74504 KB	Output is correct
41	Correct	973 ms	76816 KB	Output is correct
42	Correct	1036 ms	76076 KB	Output is correct
43	Correct	69 ms	53828 KB	Output is correct
44	Correct	1008 ms	76840 KB	Output is correct
45	Correct	1121 ms	76692 KB	Output is correct
46	Correct	1196 ms	75276 KB	Output is correct
47	Correct	698 ms	74604 KB	Output is correct
48	Correct	727 ms	73848 KB	Output is correct
49	Correct	757 ms	75264 KB	Output is correct
50	Correct	744 ms	76888 KB	Output is correct
51	Correct	869 ms	74592 KB	Output is correct
52	Correct	1454 ms	128164 KB	Output is correct
53	Correct	1289 ms	120476 KB	Output is correct
54	Correct	1291 ms	120552 KB	Output is correct
55	Correct	1359 ms	127520 KB	Output is correct
56	Correct	1170 ms	112656 KB	Output is correct
57	Correct	1156 ms	117960 KB	Output is correct
58	Correct	1116 ms	120432 KB	Output is correct
59	Correct	1177 ms	127608 KB	Output is correct
60	Correct	1349 ms	129036 KB	Output is correct
61	Correct	1279 ms	128652 KB	Output is correct
62	Correct	782 ms	122812 KB	Output is correct
63	Correct	866 ms	127972 KB	Output is correct
64	Execution timed out	5048 ms	158552 KB	Time limit exceeded
65	Halted	0 ms	0 KB	-