oj.uz

Submission #626906

# Submission time Handle Problem Language Result Execution time Memory
626906 2022-08-12T00:29:03 Z tlwpdus Radio Towers (IOI22_towers) C++17
77 / 100
 4000 ms 729324 KB 
#include "towers.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int INF = 0x3f3f3f3f;

struct PersSeg {
    vector<int> tree;
    vector<int> le;
    vector<int> ri;
    vector<int> roots;
    int n;
    int _init(int s, int e) {
        int p =tree.size();
        tree.push_back(0);
        le.push_back(-1);
        ri.push_back(-1);
        return p;
    }
    void init(int _n) {
        n = _n;
        if (n==0) return;
        roots.push_back(_init(0,n-1));
    }
    int _tree(int idx) {return idx==-1?0:tree[idx];}
    int _le(int idx) {return idx==-1?-1:le[idx];}
    int _ri(int idx) {return idx==-1?-1:ri[idx];}
    int upd(int idx, int val, int s, int e, int ori) {
        if (idx<s||e<idx) {
            return ori;
        }
        if (s==e) {
            int p = tree.size();
            tree.push_back(_tree(ori)+val);
            le.push_back(-1);
            ri.push_back(-1);
            return p;
        }
        int m =(s+e)/2;
        int l = upd(idx,val,s,m,_le(ori));
        int r = upd(idx,val,m+1,e,_ri(ori));
        int p = tree.size();
        tree.push_back(_tree(ori)+val);
        le.push_back(l);
        ri.push_back(r);
        return p;
    }
    void upd(int idx, int val) {
        if (n==0) return;
        int root = upd(idx, val, 0, n-1, roots.back());
        roots.push_back(root);
    }
    int getv(int S, int E, int s, int e, int ori) {
        if (e<S||E<s||ori==-1) return 0;
        if (S<=s&&e<=E) return _tree(ori);
        int m = (s+e)/2;
        return getv(S,E,s,m,_le(ori))+getv(S,E,m+1,e,_ri(ori));
    }
    int getv(int S, int E, int ori) {
        return getv(S,E,0,n-1,ori);
    }
};

struct Seg {
    vector<pii> tree[270000]; // v, r
    vector<int> comp[270000]; // r
    vector<int> rootnum[270000];
    PersSeg per[270000];
    const int key = 131072;
    void upd(int idx, pii p) {
        idx += key;
        while(idx) {
            tree[idx].push_back(p);
            idx/=2;
        }
    }
    void calc() {
        for (int i=1;i<key*2;i++) {
            sort(tree[i].begin(),tree[i].end());
            for (pii &p : tree[i]) {
                comp[i].push_back(p.second);
            }
            sort(comp[i].begin(),comp[i].end());
            comp[i].erase(unique(comp[i].begin(),comp[i].end()),comp[i].end());
            per[i].init(tree[i].size());
            rootnum[i].assign(tree[i].size(),0);
            for (int j=(int)tree[i].size()-1;j>=0;j--) {
                int r = lower_bound(comp[i].begin(),comp[i].end(),tree[i][j].second)-comp[i].begin();
                per[i].upd(r,1);
                rootnum[i][j] = per[i].roots.back();
            }
        }
    }
    int _getv(int i, int d, int rs, int re) {
        int t =lower_bound(tree[i].begin(),tree[i].end(),pii(d,-1))-tree[i].begin();
        if (t==tree[i].size()) return 0;
        rs = lower_bound(comp[i].begin(),comp[i].end(),rs)-comp[i].begin();
        re = upper_bound(comp[i].begin(),comp[i].end(),re)-comp[i].begin()-1;
        return per[i].getv(rs,re,rootnum[i][t]);
    }
    int getv(int s, int e, int d, int rs, int re) {
        s += key; e += key;
        int ans = 0;
        while(s<=e) {
            if (s&1) {
                ans += _getv(s,d,rs,re);
            }
            if (~e&1) {
                ans += _getv(e,d,rs,re);
            }
            s = (s+1)/2;
            e = (e-1)/2;
        }
        return ans;
    }
} itr, itl;

