oj.uz

답안 #1051069

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1051069 2024-08-09T19:12:08 Z PoonYaPat Diversity (CEOI21_diversity) C++14
64 / 100
 7000 ms 227012 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int MX=300000,sq=1350;
int MID,mx=1;

struct NN {
    ll sum,sl,sr,cnt;
} s[1<<21];

NN merge(NN a, NN b) {
    NN res;
    res.sum=a.sum+b.sum;
    res.cnt=a.cnt+b.cnt;
    res.sl=a.sl+a.cnt*b.sum+b.sl;
    res.sr=b.sr+b.cnt*a.sum+a.sr;
    return res;
}

ll fast2_query(int l, int r, int idx, int x, int val) {
    if (x>r) return s[idx].sr+s[idx].sum*(ll)(x-r);
    if (x<l) return s[idx].sl+s[idx].sum*(ll)(l-x);
    if (l==r) {
        if (val==0) s[idx]={0,0,0,0};
        else s[idx]={val,val,val,1};
        return val;
    }
    int mid=(l+r)/2;
    ll res1=fast2_query(l,mid,2*idx,x,val);
    ll res2=fast2_query(mid+1,r,2*idx+1,x,val);
    s[idx]=merge(s[2*idx],s[2*idx+1]);
    return res1+res2;
}

int have[MX+5],idx_seq=-1;
vector<int> seq;
deque<int> dq[MX+5];
ll ans=0;
ll lcnt,rcnt;
ll L=MID,R=MID;

ll cal_left(int pos) {
    return lcnt*(lcnt+1)/2 + (s[1].sl+s[1].sum*(L-pos)) + (rcnt*(rcnt+1)/2+rcnt*(R+1-pos));
}

ll cal_right(int pos) {
    return rcnt*(rcnt+1)/2 + (s[1].sr+s[1].sum*(pos-R)) + (lcnt*(lcnt+1)/2+lcnt*(pos-L+1));
}

ll cal_mid(int pos, int val) {
    return fast2_query(1,mx,1,pos,val) + (rcnt*(rcnt+1)/2+rcnt*(R+1-pos)) + (lcnt*(lcnt+1)/2+lcnt*(pos-L+1));
}

void add(int val) {

    if (have[val]>1) {
        int pos=dq[have[val]].front();
        dq[have[val]].pop_front();
        dq[have[val]+1].push_back(pos);
        ans+=cal_mid(pos,have[val]+1);

    } else if (have[val]==1) {
        int pos=dq[1].front();
        dq[1].pop_front();
        dq[2].push_back(pos);
        
        if (pos<MID) --lcnt, L=pos;
        if (pos>MID) --rcnt, R=pos;
        
        ans+=cal_mid(pos,2);

    } else {
        int pos=seq[++idx_seq];
        dq[1].push_back(pos);

        if (pos==MID) ans+=cal_mid(pos,1);
        else if (pos<MID) {
            ++lcnt;
            ans+=cal_left(pos);
        } else {
            ++rcnt;
            ans+=cal_right(pos);
        }
    }

    ++have[val];
}

void del(int val) {

    if (have[val]>2) {
        int pos=dq[have[val]].back();
        dq[have[val]].pop_back();
        dq[have[val]-1].push_front(pos);
        ans-=(cal_mid(pos,have[val]-1)+1);

    } else if (have[val]==2) {
        int pos=dq[2].back();
        dq[2].pop_back();
        dq[1].push_front(pos);

        if (pos==MID) ans-=(cal_mid(pos,1)+1);
        else {
            ans-=(cal_mid(pos,0)+2);
            if (pos<MID) ++lcnt, L=pos+1;
            if (pos>MID) ++rcnt, R=pos-1;
        } 

    } else {
        int pos=dq[1].back();
        dq[1].pop_back();
        --idx_seq;

        if (pos==MID) {
            fast2_query(1,mx,1,pos,0);
            ans=0;
        } else if (pos<MID) {
            ans-=cal_left(pos);
            --lcnt;
        } else {
            ans-=cal_right(pos);
            --rcnt;
        }
    }
    
    --have[val];
}

int n,q,a[MX+5];

struct Query {
    int l,r,idx;
    bool operator<(Query other) const {
        return pii(l/sq,((l/sq)&1) ? -r : +r)<pii(other.l/sq,((other.l/sq)&1) ? -other.r : +other.r);
    }
};

