oj.uz

Submission #1041007

# Submission time Handle Problem Language Result Execution time Memory
1041007 2024-08-01T13:49:11 Z _8_8_ Radio Towers (IOI22_towers) C++17
100 / 100
 998 ms 162072 KB 
#include "towers.h"
#include <bits/stdc++.h>

using namespace std;
int n,pos;
vector<int> h;
const int N = 2e5 + 12,B = 20;
int sp[20][N],p[20][N],lg[N],sp1[20][N],p1[20][N];
bool sub = false;
void build() {
    for(int i = 0;i < n;i++){
        sp1[0][i] = sp[0][i] = h[i];
        p1[0][i] = p[0][i] = i;
    }
    for(int i = 1;i < B;i++) {
        for(int j = 0;j + (1 << i) - 1 < n;j++) {
            int X = sp[i - 1][j],Y = sp[i - 1][j + (1 << (i - 1))];
            sp[i][j] = min(X,Y);
            if(sp[i][j] == X) {
                p[i][j] = p[i - 1][j];
            }else {
                p[i][j] = p[i - 1][j + (1 << (i - 1))];
            }
            X = sp1[i - 1][j],Y = sp1[i - 1][j + (1 << (i - 1))];
            sp1[i][j] = max(X,Y);
            if(sp1[i][j] == X) {
                p1[i][j] = p1[i - 1][j];
            }else {
                p1[i][j] = p1[i - 1][j + (1 << (i - 1))];
            }
        }
    }
}
pair<int,int> get(int L,int R) {
    int i = lg[R - L + 1];
    pair<int,int> x = make_pair(sp[i][L],p[i][L]);
    pair<int,int> y = make_pair(sp[i][R - (1 << i) + 1],p[i][R - (1 << i) + 1]);
    return min(x,y);
}
pair<int,int> get1(int L,int R) {
    int i = lg[R - L + 1];
    pair<int,int> x = make_pair(sp1[i][L],p1[i][L]);
    pair<int,int> y = make_pair(sp1[i][R - (1 << i) + 1],p1[i][R - (1 << i) + 1]);
    return max(x,y);
}
int _l[N],_r[N],val[N],_mx[N],_mn[N];
vector<int> b,t;
struct node {
    bool e = true;
    int mx = 0,mn = 1e9,ans = 0,ans1 = 0;
}T[N * 4];
node merge(node l,node r) {
    if(l.e) return r;
    if(r.e) return l;
    node ret;
    ret.e = false;
    ret.mx = max(l.mx,r.mx);
    ret.mn = min(l.mn,r.mn);
    ret.ans = max({l.ans,r.ans,l.mx - r.mn});
    ret.ans1 = max({l.ans1,r.ans1,r.mx - l.mn});
    return ret;
}
void build_(int v = 1,int tl = 0,int tr = n - 1) {
    if(tl == tr) {
        T[v].mx = T[v].mn = h[tl];
        T[v].e = false;
    }else {
        int tm = (tl + tr) >> 1;
        build_(v + v,tl,tm);
        build_(v + v + 1,tm + 1,tr);
        T[v] = merge(T[v + v],T[v + v + 1]);
    }
}
node Get(int l,int r,int v = 1,int tl = 0,int tr = n - 1) {

    if(l > r || tl > r || l > tr) {
        node f;return f;
    }
    if(tl >= l && tr <= r) return T[v];
    int tm = (tl + tr) >> 1;
    return merge(Get(l,r,v+v,tl,tm),Get(l,r,v+v+1,tm+1,tr));
}

