답안 #731958

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

new_home

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma,sse,sse2,sse3,sse4,bmi")
#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 || l > r) 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";
        multiset<int>::iterator itt = mls[it.se].lower_bound(it.fi), itt2 = itt, itt3;
  //       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 && ck2){// everything turns into -oo and oo
            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].erase(itt);
            continue;
        }
        else 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);
        }
    }
    //exit(0);
    trav(1, 1, times.size() - 1);
    for(int i = 1; i <= q; i++) cout << (answ[{y[i], l[i]}] <= 1e8 ? answ[{y[i], l[i]}] : -1) << "\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:168:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |             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:297:13: warning: unused variable 'lst' [-Wunused-variable]
  297 |         int lst = -oo;
      |             ^~~
new_home.cpp:298:13: warning: unused variable 'cnt' [-Wunused-variable]
  298 |         int cnt = 0;
      |             ^~~

Subtask #1

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	46104 KB	Output is correct
2	Correct	25 ms	46048 KB	Output is correct
3	Correct	26 ms	46056 KB	Output is correct
4	Correct	25 ms	46104 KB	Output is correct
5	Correct	27 ms	46112 KB	Output is correct
6	Correct	27 ms	46308 KB	Output is correct
7	Correct	25 ms	46240 KB	Output is correct
8	Correct	28 ms	46224 KB	Output is correct
9	Correct	26 ms	46312 KB	Output is correct
10	Correct	27 ms	46304 KB	Output is correct
11	Correct	27 ms	46232 KB	Output is correct
12	Correct	28 ms	46196 KB	Output is correct
13	Correct	26 ms	46308 KB	Output is correct
14	Correct	30 ms	46220 KB	Output is correct
15	Correct	27 ms	46272 KB	Output is correct
16	Correct	26 ms	46232 KB	Output is correct
17	Correct	28 ms	46292 KB	Output is correct
18	Correct	26 ms	46292 KB	Output is correct
19	Correct	28 ms	46252 KB	Output is correct
20	Correct	32 ms	46292 KB	Output is correct
21	Correct	28 ms	46292 KB	Output is correct
22	Correct	26 ms	46292 KB	Output is correct
23	Correct	26 ms	46236 KB	Output is correct
24	Correct	27 ms	46276 KB	Output is correct
25	Correct	27 ms	46308 KB	Output is correct
26	Correct	29 ms	46292 KB	Output is correct
27	Correct	31 ms	46252 KB	Output is correct
28	Correct	29 ms	46264 KB	Output is correct
29	Correct	27 ms	46244 KB	Output is correct
30	Correct	29 ms	46288 KB	Output is correct

Subtask #2

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	46104 KB	Output is correct
2	Correct	25 ms	46048 KB	Output is correct
3	Correct	26 ms	46056 KB	Output is correct
4	Correct	25 ms	46104 KB	Output is correct
5	Correct	27 ms	46112 KB	Output is correct
6	Correct	27 ms	46308 KB	Output is correct
7	Correct	25 ms	46240 KB	Output is correct
8	Correct	28 ms	46224 KB	Output is correct
9	Correct	26 ms	46312 KB	Output is correct
10	Correct	27 ms	46304 KB	Output is correct
11	Correct	27 ms	46232 KB	Output is correct
12	Correct	28 ms	46196 KB	Output is correct
13	Correct	26 ms	46308 KB	Output is correct
14	Correct	30 ms	46220 KB	Output is correct
15	Correct	27 ms	46272 KB	Output is correct
16	Correct	26 ms	46232 KB	Output is correct
17	Correct	28 ms	46292 KB	Output is correct
18	Correct	26 ms	46292 KB	Output is correct
19	Correct	28 ms	46252 KB	Output is correct
20	Correct	32 ms	46292 KB	Output is correct
21	Correct	28 ms	46292 KB	Output is correct
22	Correct	26 ms	46292 KB	Output is correct
23	Correct	26 ms	46236 KB	Output is correct
24	Correct	27 ms	46276 KB	Output is correct
25	Correct	27 ms	46308 KB	Output is correct
26	Correct	29 ms	46292 KB	Output is correct
27	Correct	31 ms	46252 KB	Output is correct
28	Correct	29 ms	46264 KB	Output is correct
29	Correct	27 ms	46244 KB	Output is correct
30	Correct	29 ms	46288 KB	Output is correct
31	Correct	1417 ms	73644 KB	Output is correct
32	Correct	190 ms	53452 KB	Output is correct
33	Correct	1309 ms	73144 KB	Output is correct
34	Correct	1326 ms	74244 KB	Output is correct
35	Correct	1328 ms	73692 KB	Output is correct
36	Correct	1329 ms	72720 KB	Output is correct
37	Correct	1184 ms	73936 KB	Output is correct
38	Correct	1146 ms	72268 KB	Output is correct
39	Correct	912 ms	72524 KB	Output is correct
40	Correct	952 ms	71924 KB	Output is correct
41	Correct	985 ms	74148 KB	Output is correct
42	Correct	980 ms	73380 KB	Output is correct
43	Correct	88 ms	51856 KB	Output is correct
44	Correct	963 ms	74360 KB	Output is correct
45	Correct	1012 ms	74072 KB	Output is correct
46	Correct	1132 ms	72772 KB	Output is correct
47	Correct	666 ms	71956 KB	Output is correct
48	Correct	673 ms	71296 KB	Output is correct
49	Correct	760 ms	72748 KB	Output is correct
50	Correct	726 ms	74228 KB	Output is correct
51	Correct	841 ms	72064 KB	Output is correct