vector<Query> ques;
ll Ans[50005];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    set<int> ss;
    cin>>n>>q;
    for (int i=0; i<n; ++i) cin>>a[i], ss.insert(a[i]), ++have[a[i]];
    for (auto s : ss) if (have[s]>1) ++mx;
    memset(have,0,sizeof(have));
    mx+=(mx%2);

    MID=mx/2;
    L=MID;R=MID;
    int ll=MID,rr=MID;
    seq.push_back(MID);
    for (int i=1; i<MX; ++i) {
        if (i%2==0) seq.push_back(--ll);
        else seq.push_back(++rr);
    }

    for (int i=0; i<q; ++i) {
        int l,r; cin>>l>>r;
        ques.push_back({--l,--r,i});
    }

    sort(ques.begin(),ques.end());

    int cur_l=0;
    int cur_r=-1;

    for (auto q : ques) {
        while (cur_l>q.l) add(a[--cur_l]);
        while (cur_r<q.r) add(a[++cur_r]);
        while (cur_l<q.l) del(a[cur_l++]);
        while (cur_r>q.r) del(a[cur_r--]);
        Ans[q.idx]=ans;
    }

    for (int i=0; i<q; ++i) cout<<Ans[i]<<"\n";
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 207748 KB Output is correct
2 Correct 73 ms 207772 KB Output is correct
3 Correct 68 ms 207560 KB Output is correct
4 Correct 68 ms 207556 KB Output is correct
5 Correct 67 ms 207560 KB Output is correct
6 Correct 86 ms 207556 KB Output is correct
7 Correct 75 ms 207640 KB Output is correct
8 Correct 76 ms 207748 KB Output is correct
9 Correct 70 ms 207564 KB Output is correct
10 Correct 68 ms 207596 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 207556 KB Output is correct
2 Correct 71 ms 207560 KB Output is correct
3 Correct 72 ms 207776 KB Output is correct
4 Correct 77 ms 207816 KB Output is correct
5 Correct 110 ms 208124 KB Output is correct
6 Correct 124 ms 208328 KB Output is correct
7 Correct 124 ms 208328 KB Output is correct
8 Correct 103 ms 208328 KB Output is correct
9 Correct 107 ms 208328 KB Output is correct
10 Correct 104 ms 208328 KB Output is correct
11 Correct 101 ms 208328 KB Output is correct
12 Correct 95 ms 208288 KB Output is correct
13 Correct 119 ms 208380 KB Output is correct
14 Correct 111 ms 208324 KB Output is correct
15 Correct 118 ms 208296 KB Output is correct

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 207556 KB Output is correct
2 Correct 71 ms 207560 KB Output is correct
3 Correct 72 ms 207776 KB Output is correct
4 Correct 77 ms 207816 KB Output is correct
5 Correct 110 ms 208124 KB Output is correct
6 Correct 124 ms 208328 KB Output is correct
7 Correct 124 ms 208328 KB Output is correct
8 Correct 103 ms 208328 KB Output is correct
9 Correct 107 ms 208328 KB Output is correct
10 Correct 104 ms 208328 KB Output is correct
11 Correct 101 ms 208328 KB Output is correct
12 Correct 95 ms 208288 KB Output is correct
13 Correct 119 ms 208380 KB Output is correct
14 Correct 111 ms 208324 KB Output is correct
15 Correct 118 ms 208296 KB Output is correct
16 Correct 87 ms 207676 KB Output is correct
17 Correct 72 ms 207560 KB Output is correct
18 Correct 78 ms 207636 KB Output is correct
19 Correct 85 ms 207836 KB Output is correct
20 Correct 101 ms 208252 KB Output is correct
21 Correct 114 ms 208560 KB Output is correct
22 Correct 126 ms 208360 KB Output is correct
23 Correct 112 ms 208560 KB Output is correct
24 Correct 114 ms 208612 KB Output is correct
25 Correct 106 ms 208328 KB Output is correct
26 Correct 116 ms 208328 KB Output is correct
27 Correct 109 ms 208324 KB Output is correct
28 Correct 113 ms 208428 KB Output is correct
29 Correct 105 ms 208440 KB Output is correct
30 Correct 124 ms 208388 KB Output is correct

