oj.uz

답안 #731943

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
731943 2023-04-28T07:14:41 Z minhcool 새 집 (APIO18_new_home) C++17
57 / 100
 5000 ms 247828 KB 
#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];
 
vector<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].push_back(oo);
    maxi[id].push_back(-oo);
    if(l == r) return;
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
}
 
// 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) mini[id].emplace_back(min(mini[id].back(), val));
        else maxi[id].emplace_back(max(maxi[id].back(), val));
        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].back());
    ans_que.se = max(ans_que.se, maxi[id].back());
    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";
    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);
    }
    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);
    }
    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:149:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |             if(pos < ask_pos.size()) add(1, 1, ask_pos.size() - 1, pos, ask_pos.size() - 1, (*itt2), 0);
      |                ~~~~^~~~~~~~~~~~~~~~
new_home.cpp:199:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  199 |             if(pos < ask_pos.size()) er(1, 1, ask_pos.size() - 1, pos, ask_pos.size() - 1, 0);
      |                ~~~~^~~~~~~~~~~~~~~~
new_home.cpp: In function 'void process()':
new_home.cpp:268:13: warning: unused variable 'lst' [-Wunused-variable]
  268 |         int lst = -oo;
      |             ^~~
new_home.cpp:269:13: warning: unused variable 'cnt' [-Wunused-variable]
  269 |         int cnt = 0;
      |             ^~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 95304 KB Output is correct
2 Correct 61 ms 95272 KB Output is correct
3 Correct 56 ms 95280 KB Output is correct
4 Correct 63 ms 95368 KB Output is correct
5 Correct 50 ms 95436 KB Output is correct
6 Correct 55 ms 95512 KB Output is correct
7 Correct 54 ms 95544 KB Output is correct
8 Correct 54 ms 95564 KB Output is correct
9 Correct 69 ms 95564 KB Output is correct
10 Correct 67 ms 95504 KB Output is correct
11 Correct 54 ms 95528 KB Output is correct
12 Correct 53 ms 95512 KB Output is correct
13 Correct 64 ms 95508 KB Output is correct
14 Correct 52 ms 95528 KB Output is correct
15 Correct 52 ms 95592 KB Output is correct
16 Correct 67 ms 95460 KB Output is correct
17 Correct 58 ms 95588 KB Output is correct
18 Correct 56 ms 95552 KB Output is correct
19 Correct 54 ms 95588 KB Output is correct
20 Correct 54 ms 95604 KB Output is correct
21 Correct 48 ms 95376 KB Output is correct
22 Correct 52 ms 95564 KB Output is correct
23 Correct 64 ms 95540 KB Output is correct
24 Correct 50 ms 95588 KB Output is correct
25 Correct 53 ms 95516 KB Output is correct
26 Correct 55 ms 95612 KB Output is correct
27 Correct 54 ms 95492 KB Output is correct
28 Correct 69 ms 95592 KB Output is correct
29 Correct 64 ms 95496 KB Output is correct
30 Correct 52 ms 95564 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 95304 KB Output is correct
2 Correct 61 ms 95272 KB Output is correct
3 Correct 56 ms 95280 KB Output is correct
4 Correct 63 ms 95368 KB Output is correct
5 Correct 50 ms 95436 KB Output is correct
6 Correct 55 ms 95512 KB Output is correct
7 Correct 54 ms 95544 KB Output is correct
8 Correct 54 ms 95564 KB Output is correct
9 Correct 69 ms 95564 KB Output is correct
10 Correct 67 ms 95504 KB Output is correct
11 Correct 54 ms 95528 KB Output is correct
12 Correct 53 ms 95512 KB Output is correct
13 Correct 64 ms 95508 KB Output is correct
14 Correct 52 ms 95528 KB Output is correct
15 Correct 52 ms 95592 KB Output is correct
16 Correct 67 ms 95460 KB Output is correct
17 Correct 58 ms 95588 KB Output is correct
18 Correct 56 ms 95552 KB Output is correct
19 Correct 54 ms 95588 KB Output is correct
20 Correct 54 ms 95604 KB Output is correct
21 Correct 48 ms 95376 KB Output is correct
22 Correct 52 ms 95564 KB Output is correct
23 Correct 64 ms 95540 KB Output is correct
24 Correct 50 ms 95588 KB Output is correct
25 Correct 53 ms 95516 KB Output is correct
26 Correct 55 ms 95612 KB Output is correct
27 Correct 54 ms 95492 KB Output is correct
28 Correct 69 ms 95592 KB Output is correct
29 Correct 64 ms 95496 KB Output is correct
30 Correct 52 ms 95564 KB Output is correct
31 Correct 3849 ms 135128 KB Output is correct
32 Correct 290 ms 103272 KB Output is correct
33 Correct 3158 ms 129760 KB Output is correct
34 Correct 3536 ms 136500 KB Output is correct
35 Correct 3512 ms 133100 KB Output is correct
36 Correct 3066 ms 128724 KB Output is correct
37 Correct 2518 ms 131812 KB Output is correct
38 Correct 2228 ms 128600 KB Output is correct
39 Correct 1834 ms 130236 KB Output is correct
40 Correct 1793 ms 129288 KB Output is correct
41 Correct 2445 ms 139040 KB Output is correct
42 Correct 2415 ms 138932 KB Output is correct
43 Correct 109 ms 102044 KB Output is correct
44 Correct 2565 ms 138896 KB Output is correct
45 Correct 2616 ms 137360 KB Output is correct
46 Correct 2915 ms 134432 KB Output is correct
47 Correct 1322 ms 133776 KB Output is correct
48 Correct 1319 ms 131292 KB Output is correct
49 Correct 1533 ms 132844 KB Output is correct
50 Correct 1601 ms 138060 KB Output is correct
51 Correct 1765 ms 132152 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2618 ms 227580 KB Output is correct
2 Correct 1591 ms 188516 KB Output is correct
3 Correct 1937 ms 220004 KB Output is correct
4 Correct 2482 ms 226916 KB Output is correct
5 Correct 1432 ms 186996 KB Output is correct
6 Correct 1554 ms 187848 KB Output is correct
7 Correct 1923 ms 220296 KB Output is correct
8 Correct 2327 ms 227848 KB Output is correct
9 Correct 2398 ms 227988 KB Output is correct
10 Correct 2169 ms 206016 KB Output is correct
11 Correct 1224 ms 192012 KB Output is correct
12 Correct 1749 ms 204044 KB Output is correct