struct Node{
    Node *l = 0,*r = 0;
    int mx = 0,mn = (int)1e9,s = 0;
    Node (){}
    Node (int val) {
        mx= mn = val;
        s = 1;
    }
    Node (Node *l_,Node *r_) {
        l = l_;
        r = r_;
        mx = max(l->mx,r->mx);
        mn = min(l->mn,r->mn);
        s = l->s + r->s;
    }
};
using pnode = Node *;
pnode t_[N];
pnode build1(int tl = 0,int tr = n - 1) {
    if(tl == tr) return new Node();
    int tm = (tl + tr) >> 1;
    return new Node(build1(tl,tm),build1(tm + 1,tr));
}
pnode upd(pnode v,int pos,int tl = 0,int tr = n - 1) {
    if(tl == tr) {
        return new Node(tl);
    } else {
        int tm = (tl + tr) >> 1;
        if(pos <= tm) {
            return new Node(upd(v->l,pos,tl,tm),v->r);
        } 
        return new Node(v->l,upd(v->r,pos,tm+1,tr));
    }
}
int get_sum(int l,int r,pnode v,int tl = 0,int tr = n - 1) {
    if(l > r || tl > r || l > tr) return 0;
    if(tl >= l && tr <= r) {
        return v->s;
    }else {
        int tm = (tl + tr) >> 1;
        return get_sum(l,r,v->l,tl,tm) + get_sum(l,r,v->r,tm+1,tr);
    }
}
int get_mx(int l,int r,pnode v,int tl = 0,int tr = n - 1) {
    if(l > r || tl > r || l > tr) return 0;
    if(tl >= l && tr <= r) {
        return v->mx;
    }else {
        int tm = (tl + tr) >> 1;
        return max(get_mx(l,r,v->l,tl,tm),get_mx(l,r,v->r,tm+1,tr));
    }
}
int get_mn(int l,int r,pnode v,int tl = 0,int tr = n - 1) {
    if(l > r || tl > r || l > tr) return (int)1e9;
    if(tl >= l && tr <= r) {
        return v->mn;
    }else {
        int tm = (tl + tr) >> 1;
        return min(get_mn(l,r,v->l,tl,tm),get_mn(l,r,v->r,tm+1,tr));
    }
}
void init(int nn, vector<int> H) {
    n = nn;
    h = H;
    build();
    build_();
    for(int i = 2;i <= n;i++) {
        lg[i] = lg[i / 2] + 1;
    }
    vector<int> st;
    for(int i = 0;i < n;i++) {
        while((int)st.size() && h[st.back()] > h[i]) {
            st.pop_back();
        }
        _l[i] = (st.empty() ? -1 : st.back());
        st.push_back(i);
    }
    st.clear();
    for(int i = n - 1;i >= 0;i--) {
        while(!st.empty() && h[st.back()] > h[i]) {
            st.pop_back();
        }
        _r[i] = (st.empty() ? n : st.back());
        st.push_back(i);
    }
    for(int i = 0;i < n;i++) {
        val[i] = min(get1(_l[i] + 1,i).first,get1(i,_r[i]-1).first) - h[i];
        t.push_back(i);
    }
    sort(t.begin(),t.end(),[&](int x,int y){
        return val[x] < val[y];
    });
    for(int i:t) {
        b.push_back(val[i]);
    }
    _mx[n - 1] = _mn[n - 1] = t.back();
    for(int i = n - 2;i >= 0;i--) {
        _mx[i] = max(t[i],_mx[i + 1]);
        _mn[i] = min(t[i],_mn[i + 1]);
    }
    t_[n] = build1();
    for(int i = n - 1;i >= 0;i--) {
        t_[i] = upd(t_[i + 1],t[i]);
        // cout << i << ' ' << t[i] << ' ' << val[t[i]] << '\n';
    }
}
bool fq = true;
int up[N * 2][20],up1[N * 2][20];