Subtask #4
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 207556 KB Output is correct
2 Correct 71 ms 207560 KB Output is correct
3 Correct 72 ms 207776 KB Output is correct
4 Correct 77 ms 207816 KB Output is correct
5 Correct 110 ms 208124 KB Output is correct
6 Correct 124 ms 208328 KB Output is correct
7 Correct 124 ms 208328 KB Output is correct
8 Correct 103 ms 208328 KB Output is correct
9 Correct 107 ms 208328 KB Output is correct
10 Correct 104 ms 208328 KB Output is correct
11 Correct 101 ms 208328 KB Output is correct
12 Correct 95 ms 208288 KB Output is correct
13 Correct 119 ms 208380 KB Output is correct
14 Correct 111 ms 208324 KB Output is correct
15 Correct 118 ms 208296 KB Output is correct
16 Correct 87 ms 207676 KB Output is correct
17 Correct 72 ms 207560 KB Output is correct
18 Correct 78 ms 207636 KB Output is correct
19 Correct 85 ms 207836 KB Output is correct
20 Correct 101 ms 208252 KB Output is correct
21 Correct 114 ms 208560 KB Output is correct
22 Correct 126 ms 208360 KB Output is correct
23 Correct 112 ms 208560 KB Output is correct
24 Correct 114 ms 208612 KB Output is correct
25 Correct 106 ms 208328 KB Output is correct
26 Correct 116 ms 208328 KB Output is correct
27 Correct 109 ms 208324 KB Output is correct
28 Correct 113 ms 208428 KB Output is correct
29 Correct 105 ms 208440 KB Output is correct
30 Correct 124 ms 208388 KB Output is correct
31 Correct 71 ms 207560 KB Output is correct
32 Correct 84 ms 207556 KB Output is correct
33 Correct 72 ms 207664 KB Output is correct
34 Correct 76 ms 207672 KB Output is correct
35 Correct 71 ms 207812 KB Output is correct
36 Correct 115 ms 207820 KB Output is correct
37 Correct 100 ms 207820 KB Output is correct
38 Correct 117 ms 208000 KB Output is correct
39 Correct 96 ms 208076 KB Output is correct
40 Correct 112 ms 208356 KB Output is correct
41 Correct 141 ms 208848 KB Output is correct
42 Correct 155 ms 208844 KB Output is correct
43 Correct 130 ms 208840 KB Output is correct
44 Correct 127 ms 208840 KB Output is correct
45 Correct 137 ms 208792 KB Output is correct
46 Correct 134 ms 208844 KB Output is correct
47 Correct 136 ms 208820 KB Output is correct
48 Correct 137 ms 208828 KB Output is correct
49 Correct 133 ms 208944 KB Output is correct
50 Correct 129 ms 208840 KB Output is correct
51 Correct 131 ms 208840 KB Output is correct
52 Correct 131 ms 208840 KB Output is correct
53 Correct 141 ms 208840 KB Output is correct
54 Correct 161 ms 208844 KB Output is correct
55 Correct 133 ms 208844 KB Output is correct
56 Correct 153 ms 208960 KB Output is correct
57 Correct 129 ms 208864 KB Output is correct
58 Correct 151 ms 208940 KB Output is correct
59 Correct 149 ms 208848 KB Output is correct
60 Correct 140 ms 208840 KB Output is correct