Subtask #3

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1355 ms	126188 KB	Output is correct
2	Correct	1172 ms	118444 KB	Output is correct
3	Correct	1138 ms	118140 KB	Output is correct
4	Correct	1336 ms	125220 KB	Output is correct
5	Correct	1095 ms	110284 KB	Output is correct
6	Correct	1151 ms	115560 KB	Output is correct
7	Correct	1085 ms	118028 KB	Output is correct
8	Correct	1231 ms	125080 KB	Output is correct
9	Correct	1254 ms	126548 KB	Output is correct
10	Correct	1179 ms	126000 KB	Output is correct
11	Correct	733 ms	120480 KB	Output is correct
12	Correct	865 ms	125556 KB	Output is correct

Subtask #4

0 / 23.0

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

Subtask #5

35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	46104 KB	Output is correct
2	Correct	25 ms	46048 KB	Output is correct
3	Correct	26 ms	46056 KB	Output is correct
4	Correct	25 ms	46104 KB	Output is correct
5	Correct	27 ms	46112 KB	Output is correct
6	Correct	27 ms	46308 KB	Output is correct
7	Correct	25 ms	46240 KB	Output is correct
8	Correct	28 ms	46224 KB	Output is correct
9	Correct	26 ms	46312 KB	Output is correct
10	Correct	27 ms	46304 KB	Output is correct
11	Correct	27 ms	46232 KB	Output is correct
12	Correct	28 ms	46196 KB	Output is correct
13	Correct	26 ms	46308 KB	Output is correct
14	Correct	30 ms	46220 KB	Output is correct
15	Correct	27 ms	46272 KB	Output is correct
16	Correct	26 ms	46232 KB	Output is correct
17	Correct	28 ms	46292 KB	Output is correct
18	Correct	26 ms	46292 KB	Output is correct
19	Correct	28 ms	46252 KB	Output is correct
20	Correct	32 ms	46292 KB	Output is correct
21	Correct	28 ms	46292 KB	Output is correct
22	Correct	26 ms	46292 KB	Output is correct
23	Correct	26 ms	46236 KB	Output is correct
24	Correct	27 ms	46276 KB	Output is correct
25	Correct	27 ms	46308 KB	Output is correct
26	Correct	29 ms	46292 KB	Output is correct
27	Correct	31 ms	46252 KB	Output is correct
28	Correct	29 ms	46264 KB	Output is correct
29	Correct	27 ms	46244 KB	Output is correct
30	Correct	29 ms	46288 KB	Output is correct
31	Correct	1417 ms	73644 KB	Output is correct
32	Correct	190 ms	53452 KB	Output is correct
33	Correct	1309 ms	73144 KB	Output is correct
34	Correct	1326 ms	74244 KB	Output is correct
35	Correct	1328 ms	73692 KB	Output is correct
36	Correct	1329 ms	72720 KB	Output is correct
37	Correct	1184 ms	73936 KB	Output is correct
38	Correct	1146 ms	72268 KB	Output is correct
39	Correct	912 ms	72524 KB	Output is correct
40	Correct	952 ms	71924 KB	Output is correct
41	Correct	985 ms	74148 KB	Output is correct
42	Correct	980 ms	73380 KB	Output is correct
43	Correct	88 ms	51856 KB	Output is correct
44	Correct	963 ms	74360 KB	Output is correct
45	Correct	1012 ms	74072 KB	Output is correct
46	Correct	1132 ms	72772 KB	Output is correct
47	Correct	666 ms	71956 KB	Output is correct
48	Correct	673 ms	71296 KB	Output is correct
49	Correct	760 ms	72748 KB	Output is correct
50	Correct	726 ms	74228 KB	Output is correct
51	Correct	841 ms	72064 KB	Output is correct
52	Correct	329 ms	69452 KB	Output is correct
53	Correct	335 ms	69952 KB	Output is correct
54	Correct	681 ms	71184 KB	Output is correct
55	Correct	689 ms	72628 KB	Output is correct
56	Correct	599 ms	70468 KB	Output is correct
57	Correct	882 ms	73680 KB	Output is correct
58	Correct	728 ms	73552 KB	Output is correct
59	Correct	612 ms	71768 KB	Output is correct
60	Correct	871 ms	73532 KB	Output is correct
61	Correct	72 ms	51908 KB	Output is correct
62	Correct	313 ms	69232 KB	Output is correct
63	Correct	558 ms	71020 KB	Output is correct
64	Correct	594 ms	71980 KB	Output is correct
65	Correct	743 ms	73824 KB	Output is correct
66	Correct	946 ms	74076 KB	Output is correct
67	Correct	186 ms	54744 KB	Output is correct