Subtask #4
0 / 23.0

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

Subtask #5
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 95304 KB Output is correct
2 Correct 61 ms 95272 KB Output is correct
3 Correct 56 ms 95280 KB Output is correct
4 Correct 63 ms 95368 KB Output is correct
5 Correct 50 ms 95436 KB Output is correct
6 Correct 55 ms 95512 KB Output is correct
7 Correct 54 ms 95544 KB Output is correct
8 Correct 54 ms 95564 KB Output is correct
9 Correct 69 ms 95564 KB Output is correct
10 Correct 67 ms 95504 KB Output is correct
11 Correct 54 ms 95528 KB Output is correct
12 Correct 53 ms 95512 KB Output is correct
13 Correct 64 ms 95508 KB Output is correct
14 Correct 52 ms 95528 KB Output is correct
15 Correct 52 ms 95592 KB Output is correct
16 Correct 67 ms 95460 KB Output is correct
17 Correct 58 ms 95588 KB Output is correct
18 Correct 56 ms 95552 KB Output is correct
19 Correct 54 ms 95588 KB Output is correct
20 Correct 54 ms 95604 KB Output is correct
21 Correct 48 ms 95376 KB Output is correct
22 Correct 52 ms 95564 KB Output is correct
23 Correct 64 ms 95540 KB Output is correct
24 Correct 50 ms 95588 KB Output is correct
25 Correct 53 ms 95516 KB Output is correct
26 Correct 55 ms 95612 KB Output is correct
27 Correct 54 ms 95492 KB Output is correct
28 Correct 69 ms 95592 KB Output is correct
29 Correct 64 ms 95496 KB Output is correct
30 Correct 52 ms 95564 KB Output is correct
31 Correct 3849 ms 135128 KB Output is correct
32 Correct 290 ms 103272 KB Output is correct
33 Correct 3158 ms 129760 KB Output is correct
34 Correct 3536 ms 136500 KB Output is correct
35 Correct 3512 ms 133100 KB Output is correct
36 Correct 3066 ms 128724 KB Output is correct
37 Correct 2518 ms 131812 KB Output is correct
38 Correct 2228 ms 128600 KB Output is correct
39 Correct 1834 ms 130236 KB Output is correct
40 Correct 1793 ms 129288 KB Output is correct
41 Correct 2445 ms 139040 KB Output is correct
42 Correct 2415 ms 138932 KB Output is correct
43 Correct 109 ms 102044 KB Output is correct
44 Correct 2565 ms 138896 KB Output is correct
45 Correct 2616 ms 137360 KB Output is correct
46 Correct 2915 ms 134432 KB Output is correct
47 Correct 1322 ms 133776 KB Output is correct
48 Correct 1319 ms 131292 KB Output is correct
49 Correct 1533 ms 132844 KB Output is correct
50 Correct 1601 ms 138060 KB Output is correct
51 Correct 1765 ms 132152 KB Output is correct
52 Correct 539 ms 129672 KB Output is correct
53 Correct 502 ms 130304 KB Output is correct
54 Correct 1599 ms 134312 KB Output is correct
55 Correct 1804 ms 136280 KB Output is correct
56 Correct 1370 ms 133388 KB Output is correct
57 Correct 2251 ms 138072 KB Output is correct
58 Correct 1899 ms 137532 KB Output is correct
59 Correct 1481 ms 135172 KB Output is correct
60 Correct 2384 ms 138620 KB Output is correct
61 Correct 100 ms 102608 KB Output is correct
62 Correct 502 ms 129500 KB Output is correct
63 Correct 1037 ms 133308 KB Output is correct
64 Correct 1328 ms 134948 KB Output is correct
65 Correct 1916 ms 139288 KB Output is correct
66 Correct 2470 ms 139764 KB Output is correct
67 Correct 308 ms 107468 KB Output is correct

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 95304 KB Output is correct
2 Correct 61 ms 95272 KB Output is correct
3 Correct 56 ms 95280 KB Output is correct
4 Correct 63 ms 95368 KB Output is correct
5 Correct 50 ms 95436 KB Output is correct
6 Correct 55 ms 95512 KB Output is correct
7 Correct 54 ms 95544 KB Output is correct
8 Correct 54 ms 95564 KB Output is correct
9 Correct 69 ms 95564 KB Output is correct
10 Correct 67 ms 95504 KB Output is correct
11 Correct 54 ms 95528 KB Output is correct
12 Correct 53 ms 95512 KB Output is correct
13 Correct 64 ms 95508 KB Output is correct
14 Correct 52 ms 95528 KB Output is correct
15 Correct 52 ms 95592 KB Output is correct
16 Correct 67 ms 95460 KB Output is correct
17 Correct 58 ms 95588 KB Output is correct
18 Correct 56 ms 95552 KB Output is correct
19 Correct 54 ms 95588 KB Output is correct
20 Correct 54 ms 95604 KB Output is correct
21 Correct 48 ms 95376 KB Output is correct
22 Correct 52 ms 95564 KB Output is correct
23 Correct 64 ms 95540 KB Output is correct
24 Correct 50 ms 95588 KB Output is correct
25 Correct 53 ms 95516 KB Output is correct
26 Correct 55 ms 95612 KB Output is correct
27 Correct 54 ms 95492 KB Output is correct
28 Correct 69 ms 95592 KB Output is correct
29 Correct 64 ms 95496 KB Output is correct
30 Correct 52 ms 95564 KB Output is correct
31 Correct 3849 ms 135128 KB Output is correct
32 Correct 290 ms 103272 KB Output is correct
33 Correct 3158 ms 129760 KB Output is correct
34 Correct 3536 ms 136500 KB Output is correct
35 Correct 3512 ms 133100 KB Output is correct
36 Correct 3066 ms 128724 KB Output is correct
37 Correct 2518 ms 131812 KB Output is correct
38 Correct 2228 ms 128600 KB Output is correct
39 Correct 1834 ms 130236 KB Output is correct
40 Correct 1793 ms 129288 KB Output is correct
41 Correct 2445 ms 139040 KB Output is correct
42 Correct 2415 ms 138932 KB Output is correct
43 Correct 109 ms 102044 KB Output is correct
44 Correct 2565 ms 138896 KB Output is correct
45 Correct 2616 ms 137360 KB Output is correct
46 Correct 2915 ms 134432 KB Output is correct
47 Correct 1322 ms 133776 KB Output is correct
48 Correct 1319 ms 131292 KB Output is correct
49 Correct 1533 ms 132844 KB Output is correct
50 Correct 1601 ms 138060 KB Output is correct
51 Correct 1765 ms 132152 KB Output is correct
52 Correct 2618 ms 227580 KB Output is correct
53 Correct 1591 ms 188516 KB Output is correct
54 Correct 1937 ms 220004 KB Output is correct
55 Correct 2482 ms 226916 KB Output is correct
56 Correct 1432 ms 186996 KB Output is correct
57 Correct 1554 ms 187848 KB Output is correct
58 Correct 1923 ms 220296 KB Output is correct
59 Correct 2327 ms 227848 KB Output is correct
60 Correct 2398 ms 227988 KB Output is correct
61 Correct 2169 ms 206016 KB Output is correct
62 Correct 1224 ms 192012 KB Output is correct
63 Correct 1749 ms 204044 KB Output is correct
64 Execution timed out 5111 ms 247828 KB Time limit exceeded
65 Halted 0 ms 0 KB -