Subtask #5
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 207748 KB Output is correct
2 Correct 73 ms 207772 KB Output is correct
3 Correct 68 ms 207560 KB Output is correct
4 Correct 68 ms 207556 KB Output is correct
5 Correct 67 ms 207560 KB Output is correct
6 Correct 86 ms 207556 KB Output is correct
7 Correct 75 ms 207640 KB Output is correct
8 Correct 76 ms 207748 KB Output is correct
9 Correct 70 ms 207564 KB Output is correct
10 Correct 68 ms 207596 KB Output is correct
11 Correct 72 ms 207556 KB Output is correct
12 Correct 71 ms 207560 KB Output is correct
13 Correct 72 ms 207776 KB Output is correct
14 Correct 77 ms 207816 KB Output is correct
15 Correct 110 ms 208124 KB Output is correct
16 Correct 124 ms 208328 KB Output is correct
17 Correct 124 ms 208328 KB Output is correct
18 Correct 103 ms 208328 KB Output is correct
19 Correct 107 ms 208328 KB Output is correct
20 Correct 104 ms 208328 KB Output is correct
21 Correct 101 ms 208328 KB Output is correct
22 Correct 95 ms 208288 KB Output is correct
23 Correct 119 ms 208380 KB Output is correct
24 Correct 111 ms 208324 KB Output is correct
25 Correct 118 ms 208296 KB Output is correct
26 Correct 87 ms 207676 KB Output is correct
27 Correct 72 ms 207560 KB Output is correct
28 Correct 78 ms 207636 KB Output is correct
29 Correct 85 ms 207836 KB Output is correct
30 Correct 101 ms 208252 KB Output is correct
31 Correct 114 ms 208560 KB Output is correct
32 Correct 126 ms 208360 KB Output is correct
33 Correct 112 ms 208560 KB Output is correct
34 Correct 114 ms 208612 KB Output is correct
35 Correct 106 ms 208328 KB Output is correct
36 Correct 116 ms 208328 KB Output is correct
37 Correct 109 ms 208324 KB Output is correct
38 Correct 113 ms 208428 KB Output is correct
39 Correct 105 ms 208440 KB Output is correct
40 Correct 124 ms 208388 KB Output is correct
41 Correct 71 ms 207560 KB Output is correct
42 Correct 84 ms 207556 KB Output is correct
43 Correct 72 ms 207664 KB Output is correct
44 Correct 76 ms 207672 KB Output is correct
45 Correct 71 ms 207812 KB Output is correct
46 Correct 115 ms 207820 KB Output is correct
47 Correct 100 ms 207820 KB Output is correct
48 Correct 117 ms 208000 KB Output is correct
49 Correct 96 ms 208076 KB Output is correct
50 Correct 112 ms 208356 KB Output is correct
51 Correct 141 ms 208848 KB Output is correct
52 Correct 155 ms 208844 KB Output is correct
53 Correct 130 ms 208840 KB Output is correct
54 Correct 127 ms 208840 KB Output is correct
55 Correct 137 ms 208792 KB Output is correct
56 Correct 134 ms 208844 KB Output is correct
57 Correct 136 ms 208820 KB Output is correct
58 Correct 137 ms 208828 KB Output is correct
59 Correct 133 ms 208944 KB Output is correct
60 Correct 129 ms 208840 KB Output is correct
61 Correct 131 ms 208840 KB Output is correct
62 Correct 131 ms 208840 KB Output is correct
63 Correct 141 ms 208840 KB Output is correct
64 Correct 161 ms 208844 KB Output is correct
65 Correct 133 ms 208844 KB Output is correct
66 Correct 153 ms 208960 KB Output is correct
67 Correct 129 ms 208864 KB Output is correct
68 Correct 151 ms 208940 KB Output is correct
69 Correct 149 ms 208848 KB Output is correct
70 Correct 140 ms 208840 KB Output is correct
71 Correct 88 ms 208068 KB Output is correct
72 Correct 106 ms 208072 KB Output is correct
73 Correct 89 ms 208068 KB Output is correct
74 Correct 90 ms 208072 KB Output is correct
75 Correct 92 ms 208068 KB Output is correct
76 Correct 103 ms 208256 KB Output is correct
77 Correct 100 ms 208340 KB Output is correct
78 Correct 104 ms 208380 KB Output is correct
79 Correct 106 ms 208484 KB Output is correct
80 Correct 100 ms 208324 KB Output is correct
81 Correct 124 ms 210232 KB Output is correct
82 Correct 133 ms 210236 KB Output is correct
83 Correct 135 ms 210328 KB Output is correct
84 Correct 134 ms 210376 KB Output is correct
85 Correct 138 ms 210360 KB Output is correct
86 Correct 125 ms 210116 KB Output is correct
87 Correct 125 ms 210112 KB Output is correct
88 Correct 122 ms 210112 KB Output is correct
89 Correct 152 ms 210112 KB Output is correct
90 Correct 126 ms 210116 KB Output is correct
91 Correct 200 ms 221780 KB Output is correct
92 Correct 180 ms 221636 KB Output is correct
93 Correct 181 ms 221632 KB Output is correct
94 Correct 179 ms 221636 KB Output is correct
95 Correct 183 ms 221632 KB Output is correct
96 Correct 206 ms 227012 KB Output is correct
97 Correct 196 ms 227012 KB Output is correct
98 Correct 190 ms 227012 KB Output is correct
99 Correct 207 ms 227008 KB Output is correct
100 Correct 198 ms 227008 KB Output is correct
101 Correct 195 ms 227008 KB Output is correct
102 Correct 199 ms 227008 KB Output is correct
103 Correct 192 ms 227004 KB Output is correct
104 Correct 190 ms 227012 KB Output is correct
105 Correct 201 ms 226996 KB Output is correct
106 Correct 204 ms 225476 KB Output is correct
107 Correct 198 ms 225476 KB Output is correct
108 Correct 178 ms 225476 KB Output is correct
109 Correct 220 ms 225356 KB Output is correct
110 Correct 192 ms 225472 KB Output is correct
111 Correct 193 ms 225476 KB Output is correct
112 Correct 215 ms 225540 KB Output is correct
113 Correct 189 ms 225440 KB Output is correct
114 Correct 208 ms 225476 KB Output is correct
115 Correct 195 ms 225472 KB Output is correct

