QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#90714#5258. MortgageDenisovAC ✓1054ms19460kbC++235.7kb2023-03-24 21:47:562023-03-24 21:47:58

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-24 21:47:58]
  • 评测
  • 测评结果:AC
  • 用时:1054ms
  • 内存:19460kb
  • [2023-03-24 21:47:56]
  • 提交

answer

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")
#include <bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
inline bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
inline bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef LOCAL
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define D while (false)
#define LOG(...)
#endif // LOCAL

const int max_n = -1;

vector <int> ans;
vector <ll> pref;


const ld inf = 1e18;
struct line {

    ll m, b; ld x;
    ll val; bool isQuery;
    line(ll _m = 0, ll _b = 0) :
        m(_m), b(_b), val(0), x(-inf), isQuery(false) {}

    ll eval(ll x) const { return m * x + b;    }
    bool parallel(const line &l) const { return m == l.m; }
    ld intersect(const line &l) const {
        return parallel(l) ? inf : 1.0 * (l.b - b) / (m - l.m);
    }
    bool operator < (const line &l) const {
        if(l.isQuery) return x < l.val;
        else return m < l.m;
    }
};
struct convex_hull_trick {
/// max
    set<line> hull;
    typedef set<line> :: iterator iter;

    bool cPrev(iter it) { return it != hull.begin(); }
    bool cNext(iter it) { return it != hull.end() && next(it) != hull.end(); }

    bool bad(const line &l1, const line &l2, const line &l3) {
        return l1.intersect(l3) <= l1.intersect(l2);
    }
    bool bad(iter it) {
        return cPrev(it) && cNext(it) && bad(*prev(it), *it, *next(it));
    }

    iter update(iter it) {
        if(!cPrev(it)) return it;
        ld x = it -> intersect(*prev(it));
        line tmp(*it); tmp.x = x;
        it = hull.erase(it);
        return hull.insert(it, tmp);
    }

    void addLine(ll m, ll b) {
        m *= -1;
        b *= -1;
        line l(m, b);
        iter it = hull.lower_bound(l);
        if(it != hull.end() && l.parallel(*it)) {
            if(it -> b < b) it = hull.erase(it);
            else return;
        }

        it = hull.insert(it, l);
        if(bad(it)) return (void) hull.erase(it);

        while(cPrev(it) && bad(prev(it))) hull.erase(prev(it));
        while(cNext(it) && bad(next(it))) hull.erase(next(it));

        it = update(it);
        if(cPrev(it)) update(prev(it));
        if(cNext(it)) update(next(it));
    }

    ll query(ll x) const {
        if(hull.empty()) return -inf;
        line q; q.val = x, q.isQuery = 1;
        iter it = --hull.lower_bound(q);
        return it -> eval(x);
    }

    inline void clear() {
        hull.clear();
    }

};
convex_hull_trick cht;

const int MX = 1e9 + 1;