Subtask #6

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	46104 KB	Output is correct
2	Correct	25 ms	46048 KB	Output is correct
3	Correct	26 ms	46056 KB	Output is correct
4	Correct	25 ms	46104 KB	Output is correct
5	Correct	27 ms	46112 KB	Output is correct
6	Correct	27 ms	46308 KB	Output is correct
7	Correct	25 ms	46240 KB	Output is correct
8	Correct	28 ms	46224 KB	Output is correct
9	Correct	26 ms	46312 KB	Output is correct
10	Correct	27 ms	46304 KB	Output is correct
11	Correct	27 ms	46232 KB	Output is correct
12	Correct	28 ms	46196 KB	Output is correct
13	Correct	26 ms	46308 KB	Output is correct
14	Correct	30 ms	46220 KB	Output is correct
15	Correct	27 ms	46272 KB	Output is correct
16	Correct	26 ms	46232 KB	Output is correct
17	Correct	28 ms	46292 KB	Output is correct
18	Correct	26 ms	46292 KB	Output is correct
19	Correct	28 ms	46252 KB	Output is correct
20	Correct	32 ms	46292 KB	Output is correct
21	Correct	28 ms	46292 KB	Output is correct
22	Correct	26 ms	46292 KB	Output is correct
23	Correct	26 ms	46236 KB	Output is correct
24	Correct	27 ms	46276 KB	Output is correct
25	Correct	27 ms	46308 KB	Output is correct
26	Correct	29 ms	46292 KB	Output is correct
27	Correct	31 ms	46252 KB	Output is correct
28	Correct	29 ms	46264 KB	Output is correct
29	Correct	27 ms	46244 KB	Output is correct
30	Correct	29 ms	46288 KB	Output is correct
31	Correct	1417 ms	73644 KB	Output is correct
32	Correct	190 ms	53452 KB	Output is correct
33	Correct	1309 ms	73144 KB	Output is correct
34	Correct	1326 ms	74244 KB	Output is correct
35	Correct	1328 ms	73692 KB	Output is correct
36	Correct	1329 ms	72720 KB	Output is correct
37	Correct	1184 ms	73936 KB	Output is correct
38	Correct	1146 ms	72268 KB	Output is correct
39	Correct	912 ms	72524 KB	Output is correct
40	Correct	952 ms	71924 KB	Output is correct
41	Correct	985 ms	74148 KB	Output is correct
42	Correct	980 ms	73380 KB	Output is correct
43	Correct	88 ms	51856 KB	Output is correct
44	Correct	963 ms	74360 KB	Output is correct
45	Correct	1012 ms	74072 KB	Output is correct
46	Correct	1132 ms	72772 KB	Output is correct
47	Correct	666 ms	71956 KB	Output is correct
48	Correct	673 ms	71296 KB	Output is correct
49	Correct	760 ms	72748 KB	Output is correct
50	Correct	726 ms	74228 KB	Output is correct
51	Correct	841 ms	72064 KB	Output is correct
52	Correct	1355 ms	126188 KB	Output is correct
53	Correct	1172 ms	118444 KB	Output is correct
54	Correct	1138 ms	118140 KB	Output is correct
55	Correct	1336 ms	125220 KB	Output is correct
56	Correct	1095 ms	110284 KB	Output is correct
57	Correct	1151 ms	115560 KB	Output is correct
58	Correct	1085 ms	118028 KB	Output is correct
59	Correct	1231 ms	125080 KB	Output is correct
60	Correct	1254 ms	126548 KB	Output is correct
61	Correct	1179 ms	126000 KB	Output is correct
62	Correct	733 ms	120480 KB	Output is correct
63	Correct	865 ms	125556 KB	Output is correct
64	Execution timed out	5035 ms	157036 KB	Time limit exceeded
65	Halted	0 ms	0 KB	-