Subtask #6
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 207748 KB Output is correct
2 Correct 73 ms 207772 KB Output is correct
3 Correct 68 ms 207560 KB Output is correct
4 Correct 68 ms 207556 KB Output is correct
5 Correct 67 ms 207560 KB Output is correct
6 Correct 86 ms 207556 KB Output is correct
7 Correct 75 ms 207640 KB Output is correct
8 Correct 76 ms 207748 KB Output is correct
9 Correct 70 ms 207564 KB Output is correct
10 Correct 68 ms 207596 KB Output is correct
11 Correct 72 ms 207556 KB Output is correct
12 Correct 71 ms 207560 KB Output is correct
13 Correct 72 ms 207776 KB Output is correct
14 Correct 77 ms 207816 KB Output is correct
15 Correct 110 ms 208124 KB Output is correct
16 Correct 124 ms 208328 KB Output is correct
17 Correct 124 ms 208328 KB Output is correct
18 Correct 103 ms 208328 KB Output is correct
19 Correct 107 ms 208328 KB Output is correct
20 Correct 104 ms 208328 KB Output is correct
21 Correct 101 ms 208328 KB Output is correct
22 Correct 95 ms 208288 KB Output is correct
23 Correct 119 ms 208380 KB Output is correct
24 Correct 111 ms 208324 KB Output is correct
25 Correct 118 ms 208296 KB Output is correct
26 Correct 87 ms 207676 KB Output is correct
27 Correct 72 ms 207560 KB Output is correct
28 Correct 78 ms 207636 KB Output is correct
29 Correct 85 ms 207836 KB Output is correct
30 Correct 101 ms 208252 KB Output is correct
31 Correct 114 ms 208560 KB Output is correct
32 Correct 126 ms 208360 KB Output is correct
33 Correct 112 ms 208560 KB Output is correct
34 Correct 114 ms 208612 KB Output is correct
35 Correct 106 ms 208328 KB Output is correct
36 Correct 116 ms 208328 KB Output is correct
37 Correct 109 ms 208324 KB Output is correct
38 Correct 113 ms 208428 KB Output is correct
39 Correct 105 ms 208440 KB Output is correct
40 Correct 124 ms 208388 KB Output is correct
41 Correct 71 ms 207560 KB Output is correct
42 Correct 84 ms 207556 KB Output is correct
43 Correct 72 ms 207664 KB Output is correct
44 Correct 76 ms 207672 KB Output is correct
45 Correct 71 ms 207812 KB Output is correct
46 Correct 115 ms 207820 KB Output is correct
47 Correct 100 ms 207820 KB Output is correct
48 Correct 117 ms 208000 KB Output is correct
49 Correct 96 ms 208076 KB Output is correct
50 Correct 112 ms 208356 KB Output is correct
51 Correct 141 ms 208848 KB Output is correct
52 Correct 155 ms 208844 KB Output is correct
53 Correct 130 ms 208840 KB Output is correct
54 Correct 127 ms 208840 KB Output is correct
55 Correct 137 ms 208792 KB Output is correct
56 Correct 134 ms 208844 KB Output is correct
57 Correct 136 ms 208820 KB Output is correct
58 Correct 137 ms 208828 KB Output is correct
59 Correct 133 ms 208944 KB Output is correct
60 Correct 129 ms 208840 KB Output is correct
61 Correct 131 ms 208840 KB Output is correct
62 Correct 131 ms 208840 KB Output is correct
63 Correct 141 ms 208840 KB Output is correct
64 Correct 161 ms 208844 KB Output is correct
65 Correct 133 ms 208844 KB Output is correct
66 Correct 153 ms 208960 KB Output is correct
67 Correct 129 ms 208864 KB Output is correct
68 Correct 151 ms 208940 KB Output is correct
69 Correct 149 ms 208848 KB Output is correct
70 Correct 140 ms 208840 KB Output is correct
71 Correct 88 ms 208068 KB Output is correct
72 Correct 106 ms 208072 KB Output is correct
73 Correct 89 ms 208068 KB Output is correct
74 Correct 90 ms 208072 KB Output is correct
75 Correct 92 ms 208068 KB Output is correct
76 Correct 103 ms 208256 KB Output is correct
77 Correct 100 ms 208340 KB Output is correct
78 Correct 104 ms 208380 KB Output is correct
79 Correct 106 ms 208484 KB Output is correct
80 Correct 100 ms 208324 KB Output is correct
81 Correct 124 ms 210232 KB Output is correct
82 Correct 133 ms 210236 KB Output is correct
83 Correct 135 ms 210328 KB Output is correct
84 Correct 134 ms 210376 KB Output is correct
85 Correct 138 ms 210360 KB Output is correct
86 Correct 125 ms 210116 KB Output is correct
87 Correct 125 ms 210112 KB Output is correct
88 Correct 122 ms 210112 KB Output is correct
89 Correct 152 ms 210112 KB Output is correct
90 Correct 126 ms 210116 KB Output is correct
91 Correct 200 ms 221780 KB Output is correct
92 Correct 180 ms 221636 KB Output is correct
93 Correct 181 ms 221632 KB Output is correct
94 Correct 179 ms 221636 KB Output is correct
95 Correct 183 ms 221632 KB Output is correct
96 Correct 206 ms 227012 KB Output is correct
97 Correct 196 ms 227012 KB Output is correct
98 Correct 190 ms 227012 KB Output is correct
99 Correct 207 ms 227008 KB Output is correct
100 Correct 198 ms 227008 KB Output is correct
101 Correct 195 ms 227008 KB Output is correct
102 Correct 199 ms 227008 KB Output is correct
103 Correct 192 ms 227004 KB Output is correct
104 Correct 190 ms 227012 KB Output is correct
105 Correct 201 ms 226996 KB Output is correct
106 Correct 204 ms 225476 KB Output is correct
107 Correct 198 ms 225476 KB Output is correct
108 Correct 178 ms 225476 KB Output is correct
109 Correct 220 ms 225356 KB Output is correct
110 Correct 192 ms 225472 KB Output is correct
111 Correct 193 ms 225476 KB Output is correct
112 Correct 215 ms 225540 KB Output is correct
113 Correct 189 ms 225440 KB Output is correct
114 Correct 208 ms 225476 KB Output is correct
115 Correct 195 ms 225472 KB Output is correct
116 Correct 1192 ms 209088 KB Output is correct
117 Correct 1344 ms 209052 KB Output is correct
118 Correct 1508 ms 209344 KB Output is correct
119 Correct 2025 ms 209600 KB Output is correct
120 Correct 2362 ms 209600 KB Output is correct
121 Correct 2610 ms 209860 KB Output is correct
122 Correct 2872 ms 209856 KB Output is correct
123 Correct 3837 ms 210368 KB Output is correct
124 Correct 4380 ms 210780 KB Output is correct
125 Correct 4398 ms 212932 KB Output is correct
126 Correct 4667 ms 210444 KB Output is correct
127 Correct 4662 ms 210560 KB Output is correct
128 Correct 4775 ms 210636 KB Output is correct
129 Correct 4790 ms 210564 KB Output is correct
130 Correct 4723 ms 210556 KB Output is correct
131 Correct 5040 ms 210616 KB Output is correct
132 Correct 5093 ms 210684 KB Output is correct
133 Correct 5046 ms 210712 KB Output is correct
134 Correct 5203 ms 210600 KB Output is correct
135 Correct 5177 ms 210628 KB Output is correct
136 Correct 5259 ms 210664 KB Output is correct
137 Correct 5135 ms 210636 KB Output is correct
138 Correct 5263 ms 210576 KB Output is correct
139 Correct 5317 ms 210604 KB Output is correct
140 Correct 5136 ms 210604 KB Output is correct
141 Correct 5732 ms 210624 KB Output is correct
142 Correct 5785 ms 210656 KB Output is correct
143 Correct 5849 ms 210664 KB Output is correct
144 Correct 5617 ms 210672 KB Output is correct
145 Correct 5718 ms 210656 KB Output is correct
146 Correct 6685 ms 211108 KB Output is correct
147 Correct 6694 ms 211116 KB Output is correct
148 Correct 6779 ms 211108 KB Output is correct
149 Correct 6726 ms 211096 KB Output is correct
150 Correct 6607 ms 211136 KB Output is correct
151 Correct 6728 ms 213440 KB Output is correct
152 Correct 6865 ms 213428 KB Output is correct
153 Execution timed out 7072 ms 212876 KB Time limit exceeded
154 Halted 0 ms 0 KB -