inline void solve (int l, int r, vector <pair<pii, int> > &q) {
    if (l > r || q.empty()) {
        return;
    }
    int x = (l + r) >> 1;
    vector <pair<pii, int> > Q[3];
    for (auto &i : q) {
        if (i.first.second < x) {
            Q[0].pb(i);
        }
        else if (i.first.first > x) {
            Q[1].pb(i);
        }
        else {
            Q[2].pb(i);
        }
    }
    solve(l, x - 1, Q[0]);
    solve(x + 1, r, Q[1]);
    cht.clear();
    for (int i = x, j = len(Q[2]) - 1; i >= l; i--) {
        cht.addLine(-i, pref[i]);
        while (j >= 0 && Q[2][j].first.first == i) {
            int L = -1, R = MX;
            while (L < R) {
                int mid = (L + R + 1) >> 1;
                ll val = -cht.query(mid) - pref[i - 1] - (1ll - i) * mid;
                if (val >= 0) {
                    L = mid;
                }
                else {
                    R = mid - 1;
                }
            }
            umin(ans[Q[2][j].second], R);
            --j;
        }
    }
    cht.clear();
    sort(all(Q[2]), [&] (pair<pii, int> a, pair<pii, int> b) {
        return a.first.second < b.first.second;
    });
    for (int i = x, j = 0; i <= r; i++) {
        cht.addLine(-i, pref[i]);
        while (j < len(Q[2]) && Q[2][j].first.second == i) {
            int L = -1, R = MX;
            while (L < R) {
                int mid = (L + R + 1) >> 1;
                ll val = -cht.query(mid) - pref[Q[2][j].first.first - 1] - (1ll - Q[2][j].first.first) * mid;
                if (val >= 0) {
                    L = mid;
                }
                else {
                    R = mid - 1;
                }
            }
            umin(ans[Q[2][j].second], R);
            ++j;
        }
    }
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    pref.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> pref[i];
        pref[i] += pref[i - 1];
    }
    ans.assign(m, MX);
    vector <pair<pii, int> > q(m);
    for (int i = 0; i < m; i++) {
        cin >> q[i].first.first >> q[i].first.second;
        q[i].first.second += q[i].first.first - 1;
        q[i].second = i;
    }
    sort(all(q));
    solve(1, n, q);
    for (auto &i : ans) {
        if (i == -1) {
            cout << "stay with parents\n";
        }
        else {
            cout << i << '\n';
        }
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3336kb

input:

10 10
21 18 19 18 16 15 13 13 13 10
10 1
6 4
7 3
2 2
6 5
2 6
3 2
4 1
1 5
6 3

output:

10
13
13
18
12
16
18
18
18
13

result:

ok 10 lines

Test #2:

score: 0
Accepted
time: 3ms
memory: 3404kb

input:

1000 1000
196 207 195 207 200 203 202 204 205 191 190 188 203 198 201 188 203 198 196 196 200 195 200 206 193 198 186 196 200 185 202 195 203 199 185 199 202 191 184 194 195 194 193 195 184 197 189 193 186 187 193 193 196 186 195 193 186 192 188 188 187 197 179 188 195 196 197 186 194 183 189 185 19...

output:

158
16
110
64
160
118
169
63
172
128
93
82
118
119
86
32
174
145
139
84
149
120
133
155
108
110
65
178
90
99
118
91
133
85
151
76
130
50
91
99
95
78
110
87
119
141
68
81
172
82
112
139
136
81
79
16
51
31
104
116
108
38
75
176
156
55
165
112
146
74
68
172
112
157
94
177
111
166
110
112
98
155
109
155...

result:

ok 1000 lines

Test #3:

score: 0
Accepted
time: 4ms
memory: 3428kb

input:

1000 1000
1023 912 1076 907 1015 1078 1075 1031 930 925 925 960 1013 893 1052 920 967 1046 960 1077 888 883 1045 1049 1034 1062 967 1021 986 938 871 916 901 1032 1003 1020 900 909 920 1048 884 859 1016 922 945 955 1002 1033 947 1025 970 862 929 908 912 956 873 845 933 873 921 918 904 884 1033 900 99...

output:

220
651
401
454
516
692
597
294
779
418
468
679
293
348
920
172
554
303
282
104
580
824
569
376
221
226
454
232
794
469
788
925
394
308
245
624
614
422
252
407
149
529
178
612
584
429
629
357
477
886
896
517
114
762
560
546
516
735
275
818
304
608
214
685
205
561
470
826
844
335
618
327
651
799
843
...

result:

ok 1000 lines

Test #4:

score: 0
Accepted
time: 4ms
memory: 3448kb

input:

1000 1000
938 360 206 545 664 694 717 653 217 681 574 932 125 191 677 87 875 177 253 29 748 915 222 288 771 785 233 112 922 847 473 267 365 610 76 404 776 3 821 971 730 988 652 263 525 233 91 821 319 876 467 617 271 899 53 650 874 369 746 307 592 915 309 93 387 885 800 387 617 382 928 963 540 943 22...

output:

335
9
125
426
415
352
362
292
456
475
399
477
341
387
500
475
201
483
246
509
280
496
407
433
470
445
340
459
472
439
472
411
458
327
227
428
207
363
77
267
231
204
333
387
137
315
23
33
471
313
37
202
31
177
425
125
403
177
371
480
329
468
163
340
416
458
202
202
143
345
478
17
383
375
493
213
382
...

result:

ok 1000 lines

Test #5:

score: 0
Accepted
time: 4ms
memory: 3432kb

input:

1000 1000
45 -80 65 -47 -17 75 49 79 38 65 25 64 53 74 0 -43 38 22 -48 -6 37 12 24 -36 -9 9 -64 -66 -31 91 -5 29 62 98 56 133 64 59 93 -6 97 89 7 121 125 21 39 95 131 60 -33 -4 6 63 52 44 25 -38 24 -40 94 135 129 129 13 87 28 -10 -13 168 128 140 1 152 52 88 99 107 88 81 176 18 73 29 93 165 50 146 13...

output:

419
136
345
312
338
1
490
557
177
84
50
688
315
784
141
244
stay with parents
53
408
218
764
451
127
371
823
805
349
552
167
523
stay with parents
500
3
52
411
51
699
422
435
278
187
134
252
585
108
583
44
55
109
310
167
879
712
stay with parents
336
311
108
stay with parents
51
434
stay with parent...

result:

ok 1000 lines

Test #6:

score: 0
Accepted
time: 3ms
memory: 3396kb

input:

1000 1000
210 201 195 208 191 209 201 195 201 192 199 200 205 188 200 198 197 207 189 199 194 197 206 186 198 204 203 187 200 201 197 197 191 197 192 191 192 188 189 194 197 191 192 182 184 195 192 183 200 193 193 193 192 190 190 194 182 197 180 191 184 181 189 184 186 180 194 197 194 187 196 196 18...

output:

92
92
102
93
89
114
149
105
72
114
87
71
77
171
90
36
127
136
39
165
92
62
157
135
101
82
87
78
136
99
141
73
109
141
23
73
76
112
58
110
105
97
84
181
19
100
127
76
108
109
49
150
165
159
152
101
108
94
25
87
67
78
127
56
37
50
161
131
142
40
47
73
117
169
87
157
109
121
59
75
184
80
67
82
48
61
65...

result:

ok 1000 lines

Test #7:

score: 0
Accepted
time: 3ms
memory: 3460kb

input:

1000 1000
1000 998 998 998 997 994 994 992 991 991 991 989 987 987 987 986 984 983 982 982 981 979 978 976 975 974 973 972 973 971 969 968 968 968 965 964 963 963 963 960 961 959 957 958 956 955 955 952 951 951 950 949 950 948 947 947 945 943 944 942 940 940 940 938 938 936 936 935 932 932 930 931 9...

output:

598
365
299
422
294
499
645
316
469
475
612
702
612
344
324
424
597
418
241
488
471
618
640
946
673
350
728
925
628
315
389
499
314
216
215
692
600
149
283
826
648
415
639
666
849
273
536
683
339
747
564
380
483
368
555
471
500
959
364
337
441
648
655
342
542
605
676
386
643
80
628
581
149
544
560
9...

result:

ok 1000 lines

Test #8:

score: 0
Accepted
time: 4ms
memory: 3412kb

input:

1000 1000
1 3 2 4 4 6 7 7 10 9 10 12 12 14 14 15 18 19 18 21 21 23 23 23 24 27 27 29 28 29 31 31 33 33 34 36 37 38 38 39 41 41 42 43 44 46 46 49 49 49 50 52 52 55 55 56 58 59 59 59 60 63 64 63 65 65 68 69 69 70 72 71 72 73 76 77 77 79 80 81 82 83 82 83 86 86 88 87 90 89 91 93 93 95 94 97 98 98 98 10...

output:

783
72
634
21
295
234
337
241
823
69
52
39
9
209
270
21
478
802
576
49
232
145
583
516
361
46
519
651
150
459
195
204
31
602
553
266
10
656
398
98
331
584
29
332
296
357
198
595
241
239
401
414
543
288
144
283
187
277
222
803
732
503
2
195
620
481
320
155
438
276
59
142
538
684
127
192
446
243
491
2...

result:

ok 1000 lines

Test #9:

score: 0
Accepted
time: 718ms
memory: 11496kb

input:

200000 200000
4700652 -5734778 3503665 -6188002 8657410 2276806 -6431469 9627247 9673670 9221683 -3908423 -3069613 -653905 2608836 -4959288 -3108645 2053787 -5840353 259545 9847990 2267414 4231267 8319662 9920009 1973822 3854711 9434531 5938280 -5348422 -4062145 -5060918 -3946777 -7934092 7908462 83...

output:

531534449
60349244
698110493
683183122
239017077
155761236
198479042
224389969
53360136
280044750
690025597
359180266
155492131
100215867
7489229
371149856
257552128
756373561
625758735
10281065
33154057
331682245
187783019
356644222
284214063
184871804
232220709
282778596
659349476
574267601
271559...

result:

ok 200000 lines

Test #10:

score: 0
Accepted
time: 481ms
memory: 11120kb

input:

200000 200000
1000000000 1000000000 1000000000 994665379 991463472 993592249 990545330 1000000000 1000000000 993709443 993048450 993175969 1000000000 1000000000 1000000000 1000000000 996652523 1000000000 992737565 1000000000 995381198 999029778 994486837 1000000000 1000000000 1000000000 993523414 99...

output:

435875275
457648009
211124733
489445386
272681020
170279466
457584046
180315969
724633614
337953745
382261536
544196655
49729496
125390351
80990952
414848358
237788201
264980067
590869611
767628306
442404587
573389407
358308533
673491043
546282286
623796355
310334534
305536304
643892535
451194211
31...

result:

ok 200000 lines

Test #11:

score: 0
Accepted
time: 458ms
memory: 10996kb

input:

200000 200000
999936527 1000000000 1000000000 999911064 1000000000 999931025 999987503 999873607 999979442 999867372 999998797 999903420 999942880 999836369 999961944 999997043 999859703 1000000000 999872353 999967979 999895588 999873633 999989612 999939739 999929350 999959172 999826478 999898163 99...

output:

685852606
779027428
767670633
407552348
429157344
536572435
820750082
343199906
153240019
172312558
696380287
469815009
494985027
476719828
619352415
34133816
684452544
206679853
506577503
272757735
230547389
483884971
511887454
396592355
161362798
407519861
605254754
258882877
746577675
73817816
75...

result:

ok 200000 lines

Test #12:

score: 0
Accepted
time: 879ms
memory: 12128kb

input:

200000 200000
29091 38973 -43929 -59096 85131 -48337 55517 -33006 114388 88422 7767 -40627 51481 72946 50475 -11447 34620 163684 152282 17662 127085 117685 96487 130743 48134 216283 135263 86053 82895 96458 120002 55804 119261 211075 164992 157722 254034 265948 189624 138315 217932 180546 277174 157...

output:

243257560
912832934
310015430
101031560
763481383
163629518
514370005
76106312
84131976
6965181
562147379
643978961
377798707
623798585
726189886
624382491
700519954
442408520
215468449
128115935
259664291
514835375
319905852
89344678
414911644
447441446
407846688
188468274
273723302
73973026
385489...

result:

ok 200000 lines

Test #13:

score: 0
Accepted
time: 582ms
memory: 11164kb

input:

200000 200000
478661126 262135998 865858988 810996444 591942227 735500821 501689749 50371518 517447906 446463295 608437123 167043833 827378253 748574239 756186328 580692189 517172087 443374960 523720487 881889997 117184442 337424808 411056272 500688800 480471810 143343364 535362952 859590020 5707259...

output:

272999720
315747073
257419408
189314016
356413659
147502771
180971112
483448182
426842843
378086080
176669194
80835598
216151657
369651435
384795439
496220857
86118937
348241535
444535257
387577828
147119493
342572677
34041459
330955795
468414923
484368631
268057725
393103897
58717209
282747703
3721...

result:

ok 200000 lines

Test #14:

score: 0
Accepted
time: 532ms
memory: 11092kb

input:

200000 200000
294832171 -327658233 662058359 -810653343 -625990848 120657884 -976742718 729067584 -794355628 -907624514 -18150063 881125723 60482279 562743356 -401926055 135101492 -933157390 831548262 344876913 312305225 605857917 170214669 -806582706 -796932016 988860514 -674531379 -806347473 -3319...

output:

stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with pa...

result:

ok 200000 lines

Test #15:

score: 0
Accepted
time: 1054ms
memory: 19460kb

input:

200000 200000
-115 5684 9666 14889 19500 24791 29979 35076 39517 44226 49871 55618 60521 65324 70881 75009 80102 85772 90581 95968 100435 105969 110891 115806 120783 124075 129105 134658 140322 144984 150821 155933 160753 165985 170677 174002 180757 184590 189474 194645 200562 205274 209745 214890 2...

output:

487754816
148845568
533460296
274270708
334714248
516345330
122364942
464210262
586120601
753660346
824860348
298260873
296325973
477055095
361450664
206315763
91844684
138950455
147594323
399949576
533145826
306884304
335329718
313459627
750359129
79690485
537295793
877189280
664030013
266225862
64...

result:

ok 200000 lines

Test #16:

score: 0
Accepted
time: 425ms
memory: 11056kb

input:

200000 200000
999999438 999994121 999990963 999984265 999979994 999975607 999970032 999964839 999959530 999954639 999949517 999945232 999939568 999934480 999930947 999925049 999920728 999914933 999910428 999904124 999899891 999894253 999890668 999885182 999879535 999874719 999870139 999864703 999860...

output:

442837499
247532495
768915002
592024999
313189997
323892498
830032502
749387498
559512500
449432498
629235000
577270000
640277500
497827500
599900004
817349998
299582492
669992500
384737501
464914999
723607499
795402502
639147500
316219989
109647500
469607499
563704999
357369999
629572500
639892501
...

result:

ok 200000 lines

Test #17:

score: 0
Accepted
time: 530ms
memory: 11036kb

input:

200000 200000
191 199 206 199 197 201 204 206 205 193 209 202 195 202 205 208 208 206 207 191 205 192 196 196 201 202 190 192 200 206 190 205 191 200 191 195 205 194 204 190 204 208 205 210 200 193 196 194 195 192 205 209 206 200 199 202 199 191 195 195 205 190 197 202 194 191 204 197 208 199 196 18...

output:

40
67
19
50
40
96
22
75
20
58
53
74
19
58
39
134
86
82
16
4
65
9
31
74
69
28
74
17
80
46
85
52
21
15
65
81
77
34
71
44
48
71
49
50
24
96
121
159
104
96
103
41
32
51
3
23
10
46
96
65
50
81
39
103
101
94
78
34
104
104
99
32
17
103
190
98
46
65
99
24
47
91
143
11
13
84
34
44
70
60
68
68
48
12
55
94
154...

result:

ok 200000 lines

Test #18:

score: 0
Accepted
time: 490ms
memory: 11064kb

input:

200000 200000
1059 1069 994 1089 1010 932 1019 981 991 1036 1037 1055 1098 967 924 940 979 1021 1040 1010 998 1092 1012 930 946 997 986 1007 912 918 917 1040 955 905 918 964 968 901 995 1016 1011 1005 1092 1051 990 981 1060 1081 1070 985 1081 1087 1038 1078 961 1092 1077 1098 913 1027 1035 954 1009 ...

output:

143
491
717
733
354
712
579
552
346
451
759
794
282
226
235
663
669
154
378
294
388
223
537
735
875
368
662
856
315
765
652
778
391
315
494
574
379
396
785
609
557
371
522
382
333
794
254
272
682
560
620
455
541
517
531
600
66
563
602
648
732
161
55
644
668
59
494
507
301
563
324
218
339
465
544
913...

result:

ok 200000 lines

Test #19:

score: 0
Accepted
time: 551ms
memory: 10992kb

input:

200000 200000
963 469 53 741 13 335 145 806 737 314 524 461 507 991 644 670 157 128 663 394 45 95 887 413 955 761 840 139 196 18 179 375 702 131 367 123 312 576 710 56 755 57 322 924 157 348 70 480 334 121 399 894 449 754 598 890 449 79 696 431 248 999 880 920 590 754 11 223 982 352 657 277 887 569 ...

output:

365
424
98
325
410
274
448
230
217
269
458
438
265
471
312
447
412
269
60
86
208
149
428
417
432
337
367
471
186
463
125
402
414
296
311
149
300
481
290
366
162
449
220
359
415
429
442
209
383
251
283
241
264
19
472
275
262
399
492
474
248
485
80
455
419
179
120
182
12
24
483
208
271
485
331
390
173...

result:

ok 200000 lines

Test #20:

score: 0
Accepted
time: 645ms
memory: 11176kb

input:

200000 200000
3744830 1595361 8644139 101223 -5065373 3046578 -5695328 5229211 9229269 4232412 -488563 1136902 -2976454 -3137918 -492040 5274343 714575 -5071761 -4767765 8447286 -4580658 -2777522 7877546 6762178 -511328 7701731 -5479689 -4140308 10815008 -6379209 979729 -658142 3062119 244629 -68119...

output:

164541327
231925274
485949823
382241474
66239125
134584675
369469489
359270868
148308240
393656548
332556052
90244039
311109379
480583042
681768979
349142880
339020945
498041073
373819995
270911991
436908849
24620722
376650900
190999823
30043649
124141801
333242305
13772820
439930708
457196941
35452...

result:

ok 200000 lines

Test #21:

score: 0
Accepted
time: 661ms
memory: 10964kb

input:

200000 200000
1000000000 992069588 998058262 993630131 1000000000 998009037 992640887 996313911 1000000000 1000000000 997242506 990273866 996733179 1000000000 1000000000 999687007 992122101 1000000000 994583329 994252684 991466636 1000000000 1000000000 990603983 990745725 996917208 1000000000 100000...

output:

602850723
407945893
690749180
405539613
75472016
151629377
23366515
30587352
142571226
35472747
717307477
485800912
236768150
214831743
485173227
26291507
6592224
215059425
432972275
467743059
15025584
498855040
478039077
158420254
173915820
168219306
212616098
155863013
481719941
499912959
27142348...

result:

ok 200000 lines

Test #22:

score: 0
Accepted
time: 812ms
memory: 12084kb

input:

200000 200000
1000000000 999933615 999996696 999782704 999746414 999697610 999777898 999596836 999541770 999583902 999537341 999476323 999443707 999268912 999262461 999245242 999257429 999054541 999041057 998955682 999011081 998875271 998809683 998859231 998787903 998816004 998751925 998550019 99854...

output:

177769668
180196829
231741515
148341542
167207333
112273574
355201123
466637635
484253164
7342460
675257785
299380388
486767996
931674517
41381379
388251463
565133169
311229641
450152398
130329852
204134384
153304085
42362352
337096089
499407773
164323924
391016449
827002292
72144794
454225319
16709...

result:

ok 200000 lines

Test #23:

score: 0
Accepted
time: 748ms
memory: 12220kb

input:

200000 200000
52491 101174 100384 123766 142794 175535 377471 414249 421320 484587 575866 571991 687415 661766 778890 714517 713128 868707 828179 866918 1077040 1066369 1064155 1178331 1210485 1337087 1236851 1431031 1493952 1456169 1564124 1501166 1565077 1704573 1668912 1798039 1897674 1865914 188...

output:

419825049
403455034
91967129
62765383
294912624
336765966
441670520
13345601
259597998
401631796
181125194
139455528
1743269
53093487
88814603
268575512
720450151
487435097
141795835
276140187
237428704
476413124
17328144
321618
207820988
397589252
225115621
350940240
494623420
525631
284803006
4784...

result:

ok 200000 lines

Test #24:

score: 0
Accepted
time: 607ms
memory: 11068kb

input:

200000 200000
405747825 711836834 581094376 82889349 243083937 479445162 998260260 362049662 657927422 647775846 538825320 567081690 238943928 963221462 596011092 867289958 577760940 697266484 177737089 35577631 581988738 265711945 924826397 740391180 809718864 208497675 518371637 490425395 34297375...

output:

294107551
263110021
267650733
142972236
433069091
263118994
95478990
150264575
169322366
417533797
462877245
470448524
483183992
467392168
356964693
405907735
447929155
51597875
224955427
334077401
443197541
213544308
347167897
350443095
371968799
474484551
493424744
383696744
426816711
162543715
45...

result:

ok 200000 lines

Test #25:

score: 0
Accepted
time: 550ms
memory: 10956kb

input:

200000 200000
-554176658 750721642 -22411758 567853365 -147607202 203633157 -697381474 -379454201 373014620 740869948 899526648 -932177542 -22094364 83192324 -149932156 -406679372 786617866 -530220862 -693189961 -593618993 478812406 -151135019 349929776 527393598 400819915 602353366 191931610 308200...

output:

stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
stay with pa...

result:

ok 200000 lines

Test #26:

score: 0
Accepted
time: 809ms
memory: 12712kb

input:

200000 200000
17 50311 99910 150519 200749 249287 300712 349222 399697 449892 499793 550447 599045 650260 700180 750441 800091 850093 900100 949403 1000408 1050984 1100258 1149747 1199502 1249381 1300546 1349746 1400378 1450739 1499660 1550378 1600160 1650694 1699114 1750029 1800804 1850740 1900371 ...

output:

342689230
157390787
252701340
476299222
59035783
485599195
498860446
74403114
471250705
440895122
217749320
192164032
454062012
50254440
605749795
349100625
126573293
139227542
155149425
421959147
422324999
346999175
495060401
492554886
480281766
267399379
444049755
22605686
339831157
557449145
4524...

result:

ok 200000 lines

Test #27:

score: 0
Accepted
time: 845ms
memory: 12600kb

input:

200000 200000
1000000000 999949059 999900589 999850206 999799859 999750077 999700777 999650351 999599178 999550142 999499980 999449261 999400745 999349030 999299479 999249824 999199297 999150578 999100025 999050724 998999545 998949117 998900101 998850280 998800810 998749075 998699489 998649084 99859...

output:

737300324
493292718
236443465
473090079
169449565
64586237
120463660
467197886
612949244
224000382
477185489
145689274
152233838
537475012
433149992
448600763
53982390
190734991
62245950
493168443
87399386
396499716
98249616
350642135
89649990
111765174
662173823
119821631
430386109
218710958
367811...

result:

ok 200000 lines

Test #28:

score: 0
Accepted
time: 37ms
memory: 4460kb

input:

199659 222
999999930 999999952 999999935 999999908 999999936 999999960 999999921 999999922 999999988 999999963 999999968 999999981 999999937 999999984 999999906 999999994 999999996 999999933 999999969 1000000000 999999970 999999954 999999927 999999990 999999937 999999914 999999962 999999981 99999994...

output:

87915448
45418842
80436042
137419507
stay with parents
stay with parents
stay with parents
135157819
stay with parents
106892737
52367921
stay with parents
stay with parents
102268086
102253799
117130487
stay with parents
119772850
stay with parents
103917778
131201306
stay with parents
stay with pa...

result:

ok 222 lines

Test #29:

score: 0
Accepted
time: 45ms
memory: 4488kb

input:

199810 221
999999909 999999959 999999908 999999913 999999936 999999956 999999990 999999961 999999956 999999991 999999999 999999991 999999980 999999925 999999910 999999945 999999927 999999905 999999998 999999929 999999938 999999907 999999940 999999962 999999900 999999926 999999999 999999919 999999925...

output:

3213348
10529638
104885755
123186646
stay with parents
24648842
14606030
132581462
86964589
123911772
stay with parents
stay with parents
59060049
69327991
stay with parents
stay with parents
stay with parents
stay with parents
104684080
40902732
120109551
stay with parents
43777139
109732064
573551...

result:

ok 221 lines

Test #30:

score: 0
Accepted
time: 47ms
memory: 4488kb

input:

199181 222
999999966 999999966 999999960 999999933 999999910 999999913 999999956 999999906 999999930 999999975 999999923 999999987 999999933 999999917 999999918 999999989 999999990 999999935 999999931 999999989 999999940 999999932 999999944 999999980 999999936 999999957 999999998 999999921 999999956...

output:

118720579
24168975
69373979
47006645
62333077
stay with parents
116934453
stay with parents
25941369
91392565
27012581
7747260
75640888
76504079
stay with parents
97136696
stay with parents
stay with parents
stay with parents
stay with parents
stay with parents
70163377
stay with parents
7165085
121...

result:

ok 222 lines

Test #31:

score: 0
Accepted
time: 37ms
memory: 4460kb

input:

199279 222
999999946 999999907 999999954 999999941 999999903 999999993 999999938 999999916 999999938 999999986 999999904 999999945 999999929 999999950 999999958 999999947 999999903 999999924 999999998 999999983 999999953 999999951 999999951 999999957 999999972 999999965 999999968 999999912 999999909...

output:

63174768
121421457
99552861
89890393
85949647
stay with parents
120281251
stay with parents
stay with parents
73743670
48439126
56534072
14557112
50830665
83889744
41446389
75322951
44546582
52684843
stay with parents
stay with parents
91137950
stay with parents
stay with parents
stay with parents
9...

result:

ok 222 lines

Test #32:

score: 0
Accepted
time: 36ms
memory: 4548kb

input:

199464 221
999999998 999999953 999999999 999999969 999999954 999999919 999999974 999999924 999999949 999999907 999999909 999999982 999999904 999999912 999999987 999999911 999999945 999999929 999999967 999999923 999999953 999999933 999999977 999999928 999999938 999999932 999999927 999999904 999999920...

output:

stay with parents
119260326
117339414
37262260
136218960
stay with parents
38960962
stay with parents
80441994
101703450
30958202
71434083
15832805
stay with parents
45852128
74497995
stay with parents
92394927
stay with parents
108853030
83388079
87862347
stay with parents
stay with parents
1071767...

result:

ok 221 lines