struct Idxtree {
    int tree[270000];
    const int key = 131072;
    void init() {
        memset(tree,0x3f,sizeof(tree));
    }
    void upd(int idx, int val) {
        idx += key;
        while(idx) {
            tree[idx] = min(tree[idx],val);
            idx/=2;
        }
    }
    int getv(int s, int e) {
        s += key;
        e += key;
        int ans = INF;
        while(s<=e) {
            if (s&1) ans = min(ans,tree[s]);
            if (~e&1) ans = min(ans,tree[e]);
            s = (s+1)/2;
            e = (e-1)/2;
        }
        return ans;
    }
} ith;

struct MIdxtree {
    int tree[270000];
    const int key = 131072;
    void init() {
        memset(tree,0,sizeof(tree));
    }
    void upd(int idx, int val) {
        idx += key;
        while(idx) {
            tree[idx] = max(tree[idx],val);
            idx/=2;
        }
    }
    int getv(int s, int e) {
        s += key;
        e += key;
        int ans = 0;
        while(s<=e) {
            if (s&1) ans = max(ans,tree[s]);
            if (~e&1) ans = max(ans,tree[e]);
            s = (s+1)/2;
            e = (e-1)/2;
        }
        return ans;
    }
} ithm;

int N;
vector<int> H;
int pr[100100], pl[100100];
int l[100100], r[100100];
map<int,int> loc;

void init(int _N, vector<int> _H) {
    N = _N;
    H = _H;
    ith.init();
    ithm.init();
    for (int i=0;i<N;i++) {
        ith.upd(i,H[i]);
        ithm.upd(i,H[i]);
        loc[H[i]] = i;
    }
    vector<int> st;
    for (int i=0;i<=N;i++) {
        int h = (i==N?INF:H[i]);
        while(!st.empty()&&H[st.back()]<h) {
            pr[st.back()] = i;
            r[st.back()] = H[st.back()] - ith.getv(st.back(),i-1);
            st.pop_back();
        }
        st.push_back(i);
    }
    st.clear();
    for (int i=N-1;i>=-1;i--) {
        int h = (i==-1?INF:H[i]);
        while(!st.empty()&&H[st.back()]<h) {
            pl[st.back()] = i;
            l[st.back()] = H[st.back()] - ith.getv(i+1, st.back());
            st.pop_back();
        }
        st.push_back(i);
    }
    for (int i=0;i<N;i++) {
        itr.upd(i, {min(l[i],r[i]), pr[i]});
        itl.upd(i, {min(l[i],r[i]),pl[i]});
    }
    itl.calc();
    itr.calc();
}

int max_towers(int L, int R, int D) {
    int ans = itr.getv(L, R, D, 0, N)+1;
    int maxih = ithm.getv(L,R);
    int m = loc[maxih];
    int minih = ith.getv(L,R);
    if (maxih-minih<D) return 1;
    {
        int s = m, e = R;
        while(s<=e) {
            int mid = (s+e)/2;
            if (ithm.getv(mid,R)-ith.getv(mid,R)>=D) s = mid+1;
            else e = mid-1;
        }
        ans -= itr.getv(s,R,D,R+1,N);
    }
    {
        int s = L, e = m;
        while(s<=e) {
            int mid = (s+e)/2;
            if (ithm.getv(L,mid)-ith.getv(L,mid)>=D) e = mid-1;
            else s = mid+1;
        }
        ans -= itl.getv(L,e,D,-1,L-1);
    }

    return ans;
}

Compilation message

towers.cpp: In member function 'int Seg::_getv(int, int, int, int)':
towers.cpp:102:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         if (t==tree[i].size()) return 0;
      |             ~^~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1399 ms 467072 KB Output is correct