bool solver(int x,int y,int d) {
    int l = x,r = y + 1;
    while(r - l > 1) {
        int mid = (l + r) >> 1;
        if(get1(x,mid).first >= h[x] + d) {
            r = mid;
        } else {
            l = mid;
        }
    }
    if(r == y + 1) {
        return false;
    }
    x = r;
    node _ = Get(x,y);
    return (_.ans >= d);
}
bool solvel(int x,int y,int d) {
    if(x > y) return 0;
    int l = x - 1,r = y;
    while(r - l > 1) {
        int mid = (l + r) >> 1;
        if(get1(mid,y).first >= h[y] + d) {
            l = mid;
        }else {
            r = mid;
        }
    }
    // cout << x << ' ' << y << ' ' << l << '\n';
    if(l == x - 1) return false;
    y = l;
    node _ = Get(x,y);
    return (_.ans1 >= d);
}
int max_towers(int l_, int r_, int d) {
    int it = lower_bound(b.begin(),b.end(),d) - b.begin();
    int ret = 0;
    int l,r;
    if(it == (int)b.size()) {
        l = r = get(l_,r_).second;
        ret++;
    } else {
        l = get_mn(l_,r_,t_[it]);
        r = get_mx(l_,r_,t_[it]);
        ret = get_sum(l_,r_,t_[it]);

        if(!ret) {
            l = r = get(l_,r_).second;
            ret++;
        }
    }
    return ret + (l != (int)1e9 ? solvel(l_,l,d) : 0) + solver(r,r_,d); 
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 116692 KB Output is correct
2 Correct 655 ms 161744 KB Output is correct
3 Correct 688 ms 161800 KB Output is correct
4 Correct 703 ms 161740 KB Output is correct
5 Correct 701 ms 161744 KB Output is correct
6 Correct 726 ms 161744 KB Output is correct
7 Correct 747 ms 161736 KB Output is correct
8 Correct 2 ms 18776 KB Output is correct
9 Correct 5 ms 44888 KB Output is correct
10 Correct 5 ms 44888 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 37464 KB Output is correct
2 Correct 5 ms 44888 KB Output is correct
3 Correct 5 ms 44888 KB Output is correct
4 Correct 7 ms 44888 KB Output is correct
5 Correct 4 ms 44824 KB Output is correct
6 Correct 5 ms 44888 KB Output is correct
7 Correct 5 ms 44888 KB Output is correct
8 Correct 5 ms 44888 KB Output is correct
9 Correct 5 ms 44888 KB Output is correct
10 Correct 5 ms 44888 KB Output is correct
11 Correct 6 ms 44888 KB Output is correct
12 Correct 2 ms 18776 KB Output is correct
13 Correct 5 ms 44888 KB Output is correct
14 Correct 7 ms 44888 KB Output is correct
15 Correct 5 ms 44888 KB Output is correct
16 Correct 5 ms 44820 KB Output is correct
17 Correct 5 ms 44980 KB Output is correct
18 Correct 5 ms 44888 KB Output is correct
19 Correct 5 ms 44888 KB Output is correct
20 Correct 5 ms 44888 KB Output is correct
21 Correct 5 ms 44820 KB Output is correct
22 Correct 5 ms 44888 KB Output is correct
23 Correct 5 ms 44888 KB Output is correct
24 Correct 5 ms 44888 KB Output is correct
25 Correct 4 ms 40024 KB Output is correct
26 Correct 5 ms 44824 KB Output is correct
27 Correct 6 ms 44888 KB Output is correct
28 Correct 5 ms 44888 KB Output is correct
29 Correct 5 ms 44888 KB Output is correct
30 Correct 5 ms 44888 KB Output is correct
31 Correct 5 ms 44888 KB Output is correct
32 Correct 5 ms 44808 KB Output is correct
33 Correct 5 ms 44888 KB Output is correct
34 Correct 5 ms 44900 KB Output is correct
35 Correct 5 ms 44888 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 37464 KB Output is correct
2 Correct 5 ms 44888 KB Output is correct
3 Correct 5 ms 44888 KB Output is correct
4 Correct 7 ms 44888 KB Output is correct
5 Correct 4 ms 44824 KB Output is correct
6 Correct 5 ms 44888 KB Output is correct
7 Correct 5 ms 44888 KB Output is correct
8 Correct 5 ms 44888 KB Output is correct
9 Correct 5 ms 44888 KB Output is correct
10 Correct 5 ms 44888 KB Output is correct
11 Correct 6 ms 44888 KB Output is correct
12 Correct 2 ms 18776 KB Output is correct
13 Correct 5 ms 44888 KB Output is correct
14 Correct 7 ms 44888 KB Output is correct
15 Correct 5 ms 44888 KB Output is correct
16 Correct 5 ms 44820 KB Output is correct
17 Correct 5 ms 44980 KB Output is correct
18 Correct 5 ms 44888 KB Output is correct
19 Correct 5 ms 44888 KB Output is correct
20 Correct 5 ms 44888 KB Output is correct
21 Correct 5 ms 44820 KB Output is correct
22 Correct 5 ms 44888 KB Output is correct
23 Correct 5 ms 44888 KB Output is correct
24 Correct 5 ms 44888 KB Output is correct
25 Correct 4 ms 40024 KB Output is correct
26 Correct 5 ms 44824 KB Output is correct
27 Correct 6 ms 44888 KB Output is correct
28 Correct 5 ms 44888 KB Output is correct
29 Correct 5 ms 44888 KB Output is correct
30 Correct 5 ms 44888 KB Output is correct
31 Correct 5 ms 44888 KB Output is correct
32 Correct 5 ms 44808 KB Output is correct
33 Correct 5 ms 44888 KB Output is correct
34 Correct 5 ms 44900 KB Output is correct
35 Correct 5 ms 44888 KB Output is correct
36 Correct 60 ms 121680 KB Output is correct
37 Correct 96 ms 161356 KB Output is correct
38 Correct 100 ms 161516 KB Output is correct
39 Correct 98 ms 161464 KB Output is correct
40 Correct 99 ms 161396 KB Output is correct
41 Correct 112 ms 161352 KB Output is correct
42 Correct 106 ms 161352 KB Output is correct
43 Correct 78 ms 161744 KB Output is correct
44 Correct 80 ms 161744 KB Output is correct
45 Correct 91 ms 161624 KB Output is correct
46 Correct 84 ms 161768 KB Output is correct
47 Correct 106 ms 161356 KB Output is correct
48 Correct 106 ms 161356 KB Output is correct
49 Correct 108 ms 161396 KB Output is correct
50 Correct 80 ms 161964 KB Output is correct
51 Correct 82 ms 161712 KB Output is correct
52 Correct 107 ms 161352 KB Output is correct
53 Correct 116 ms 161348 KB Output is correct
54 Correct 99 ms 161404 KB Output is correct
55 Correct 85 ms 161744 KB Output is correct
56 Correct 79 ms 161536 KB Output is correct
57 Correct 101 ms 158116 KB Output is correct
58 Correct 96 ms 161348 KB Output is correct
59 Correct 96 ms 161356 KB Output is correct
60 Correct 106 ms 161356 KB Output is correct
61 Correct 108 ms 161440 KB Output is correct
62 Correct 101 ms 161356 KB Output is correct
63 Correct 108 ms 161356 KB Output is correct
64 Correct 82 ms 161744 KB Output is correct
65 Correct 86 ms 161744 KB Output is correct
66 Correct 79 ms 161744 KB Output is correct
67 Correct 82 ms 161892 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 655 ms 160840 KB Output is correct
2 Correct 812 ms 161356 KB Output is correct
3 Correct 792 ms 161356 KB Output is correct
4 Correct 799 ms 161356 KB Output is correct
5 Correct 757 ms 161356 KB Output is correct
6 Correct 797 ms 161508 KB Output is correct
7 Correct 756 ms 161536 KB Output is correct
8 Correct 702 ms 161736 KB Output is correct
9 Correct 719 ms 161744 KB Output is correct
10 Correct 871 ms 161704 KB Output is correct
11 Correct 883 ms 161744 KB Output is correct
12 Correct 756 ms 161808 KB Output is correct
13 Correct 749 ms 161952 KB Output is correct
14 Correct 2 ms 18776 KB Output is correct
15 Correct 5 ms 44888 KB Output is correct
16 Correct 5 ms 44888 KB Output is correct
17 Correct 104 ms 161400 KB Output is correct
18 Correct 106 ms 161608 KB Output is correct
19 Correct 106 ms 161352 KB Output is correct
20 Correct 94 ms 161744 KB Output is correct
21 Correct 85 ms 161736 KB Output is correct
22 Correct 113 ms 161332 KB Output is correct
23 Correct 112 ms 161356 KB Output is correct
24 Correct 110 ms 161352 KB Output is correct
25 Correct 86 ms 161744 KB Output is correct
26 Correct 89 ms 161736 KB Output is correct
27 Correct 5 ms 44888 KB Output is correct
28 Correct 5 ms 44888 KB Output is correct
29 Correct 5 ms 44888 KB Output is correct
30 Correct 5 ms 44888 KB Output is correct
31 Correct 5 ms 44888 KB Output is correct
32 Correct 6 ms 44888 KB Output is correct
33 Correct 5 ms 44888 KB Output is correct
34 Correct 5 ms 44888 KB Output is correct
35 Correct 5 ms 44888 KB Output is correct
36 Correct 5 ms 44888 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 77400 KB Output is correct
2 Correct 686 ms 161356 KB Output is correct
3 Correct 704 ms 161476 KB Output is correct
4 Correct 717 ms 161524 KB Output is correct
5 Correct 672 ms 161352 KB Output is correct
6 Correct 690 ms 161356 KB Output is correct
7 Correct 721 ms 161340 KB Output is correct
8 Correct 697 ms 161744 KB Output is correct
9 Correct 668 ms 161928 KB Output is correct
10 Correct 682 ms 161744 KB Output is correct
11 Correct 670 ms 161772 KB Output is correct
12 Correct 100 ms 161356 KB Output is correct
13 Correct 101 ms 161464 KB Output is correct
14 Correct 104 ms 161540 KB Output is correct
15 Correct 83 ms 161736 KB Output is correct
16 Correct 81 ms 161744 KB Output is correct
17 Correct 99 ms 158124 KB Output is correct
18 Correct 105 ms 161440 KB Output is correct
19 Correct 104 ms 161352 KB Output is correct
20 Correct 104 ms 161356 KB Output is correct
21 Correct 106 ms 161532 KB Output is correct
22 Correct 104 ms 161356 KB Output is correct
23 Correct 103 ms 161448 KB Output is correct
24 Correct 82 ms 161908 KB Output is correct
25 Correct 84 ms 161724 KB Output is correct
26 Correct 83 ms 161732 KB Output is correct
27 Correct 89 ms 161744 KB Output is correct
28 Correct 5 ms 44888 KB Output is correct
29 Correct 5 ms 44888 KB Output is correct
30 Correct 5 ms 44888 KB Output is correct
31 Correct 5 ms 44888 KB Output is correct
32 Correct 5 ms 44888 KB Output is correct
33 Correct 4 ms 40024 KB Output is correct
34 Correct 5 ms 44888 KB Output is correct
35 Correct 5 ms 44888 KB Output is correct
36 Correct 5 ms 44888 KB Output is correct
37 Correct 5 ms 44888 KB Output is correct
38 Correct 5 ms 44748 KB Output is correct
39 Correct 5 ms 44888 KB Output is correct
40 Correct 5 ms 44888 KB Output is correct
41 Correct 5 ms 44888 KB Output is correct
42 Correct 5 ms 44888 KB Output is correct
43 Correct 5 ms 44804 KB Output is correct

Subtask #6
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 37464 KB Output is correct
2 Correct 5 ms 44888 KB Output is correct
3 Correct 5 ms 44888 KB Output is correct
4 Correct 7 ms 44888 KB Output is correct
5 Correct 4 ms 44824 KB Output is correct
6 Correct 5 ms 44888 KB Output is correct
7 Correct 5 ms 44888 KB Output is correct
8 Correct 5 ms 44888 KB Output is correct
9 Correct 5 ms 44888 KB Output is correct
10 Correct 5 ms 44888 KB Output is correct
11 Correct 6 ms 44888 KB Output is correct
12 Correct 2 ms 18776 KB Output is correct
13 Correct 5 ms 44888 KB Output is correct
14 Correct 7 ms 44888 KB Output is correct
15 Correct 5 ms 44888 KB Output is correct
16 Correct 5 ms 44820 KB Output is correct
17 Correct 5 ms 44980 KB Output is correct
18 Correct 5 ms 44888 KB Output is correct
19 Correct 5 ms 44888 KB Output is correct
20 Correct 5 ms 44888 KB Output is correct
21 Correct 5 ms 44820 KB Output is correct
22 Correct 5 ms 44888 KB Output is correct
23 Correct 5 ms 44888 KB Output is correct
24 Correct 5 ms 44888 KB Output is correct
25 Correct 4 ms 40024 KB Output is correct
26 Correct 5 ms 44824 KB Output is correct
27 Correct 6 ms 44888 KB Output is correct
28 Correct 5 ms 44888 KB Output is correct
29 Correct 5 ms 44888 KB Output is correct
30 Correct 5 ms 44888 KB Output is correct
31 Correct 5 ms 44888 KB Output is correct
32 Correct 5 ms 44808 KB Output is correct
33 Correct 5 ms 44888 KB Output is correct
34 Correct 5 ms 44900 KB Output is correct
35 Correct 5 ms 44888 KB Output is correct
36 Correct 60 ms 121680 KB Output is correct
37 Correct 96 ms 161356 KB Output is correct
38 Correct 100 ms 161516 KB Output is correct
39 Correct 98 ms 161464 KB Output is correct
40 Correct 99 ms 161396 KB Output is correct
41 Correct 112 ms 161352 KB Output is correct
42 Correct 106 ms 161352 KB Output is correct
43 Correct 78 ms 161744 KB Output is correct
44 Correct 80 ms 161744 KB Output is correct
45 Correct 91 ms 161624 KB Output is correct
46 Correct 84 ms 161768 KB Output is correct
47 Correct 106 ms 161356 KB Output is correct
48 Correct 106 ms 161356 KB Output is correct
49 Correct 108 ms 161396 KB Output is correct
50 Correct 80 ms 161964 KB Output is correct
51 Correct 82 ms 161712 KB Output is correct
52 Correct 107 ms 161352 KB Output is correct
53 Correct 116 ms 161348 KB Output is correct
54 Correct 99 ms 161404 KB Output is correct
55 Correct 85 ms 161744 KB Output is correct
56 Correct 79 ms 161536 KB Output is correct
57 Correct 101 ms 158116 KB Output is correct
58 Correct 96 ms 161348 KB Output is correct
59 Correct 96 ms 161356 KB Output is correct
60 Correct 106 ms 161356 KB Output is correct
61 Correct 108 ms 161440 KB Output is correct
62 Correct 101 ms 161356 KB Output is correct
63 Correct 108 ms 161356 KB Output is correct
64 Correct 82 ms 161744 KB Output is correct
65 Correct 86 ms 161744 KB Output is correct
66 Correct 79 ms 161744 KB Output is correct
67 Correct 82 ms 161892 KB Output is correct
68 Correct 655 ms 160840 KB Output is correct
69 Correct 812 ms 161356 KB Output is correct
70 Correct 792 ms 161356 KB Output is correct
71 Correct 799 ms 161356 KB Output is correct
72 Correct 757 ms 161356 KB Output is correct
73 Correct 797 ms 161508 KB Output is correct
74 Correct 756 ms 161536 KB Output is correct
75 Correct 702 ms 161736 KB Output is correct
76 Correct 719 ms 161744 KB Output is correct
77 Correct 871 ms 161704 KB Output is correct
78 Correct 883 ms 161744 KB Output is correct
79 Correct 756 ms 161808 KB Output is correct
80 Correct 749 ms 161952 KB Output is correct
81 Correct 2 ms 18776 KB Output is correct
82 Correct 5 ms 44888 KB Output is correct
83 Correct 5 ms 44888 KB Output is correct
84 Correct 104 ms 161400 KB Output is correct
85 Correct 106 ms 161608 KB Output is correct
86 Correct 106 ms 161352 KB Output is correct
87 Correct 94 ms 161744 KB Output is correct
88 Correct 85 ms 161736 KB Output is correct
89 Correct 113 ms 161332 KB Output is correct
90 Correct 112 ms 161356 KB Output is correct
91 Correct 110 ms 161352 KB Output is correct
92 Correct 86 ms 161744 KB Output is correct
93 Correct 89 ms 161736 KB Output is correct
94 Correct 5 ms 44888 KB Output is correct
95 Correct 5 ms 44888 KB Output is correct
96 Correct 5 ms 44888 KB Output is correct
97 Correct 5 ms 44888 KB Output is correct
98 Correct 5 ms 44888 KB Output is correct
99 Correct 6 ms 44888 KB Output is correct
100 Correct 5 ms 44888 KB Output is correct
101 Correct 5 ms 44888 KB Output is correct
102 Correct 5 ms 44888 KB Output is correct
103 Correct 5 ms 44888 KB Output is correct
104 Correct 686 ms 150160 KB Output is correct
105 Correct 832 ms 161352 KB Output is correct
106 Correct 806 ms 161404 KB Output is correct
107 Correct 791 ms 161356 KB Output is correct
108 Correct 781 ms 161356 KB Output is correct
109 Correct 813 ms 161352 KB Output is correct
110 Correct 799 ms 161356 KB Output is correct
111 Correct 704 ms 161736 KB Output is correct
112 Correct 652 ms 161796 KB Output is correct
113 Correct 817 ms 161748 KB Output is correct
114 Correct 807 ms 161768 KB Output is correct

Subtask #7
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 116692 KB Output is correct
2 Correct 655 ms 161744 KB Output is correct
3 Correct 688 ms 161800 KB Output is correct
4 Correct 703 ms 161740 KB Output is correct
5 Correct 701 ms 161744 KB Output is correct
6 Correct 726 ms 161744 KB Output is correct
7 Correct 747 ms 161736 KB Output is correct
8 Correct 2 ms 18776 KB Output is correct
9 Correct 5 ms 44888 KB Output is correct
10 Correct 5 ms 44888 KB Output is correct
11 Correct 4 ms 37464 KB Output is correct
12 Correct 5 ms 44888 KB Output is correct
13 Correct 5 ms 44888 KB Output is correct
14 Correct 7 ms 44888 KB Output is correct
15 Correct 4 ms 44824 KB Output is correct
16 Correct 5 ms 44888 KB Output is correct
17 Correct 5 ms 44888 KB Output is correct
18 Correct 5 ms 44888 KB Output is correct
19 Correct 5 ms 44888 KB Output is correct
20 Correct 5 ms 44888 KB Output is correct
21 Correct 6 ms 44888 KB Output is correct
22 Correct 2 ms 18776 KB Output is correct
23 Correct 5 ms 44888 KB Output is correct
24 Correct 7 ms 44888 KB Output is correct
25 Correct 5 ms 44888 KB Output is correct
26 Correct 5 ms 44820 KB Output is correct
27 Correct 5 ms 44980 KB Output is correct
28 Correct 5 ms 44888 KB Output is correct
29 Correct 5 ms 44888 KB Output is correct
30 Correct 5 ms 44888 KB Output is correct
31 Correct 5 ms 44820 KB Output is correct
32 Correct 5 ms 44888 KB Output is correct
33 Correct 5 ms 44888 KB Output is correct
34 Correct 5 ms 44888 KB Output is correct
35 Correct 4 ms 40024 KB Output is correct
36 Correct 5 ms 44824 KB Output is correct
37 Correct 6 ms 44888 KB Output is correct
38 Correct 5 ms 44888 KB Output is correct
39 Correct 5 ms 44888 KB Output is correct
40 Correct 5 ms 44888 KB Output is correct
41 Correct 5 ms 44888 KB Output is correct
42 Correct 5 ms 44808 KB Output is correct
43 Correct 5 ms 44888 KB Output is correct
44 Correct 5 ms 44900 KB Output is correct
45 Correct 5 ms 44888 KB Output is correct
46 Correct 60 ms 121680 KB Output is correct
47 Correct 96 ms 161356 KB Output is correct
48 Correct 100 ms 161516 KB Output is correct
49 Correct 98 ms 161464 KB Output is correct
50 Correct 99 ms 161396 KB Output is correct
51 Correct 112 ms 161352 KB Output is correct
52 Correct 106 ms 161352 KB Output is correct
53 Correct 78 ms 161744 KB Output is correct
54 Correct 80 ms 161744 KB Output is correct
55 Correct 91 ms 161624 KB Output is correct
56 Correct 84 ms 161768 KB Output is correct
57 Correct 106 ms 161356 KB Output is correct
58 Correct 106 ms 161356 KB Output is correct
59 Correct 108 ms 161396 KB Output is correct
60 Correct 80 ms 161964 KB Output is correct
61 Correct 82 ms 161712 KB Output is correct
62 Correct 107 ms 161352 KB Output is correct
63 Correct 116 ms 161348 KB Output is correct
64 Correct 99 ms 161404 KB Output is correct
65 Correct 85 ms 161744 KB Output is correct
66 Correct 79 ms 161536 KB Output is correct
67 Correct 101 ms 158116 KB Output is correct
68 Correct 96 ms 161348 KB Output is correct
69 Correct 96 ms 161356 KB Output is correct
70 Correct 106 ms 161356 KB Output is correct
71 Correct 108 ms 161440 KB Output is correct
72 Correct 101 ms 161356 KB Output is correct
73 Correct 108 ms 161356 KB Output is correct
74 Correct 82 ms 161744 KB Output is correct
75 Correct 86 ms 161744 KB Output is correct
76 Correct 79 ms 161744 KB Output is correct
77 Correct 82 ms 161892 KB Output is correct
78 Correct 655 ms 160840 KB Output is correct
79 Correct 812 ms 161356 KB Output is correct
80 Correct 792 ms 161356 KB Output is correct
81 Correct 799 ms 161356 KB Output is correct
82 Correct 757 ms 161356 KB Output is correct
83 Correct 797 ms 161508 KB Output is correct
84 Correct 756 ms 161536 KB Output is correct
85 Correct 702 ms 161736 KB Output is correct
86 Correct 719 ms 161744 KB Output is correct
87 Correct 871 ms 161704 KB Output is correct
88 Correct 883 ms 161744 KB Output is correct
89 Correct 756 ms 161808 KB Output is correct
90 Correct 749 ms 161952 KB Output is correct
91 Correct 2 ms 18776 KB Output is correct
92 Correct 5 ms 44888 KB Output is correct
93 Correct 5 ms 44888 KB Output is correct
94 Correct 104 ms 161400 KB Output is correct
95 Correct 106 ms 161608 KB Output is correct
96 Correct 106 ms 161352 KB Output is correct
97 Correct 94 ms 161744 KB Output is correct
98 Correct 85 ms 161736 KB Output is correct
99 Correct 113 ms 161332 KB Output is correct
100 Correct 112 ms 161356 KB Output is correct
101 Correct 110 ms 161352 KB Output is correct
102 Correct 86 ms 161744 KB Output is correct
103 Correct 89 ms 161736 KB Output is correct
104 Correct 5 ms 44888 KB Output is correct
105 Correct 5 ms 44888 KB Output is correct
106 Correct 5 ms 44888 KB Output is correct
107 Correct 5 ms 44888 KB Output is correct
108 Correct 5 ms 44888 KB Output is correct
109 Correct 6 ms 44888 KB Output is correct
110 Correct 5 ms 44888 KB Output is correct
111 Correct 5 ms 44888 KB Output is correct
112 Correct 5 ms 44888 KB Output is correct
113 Correct 5 ms 44888 KB Output is correct
114 Correct 196 ms 77400 KB Output is correct
115 Correct 686 ms 161356 KB Output is correct
116 Correct 704 ms 161476 KB Output is correct
117 Correct 717 ms 161524 KB Output is correct
118 Correct 672 ms 161352 KB Output is correct
119 Correct 690 ms 161356 KB Output is correct
120 Correct 721 ms 161340 KB Output is correct
121 Correct 697 ms 161744 KB Output is correct
122 Correct 668 ms 161928 KB Output is correct
123 Correct 682 ms 161744 KB Output is correct
124 Correct 670 ms 161772 KB Output is correct
125 Correct 100 ms 161356 KB Output is correct
126 Correct 101 ms 161464 KB Output is correct
127 Correct 104 ms 161540 KB Output is correct
128 Correct 83 ms 161736 KB Output is correct
129 Correct 81 ms 161744 KB Output is correct
130 Correct 99 ms 158124 KB Output is correct
131 Correct 105 ms 161440 KB Output is correct
132 Correct 104 ms 161352 KB Output is correct
133 Correct 104 ms 161356 KB Output is correct
134 Correct 106 ms 161532 KB Output is correct
135 Correct 104 ms 161356 KB Output is correct
136 Correct 103 ms 161448 KB Output is correct
137 Correct 82 ms 161908 KB Output is correct
138 Correct 84 ms 161724 KB Output is correct
139 Correct 83 ms 161732 KB Output is correct
140 Correct 89 ms 161744 KB Output is correct
141 Correct 5 ms 44888 KB Output is correct
142 Correct 5 ms 44888 KB Output is correct
143 Correct 5 ms 44888 KB Output is correct
144 Correct 5 ms 44888 KB Output is correct
145 Correct 5 ms 44888 KB Output is correct
146 Correct 4 ms 40024 KB Output is correct
147 Correct 5 ms 44888 KB Output is correct
148 Correct 5 ms 44888 KB Output is correct
149 Correct 5 ms 44888 KB Output is correct
150 Correct 5 ms 44888 KB Output is correct
151 Correct 5 ms 44748 KB Output is correct
152 Correct 5 ms 44888 KB Output is correct
153 Correct 5 ms 44888 KB Output is correct
154 Correct 5 ms 44888 KB Output is correct
155 Correct 5 ms 44888 KB Output is correct
156 Correct 5 ms 44804 KB Output is correct
157 Correct 686 ms 150160 KB Output is correct
158 Correct 832 ms 161352 KB Output is correct
159 Correct 806 ms 161404 KB Output is correct
160 Correct 791 ms 161356 KB Output is correct
161 Correct 781 ms 161356 KB Output is correct
162 Correct 813 ms 161352 KB Output is correct
163 Correct 799 ms 161356 KB Output is correct
164 Correct 704 ms 161736 KB Output is correct
165 Correct 652 ms 161796 KB Output is correct
166 Correct 817 ms 161748 KB Output is correct
167 Correct 807 ms 161768 KB Output is correct
168 Correct 2 ms 18776 KB Output is correct
169 Correct 528 ms 92688 KB Output is correct
170 Correct 934 ms 161500 KB Output is correct
171 Correct 926 ms 161356 KB Output is correct
172 Correct 946 ms 161356 KB Output is correct
173 Correct 954 ms 161356 KB Output is correct
174 Correct 994 ms 161416 KB Output is correct
175 Correct 998 ms 161472 KB Output is correct
176 Correct 750 ms 162072 KB Output is correct
177 Correct 714 ms 161740 KB Output is correct
178 Correct 852 ms 161824 KB Output is correct
179 Correct 797 ms 161996 KB Output is correct