2 Correct 2846 ms 729124 KB Output is correct
3 Correct 2850 ms 728976 KB Output is correct
4 Correct 2725 ms 729136 KB Output is correct
5 Correct 2432 ms 729144 KB Output is correct
6 Correct 2607 ms 729100 KB Output is correct
7 Correct 2589 ms 729248 KB Output is correct
8 Correct 52 ms 95376 KB Output is correct
9 Correct 75 ms 107208 KB Output is correct
10 Correct 77 ms 107216 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 97904 KB Output is correct
2 Correct 80 ms 107304 KB Output is correct
3 Correct 79 ms 107312 KB Output is correct
4 Correct 81 ms 107220 KB Output is correct
5 Correct 81 ms 107188 KB Output is correct
6 Correct 84 ms 107180 KB Output is correct
7 Correct 81 ms 107228 KB Output is correct
8 Correct 75 ms 107296 KB Output is correct
9 Correct 80 ms 107244 KB Output is correct
10 Correct 79 ms 107248 KB Output is correct
11 Correct 76 ms 107232 KB Output is correct
12 Correct 50 ms 95428 KB Output is correct
13 Correct 78 ms 107308 KB Output is correct
14 Correct 73 ms 107324 KB Output is correct
15 Correct 83 ms 107312 KB Output is correct
16 Correct 79 ms 107188 KB Output is correct
17 Correct 82 ms 107244 KB Output is correct
18 Correct 74 ms 107424 KB Output is correct
19 Correct 74 ms 107268 KB Output is correct
20 Correct 82 ms 107300 KB Output is correct
21 Correct 83 ms 107472 KB Output is correct
22 Correct 80 ms 107260 KB Output is correct
23 Correct 74 ms 107356 KB Output is correct
24 Correct 76 ms 107304 KB Output is correct
25 Correct 63 ms 100636 KB Output is correct
26 Correct 80 ms 107268 KB Output is correct
27 Correct 82 ms 107216 KB Output is correct
28 Correct 84 ms 107216 KB Output is correct
29 Correct 82 ms 107256 KB Output is correct
30 Correct 80 ms 107284 KB Output is correct
31 Correct 80 ms 107300 KB Output is correct
32 Correct 74 ms 107228 KB Output is correct
33 Correct 74 ms 107304 KB Output is correct
34 Correct 82 ms 107296 KB Output is correct
35 Correct 81 ms 107196 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 97904 KB Output is correct
2 Correct 80 ms 107304 KB Output is correct
3 Correct 79 ms 107312 KB Output is correct
4 Correct 81 ms 107220 KB Output is correct
5 Correct 81 ms 107188 KB Output is correct
6 Correct 84 ms 107180 KB Output is correct
7 Correct 81 ms 107228 KB Output is correct
8 Correct 75 ms 107296 KB Output is correct
9 Correct 80 ms 107244 KB Output is correct
10 Correct 79 ms 107248 KB Output is correct
11 Correct 76 ms 107232 KB Output is correct
12 Correct 50 ms 95428 KB Output is correct
13 Correct 78 ms 107308 KB Output is correct
14 Correct 73 ms 107324 KB Output is correct
15 Correct 83 ms 107312 KB Output is correct
16 Correct 79 ms 107188 KB Output is correct
17 Correct 82 ms 107244 KB Output is correct
18 Correct 74 ms 107424 KB Output is correct
19 Correct 74 ms 107268 KB Output is correct
20 Correct 82 ms 107300 KB Output is correct
21 Correct 83 ms 107472 KB Output is correct
22 Correct 80 ms 107260 KB Output is correct
23 Correct 74 ms 107356 KB Output is correct
24 Correct 76 ms 107304 KB Output is correct
25 Correct 63 ms 100636 KB Output is correct
26 Correct 80 ms 107268 KB Output is correct
27 Correct 82 ms 107216 KB Output is correct
28 Correct 84 ms 107216 KB Output is correct
29 Correct 82 ms 107256 KB Output is correct
30 Correct 80 ms 107284 KB Output is correct
31 Correct 80 ms 107300 KB Output is correct
32 Correct 74 ms 107228 KB Output is correct
33 Correct 74 ms 107304 KB Output is correct
34 Correct 82 ms 107296 KB Output is correct
35 Correct 81 ms 107196 KB Output is correct
36 Correct 1101 ms 506036 KB Output is correct
37 Correct 1658 ms 728176 KB Output is correct
38 Correct 1643 ms 728248 KB Output is correct
39 Correct 1656 ms 728248 KB Output is correct
40 Correct 1671 ms 728084 KB Output is correct
41 Correct 1661 ms 728096 KB Output is correct
42 Correct 1668 ms 728200 KB Output is correct
43 Correct 1323 ms 729276 KB Output is correct
44 Correct 1308 ms 729144 KB Output is correct
45 Correct 1336 ms 728968 KB Output is correct
46 Correct 1340 ms 729160 KB Output is correct
47 Correct 1643 ms 728244 KB Output is correct
48 Correct 1676 ms 728224 KB Output is correct
49 Correct 1672 ms 728180 KB Output is correct
50 Correct 1335 ms 729180 KB Output is correct
51 Correct 1366 ms 729112 KB Output is correct
52 Correct 1655 ms 728344 KB Output is correct
53 Correct 1671 ms 728072 KB Output is correct
54 Correct 1670 ms 728388 KB Output is correct
55 Correct 1321 ms 729060 KB Output is correct
56 Correct 1337 ms 729144 KB Output is correct
57 Correct 1594 ms 702016 KB Output is correct
58 Correct 1664 ms 728284 KB Output is correct
59 Correct 1651 ms 728116 KB Output is correct
60 Correct 1685 ms 728164 KB Output is correct
61 Correct 1675 ms 728152 KB Output is correct
62 Correct 1695 ms 728364 KB Output is correct
63 Correct 1661 ms 728160 KB Output is correct
64 Correct 1323 ms 729112 KB Output is correct
65 Correct 1306 ms 729124 KB Output is correct
66 Correct 1332 ms 729276 KB Output is correct
67 Correct 1350 ms 728800 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3069 ms 724992 KB Output is correct
2 Correct 3728 ms 728444 KB Output is correct
3 Correct 3320 ms 728208 KB Output is correct
4 Correct 3576 ms 728228 KB Output is correct
5 Correct 3459 ms 728324 KB Output is correct
6 Correct 3609 ms 728252 KB Output is correct
7 Correct 3482 ms 728072 KB Output is correct
8 Correct 2565 ms 729132 KB Output is correct
9 Correct 2656 ms 729200 KB Output is correct
10 Correct 2817 ms 728972 KB Output is correct
11 Correct 2587 ms 728800 KB Output is correct
12 Correct 2452 ms 729216 KB Output is correct
13 Correct 2509 ms 729056 KB Output is correct
14 Correct 51 ms 95352 KB Output is correct
15 Correct 75 ms 107296 KB Output is correct
16 Correct 74 ms 107272 KB Output is correct
17 Correct 1642 ms 728344 KB Output is correct
18 Correct 1659 ms 728120 KB Output is correct
19 Correct 1649 ms 728264 KB Output is correct
20 Correct 1308 ms 729104 KB Output is correct
21 Correct 1362 ms 729208 KB Output is correct
22 Correct 1630 ms 728296 KB Output is correct
23 Correct 1680 ms 728368 KB Output is correct
24 Correct 1676 ms 728068 KB Output is correct
25 Correct 1612 ms 729028 KB Output is correct
26 Correct 1382 ms 729080 KB Output is correct
27 Correct 81 ms 107304 KB Output is correct
28 Correct 81 ms 107296 KB Output is correct
29 Correct 91 ms 107200 KB Output is correct
30 Correct 76 ms 107312 KB Output is correct
31 Correct 76 ms 107304 KB Output is correct
32 Correct 82 ms 107304 KB Output is correct
33 Correct 82 ms 107240 KB Output is correct
34 Correct 81 ms 107224 KB Output is correct
35 Correct 75 ms 107200 KB Output is correct
36 Correct 76 ms 107308 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 775 ms 244464 KB Output is correct
2 Correct 3128 ms 728340 KB Output is correct
3 Correct 2960 ms 728236 KB Output is correct
4 Correct 3004 ms 728240 KB Output is correct
5 Correct 2588 ms 728096 KB Output is correct
6 Correct 2828 ms 728112 KB Output is correct
7 Correct 2891 ms 728472 KB Output is correct
8 Correct 2641 ms 729176 KB Output is correct
9 Correct 2733 ms 729196 KB Output is correct
10 Correct 2334 ms 729036 KB Output is correct
11 Correct 2174 ms 729092 KB Output is correct
12 Correct 1629 ms 728140 KB Output is correct
13 Correct 1671 ms 728108 KB Output is correct
14 Correct 1659 ms 728112 KB Output is correct
15 Correct 1322 ms 729140 KB Output is correct
16 Correct 1330 ms 729288 KB Output is correct
17 Correct 1574 ms 701964 KB Output is correct
18 Correct 1638 ms 728196 KB Output is correct
19 Correct 1637 ms 728348 KB Output is correct
20 Correct 1665 ms 728172 KB Output is correct
21 Correct 1666 ms 728268 KB Output is correct
22 Correct 1666 ms 728296 KB Output is correct
23 Correct 1692 ms 728168 KB Output is correct
24 Correct 1398 ms 729212 KB Output is correct
25 Correct 1325 ms 729324 KB Output is correct
26 Correct 1332 ms 729032 KB Output is correct
27 Correct 1363 ms 728904 KB Output is correct
28 Correct 88 ms 107288 KB Output is correct
29 Correct 82 ms 107296 KB Output is correct
30 Correct 79 ms 107216 KB Output is correct
31 Correct 78 ms 107220 KB Output is correct
32 Correct 77 ms 107248 KB Output is correct
33 Correct 63 ms 100672 KB Output is correct
34 Correct 80 ms 107280 KB Output is correct
35 Correct 80 ms 107264 KB Output is correct
36 Correct 80 ms 107284 KB Output is correct
37 Correct 82 ms 107308 KB Output is correct
38 Correct 80 ms 107296 KB Output is correct
39 Correct 80 ms 107232 KB Output is correct
40 Correct 78 ms 107292 KB Output is correct
41 Correct 74 ms 107204 KB Output is correct
42 Correct 76 ms 107312 KB Output is correct
43 Correct 76 ms 107212 KB Output is correct

Subtask #6
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 97904 KB Output is correct
2 Correct 80 ms 107304 KB Output is correct
3 Correct 79 ms 107312 KB Output is correct
4 Correct 81 ms 107220 KB Output is correct
5 Correct 81 ms 107188 KB Output is correct
6 Correct 84 ms 107180 KB Output is correct
7 Correct 81 ms 107228 KB Output is correct
8 Correct 75 ms 107296 KB Output is correct
9 Correct 80 ms 107244 KB Output is correct
10 Correct 79 ms 107248 KB Output is correct
11 Correct 76 ms 107232 KB Output is correct
12 Correct 50 ms 95428 KB Output is correct
13 Correct 78 ms 107308 KB Output is correct
14 Correct 73 ms 107324 KB Output is correct
15 Correct 83 ms 107312 KB Output is correct
16 Correct 79 ms 107188 KB Output is correct
17 Correct 82 ms 107244 KB Output is correct
18 Correct 74 ms 107424 KB Output is correct
19 Correct 74 ms 107268 KB Output is correct
20 Correct 82 ms 107300 KB Output is correct
21 Correct 83 ms 107472 KB Output is correct
22 Correct 80 ms 107260 KB Output is correct
23 Correct 74 ms 107356 KB Output is correct
24 Correct 76 ms 107304 KB Output is correct
25 Correct 63 ms 100636 KB Output is correct
26 Correct 80 ms 107268 KB Output is correct
27 Correct 82 ms 107216 KB Output is correct
28 Correct 84 ms 107216 KB Output is correct
29 Correct 82 ms 107256 KB Output is correct
30 Correct 80 ms 107284 KB Output is correct
31 Correct 80 ms 107300 KB Output is correct
32 Correct 74 ms 107228 KB Output is correct
33 Correct 74 ms 107304 KB Output is correct
34 Correct 82 ms 107296 KB Output is correct
35 Correct 81 ms 107196 KB Output is correct
36 Correct 1101 ms 506036 KB Output is correct
37 Correct 1658 ms 728176 KB Output is correct
38 Correct 1643 ms 728248 KB Output is correct
39 Correct 1656 ms 728248 KB Output is correct
40 Correct 1671 ms 728084 KB Output is correct
41 Correct 1661 ms 728096 KB Output is correct
42 Correct 1668 ms 728200 KB Output is correct
43 Correct 1323 ms 729276 KB Output is correct
44 Correct 1308 ms 729144 KB Output is correct
45 Correct 1336 ms 728968 KB Output is correct
46 Correct 1340 ms 729160 KB Output is correct
47 Correct 1643 ms 728244 KB Output is correct
48 Correct 1676 ms 728224 KB Output is correct
49 Correct 1672 ms 728180 KB Output is correct
50 Correct 1335 ms 729180 KB Output is correct
51 Correct 1366 ms 729112 KB Output is correct
52 Correct 1655 ms 728344 KB Output is correct
53 Correct 1671 ms 728072 KB Output is correct
54 Correct 1670 ms 728388 KB Output is correct
55 Correct 1321 ms 729060 KB Output is correct
56 Correct 1337 ms 729144 KB Output is correct
57 Correct 1594 ms 702016 KB Output is correct
58 Correct 1664 ms 728284 KB Output is correct
59 Correct 1651 ms 728116 KB Output is correct
60 Correct 1685 ms 728164 KB Output is correct
61 Correct 1675 ms 728152 KB Output is correct
62 Correct 1695 ms 728364 KB Output is correct
63 Correct 1661 ms 728160 KB Output is correct
64 Correct 1323 ms 729112 KB Output is correct
65 Correct 1306 ms 729124 KB Output is correct
66 Correct 1332 ms 729276 KB Output is correct
67 Correct 1350 ms 728800 KB Output is correct
68 Correct 3069 ms 724992 KB Output is correct
69 Correct 3728 ms 728444 KB Output is correct
70 Correct 3320 ms 728208 KB Output is correct
71 Correct 3576 ms 728228 KB Output is correct
72 Correct 3459 ms 728324 KB Output is correct
73 Correct 3609 ms 728252 KB Output is correct
74 Correct 3482 ms 728072 KB Output is correct
75 Correct 2565 ms 729132 KB Output is correct
76 Correct 2656 ms 729200 KB Output is correct
77 Correct 2817 ms 728972 KB Output is correct
78 Correct 2587 ms 728800 KB Output is correct
79 Correct 2452 ms 729216 KB Output is correct
80 Correct 2509 ms 729056 KB Output is correct
81 Correct 51 ms 95352 KB Output is correct
82 Correct 75 ms 107296 KB Output is correct
83 Correct 74 ms 107272 KB Output is correct
84 Correct 1642 ms 728344 KB Output is correct
85 Correct 1659 ms 728120 KB Output is correct
86 Correct 1649 ms 728264 KB Output is correct
87 Correct 1308 ms 729104 KB Output is correct
88 Correct 1362 ms 729208 KB Output is correct
89 Correct 1630 ms 728296 KB Output is correct
90 Correct 1680 ms 728368 KB Output is correct
91 Correct 1676 ms 728068 KB Output is correct
92 Correct 1612 ms 729028 KB Output is correct
93 Correct 1382 ms 729080 KB Output is correct
94 Correct 81 ms 107304 KB Output is correct
95 Correct 81 ms 107296 KB Output is correct
96 Correct 91 ms 107200 KB Output is correct
97 Correct 76 ms 107312 KB Output is correct
98 Correct 76 ms 107304 KB Output is correct
99 Correct 82 ms 107304 KB Output is correct
100 Correct 82 ms 107240 KB Output is correct
101 Correct 81 ms 107224 KB Output is correct
102 Correct 75 ms 107200 KB Output is correct
103 Correct 76 ms 107308 KB Output is correct
104 Correct 3133 ms 659888 KB Output is correct
105 Correct 3511 ms 728316 KB Output is correct
106 Correct 3355 ms 728164 KB Output is correct
107 Correct 3674 ms 728088 KB Output is correct
108 Correct 3461 ms 728220 KB Output is correct
109 Correct 3674 ms 728200 KB Output is correct
110 Correct 3513 ms 728268 KB Output is correct
111 Correct 2611 ms 729248 KB Output is correct
112 Correct 2505 ms 729212 KB Output is correct
113 Correct 2676 ms 729080 KB Output is correct
114 Correct 2809 ms 729000 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1399 ms 467072 KB Output is correct
2 Correct 2846 ms 729124 KB Output is correct
3 Correct 2850 ms 728976 KB Output is correct
4 Correct 2725 ms 729136 KB Output is correct
5 Correct 2432 ms 729144 KB Output is correct
6 Correct 2607 ms 729100 KB Output is correct
7 Correct 2589 ms 729248 KB Output is correct
8 Correct 52 ms 95376 KB Output is correct
9 Correct 75 ms 107208 KB Output is correct
10 Correct 77 ms 107216 KB Output is correct
11 Correct 61 ms 97904 KB Output is correct
12 Correct 80 ms 107304 KB Output is correct
13 Correct 79 ms 107312 KB Output is correct
14 Correct 81 ms 107220 KB Output is correct
15 Correct 81 ms 107188 KB Output is correct
16 Correct 84 ms 107180 KB Output is correct
17 Correct 81 ms 107228 KB Output is correct
18 Correct 75 ms 107296 KB Output is correct
19 Correct 80 ms 107244 KB Output is correct
20 Correct 79 ms 107248 KB Output is correct
21 Correct 76 ms 107232 KB Output is correct
22 Correct 50 ms 95428 KB Output is correct
23 Correct 78 ms 107308 KB Output is correct
24 Correct 73 ms 107324 KB Output is correct
25 Correct 83 ms 107312 KB Output is correct
26 Correct 79 ms 107188 KB Output is correct
27 Correct 82 ms 107244 KB Output is correct
28 Correct 74 ms 107424 KB Output is correct
29 Correct 74 ms 107268 KB Output is correct
30 Correct 82 ms 107300 KB Output is correct
31 Correct 83 ms 107472 KB Output is correct
32 Correct 80 ms 107260 KB Output is correct
33 Correct 74 ms 107356 KB Output is correct
34 Correct 76 ms 107304 KB Output is correct
35 Correct 63 ms 100636 KB Output is correct
36 Correct 80 ms 107268 KB Output is correct
37 Correct 82 ms 107216 KB Output is correct
38 Correct 84 ms 107216 KB Output is correct
39 Correct 82 ms 107256 KB Output is correct
40 Correct 80 ms 107284 KB Output is correct
41 Correct 80 ms 107300 KB Output is correct
42 Correct 74 ms 107228 KB Output is correct
43 Correct 74 ms 107304 KB Output is correct
44 Correct 82 ms 107296 KB Output is correct
45 Correct 81 ms 107196 KB Output is correct
46 Correct 1101 ms 506036 KB Output is correct
47 Correct 1658 ms 728176 KB Output is correct
48 Correct 1643 ms 728248 KB Output is correct
49 Correct 1656 ms 728248 KB Output is correct
50 Correct 1671 ms 728084 KB Output is correct
51 Correct 1661 ms 728096 KB Output is correct
52 Correct 1668 ms 728200 KB Output is correct
53 Correct 1323 ms 729276 KB Output is correct
54 Correct 1308 ms 729144 KB Output is correct
55 Correct 1336 ms 728968 KB Output is correct
56 Correct 1340 ms 729160 KB Output is correct
57 Correct 1643 ms 728244 KB Output is correct
58 Correct 1676 ms 728224 KB Output is correct
59 Correct 1672 ms 728180 KB Output is correct
60 Correct 1335 ms 729180 KB Output is correct
61 Correct 1366 ms 729112 KB Output is correct
62 Correct 1655 ms 728344 KB Output is correct
63 Correct 1671 ms 728072 KB Output is correct
64 Correct 1670 ms 728388 KB Output is correct
65 Correct 1321 ms 729060 KB Output is correct
66 Correct 1337 ms 729144 KB Output is correct
67 Correct 1594 ms 702016 KB Output is correct
68 Correct 1664 ms 728284 KB Output is correct
69 Correct 1651 ms 728116 KB Output is correct
70 Correct 1685 ms 728164 KB Output is correct
71 Correct 1675 ms 728152 KB Output is correct
72 Correct 1695 ms 728364 KB Output is correct
73 Correct 1661 ms 728160 KB Output is correct
74 Correct 1323 ms 729112 KB Output is correct
75 Correct 1306 ms 729124 KB Output is correct
76 Correct 1332 ms 729276 KB Output is correct
77 Correct 1350 ms 728800 KB Output is correct
78 Correct 3069 ms 724992 KB Output is correct
79 Correct 3728 ms 728444 KB Output is correct
80 Correct 3320 ms 728208 KB Output is correct
81 Correct 3576 ms 728228 KB Output is correct
82 Correct 3459 ms 728324 KB Output is correct
83 Correct 3609 ms 728252 KB Output is correct
84 Correct 3482 ms 728072 KB Output is correct
85 Correct 2565 ms 729132 KB Output is correct
86 Correct 2656 ms 729200 KB Output is correct
87 Correct 2817 ms 728972 KB Output is correct
88 Correct 2587 ms 728800 KB Output is correct
89 Correct 2452 ms 729216 KB Output is correct
90 Correct 2509 ms 729056 KB Output is correct
91 Correct 51 ms 95352 KB Output is correct
92 Correct 75 ms 107296 KB Output is correct
93 Correct 74 ms 107272 KB Output is correct
94 Correct 1642 ms 728344 KB Output is correct
95 Correct 1659 ms 728120 KB Output is correct
96 Correct 1649 ms 728264 KB Output is correct
97 Correct 1308 ms 729104 KB Output is correct
98 Correct 1362 ms 729208 KB Output is correct
99 Correct 1630 ms 728296 KB Output is correct
100 Correct 1680 ms 728368 KB Output is correct
101 Correct 1676 ms 728068 KB Output is correct
102 Correct 1612 ms 729028 KB Output is correct
103 Correct 1382 ms 729080 KB Output is correct
104 Correct 81 ms 107304 KB Output is correct
105 Correct 81 ms 107296 KB Output is correct
106 Correct 91 ms 107200 KB Output is correct
107 Correct 76 ms 107312 KB Output is correct
108 Correct 76 ms 107304 KB Output is correct
109 Correct 82 ms 107304 KB Output is correct
110 Correct 82 ms 107240 KB Output is correct
111 Correct 81 ms 107224 KB Output is correct
112 Correct 75 ms 107200 KB Output is correct
113 Correct 76 ms 107308 KB Output is correct
114 Correct 775 ms 244464 KB Output is correct
115 Correct 3128 ms 728340 KB Output is correct
116 Correct 2960 ms 728236 KB Output is correct
117 Correct 3004 ms 728240 KB Output is correct
118 Correct 2588 ms 728096 KB Output is correct
119 Correct 2828 ms 728112 KB Output is correct
120 Correct 2891 ms 728472 KB Output is correct
121 Correct 2641 ms 729176 KB Output is correct
122 Correct 2733 ms 729196 KB Output is correct
123 Correct 2334 ms 729036 KB Output is correct
124 Correct 2174 ms 729092 KB Output is correct
125 Correct 1629 ms 728140 KB Output is correct
126 Correct 1671 ms 728108 KB Output is correct
127 Correct 1659 ms 728112 KB Output is correct
128 Correct 1322 ms 729140 KB Output is correct
129 Correct 1330 ms 729288 KB Output is correct
130 Correct 1574 ms 701964 KB Output is correct
131 Correct 1638 ms 728196 KB Output is correct
132 Correct 1637 ms 728348 KB Output is correct
133 Correct 1665 ms 728172 KB Output is correct
134 Correct 1666 ms 728268 KB Output is correct
135 Correct 1666 ms 728296 KB Output is correct
136 Correct 1692 ms 728168 KB Output is correct
137 Correct 1398 ms 729212 KB Output is correct
138 Correct 1325 ms 729324 KB Output is correct
139 Correct 1332 ms 729032 KB Output is correct
140 Correct 1363 ms 728904 KB Output is correct
141 Correct 88 ms 107288 KB Output is correct
142 Correct 82 ms 107296 KB Output is correct
143 Correct 79 ms 107216 KB Output is correct
144 Correct 78 ms 107220 KB Output is correct
145 Correct 77 ms 107248 KB Output is correct
146 Correct 63 ms 100672 KB Output is correct
147 Correct 80 ms 107280 KB Output is correct
148 Correct 80 ms 107264 KB Output is correct
149 Correct 80 ms 107284 KB Output is correct
150 Correct 82 ms 107308 KB Output is correct
151 Correct 80 ms 107296 KB Output is correct
152 Correct 80 ms 107232 KB Output is correct
153 Correct 78 ms 107292 KB Output is correct
154 Correct 74 ms 107204 KB Output is correct
155 Correct 76 ms 107312 KB Output is correct
156 Correct 76 ms 107212 KB Output is correct
157 Correct 3133 ms 659888 KB Output is correct
158 Correct 3511 ms 728316 KB Output is correct
159 Correct 3355 ms 728164 KB Output is correct
160 Correct 3674 ms 728088 KB Output is correct
161 Correct 3461 ms 728220 KB Output is correct
162 Correct 3674 ms 728200 KB Output is correct
163 Correct 3513 ms 728268 KB Output is correct
164 Correct 2611 ms 729248 KB Output is correct
165 Correct 2505 ms 729212 KB Output is correct
166 Correct 2676 ms 729080 KB Output is correct
167 Correct 2809 ms 729000 KB Output is correct
168 Correct 51 ms 95432 KB Output is correct
169 Correct 1734 ms 311504 KB Output is correct
170 Correct 3794 ms 728344 KB Output is correct
171 Execution timed out 4046 ms 728088 KB Time limit exceeded
172 Halted 0 ms 0 KB -