QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#749464	#7467. 遥远的过去	TheZone	150 ✓	172ms	15524kb	C++11	4.3kb	2024-11-15 01:08:26	2024-11-15 01:08:26

Judging History

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

[2024-11-15 01:08:26]
评测

测评结果：150
用时：172ms
内存：15524kb

查看

[2024-11-15 01:08:26]
提交

answer

#include<bits/stdc++.h>
#define N 200050
#define ls ch[x][0]
#define rs ch[x][1]
#define ll unsigned long long
using namespace std;
int size[N], ch[N][2], fa[N], root, v[N], n, m, q;
ll ha[N], mi[N], S;
const ll B = 11117;
const ll mod = 100003;
void update(int x) {
    size[x] = size[ls] + size[rs] + 1;
    ha[x] = ha[ls] + mi[size[ls]] * (ll)x + mi[size[ls] + 1] * ha[rs];
}
int get(int x) {
    return ch[fa[x]][1] == x;
}
void rotate(int x) {
    int f = fa[x], gf = fa[f], k = get(x);
    if(!f) return ;
    if(gf) ch[gf][get(f)] = x; fa[x] = gf;
    ch[f][k] = ch[x][!k], fa[ch[x][!k]] = f;
    ch[x][!k] = f, fa[f] = x;
    update(f), update(x);
}
inline void splay(int x) {
    int f = fa[x];
    while(f) {
        if(fa[f]) rotate(get(x) == get(f)? f : x);
        rotate(x);
        f = fa[x];
       // printf("%d %d\n", x, f);
    }
    root = x;
}
void insert(int &x, int id, int f) {
   // printf("%d %d %d   \n", x, id, f);
    if(!x) {x = id; fa[x] = f; update(x); splay(x); return ;}
    if(v[id] < v[x]) insert(ls, id, x);
    else insert(rs, id, x);
}
void clear(int x) {
    fa[x] = ls = rs = size[x] = 0;
}
void del(int x) {
    splay(x);
    if(!ls || !rs) {root = ls + rs; fa[root] = 0; clear(x); return ; }
    int now = ls;
    while(ch[now][1]) now = ch[now][1];
    splay(now);
    ch[now][1] = ch[x][1], fa[ch[x][1]] = now;
    clear(x); update(now);
}
void deb(int x) {
    if(!x) return ;
    deb(ls);
    printf(" %d %d %d   ", x, ls, rs);
    deb(rs);
}


struct HAT {
    int nxt, s;
    ll val;
} e[N << 1];
int p[N], eid;
void init() {
    memset(p, -1, sizeof p);
    eid = 0;
}
void INS(ll x) {
    int u = x % mod;
    for(int i = p[u]; i + 1; i = e[i].nxt) {
        if(x == e[i].val) { ++ e[i].s; return ;}
    }
    e[eid].val = x, e[eid].s = 1, e[eid].nxt = p[u];
    p[u] = eid ++;
}
int QRY(ll x) {
    int u = x % mod;
    for(int i = p[u]; i + 1; i = e[i].nxt) {
        if(x == e[i].val)  return e[i].s;
    } return 0;
}
int main() {
    init();
    scanf("%d%d%d", &n ,&m, &q);
    mi[0] = 1;
    for(int i = 1; i <= n; i ++) mi[i] = mi[i - 1] * B;
    
    for(int i = 1; i <= n; i ++) scanf("%d", &v[i]);
    
    for(int i = 1; i <= m; i ++) insert(root, i, 0), S += mi[i - 1];
    for(int i = m; i <= n; i ++) {
        INS(ha[root] - S * (i - m));
      //  printf("\n **  %llu   ", ha[root]); deb(root); printf("\n");
        del(i - m + 1);
     //   printf("\n **  "); deb(root); printf("\n");
        insert(root, i + 1, 0);
    }
    root = 0;
    
    memset(ch, 0, sizeof ch), memset(fa, 0, sizeof fa);
    for(int i = 1; i <= m; i ++) scanf("%d", &v[i]), insert(root, i, 0);
    while(q --) {
        int x, y;
        scanf("%d%d", &x, &y);
        del(x);
        v[x] = y; insert(root, x, 0);
        printf("%d\n", QRY(ha[root]));
    }
    return 0;
}
/*#include<bits/stdc++.h>
#define N 200050
#define ls ch[x][0]
#define rs ch[x][1]
#define ll unsigned long long
using namespace std;
int size[N], ch[N][2], fa[N], root, v[N], n, m, q;
ll ha[N], mi[N], S;
const ll B = 11117;
const ll mod = 100003;
void update(int x) {
    size[x] = size[ls] + size[rs] + 1;
    ha[x] = ha[ls] + mi[size[ls]] * (ll)x + mi[size[ls] + 1] * ha[rs];
}
int get(int x) {
    return ch[fa[x]][1] == x;
}
void rotate(int x) {
    int f = fa[x], gf = fa[f], k = get(x);
    if(!f) return ;
    if(gf) ch[gf][get(f)] = x; fa[x] = gf;
    ch[f][k] = ch[x][!k], fa[ch[x][!k]] = f;
    ch[x][!k] = f, fa[f] = x;
    update(f), update(x);
}
inline void splay(int x) {
    int f = fa[x];
    while(f) {
        if(fa[f]) rotate(get(x) == get(f)? f : x);
        rotate(x);
        f = fa[x];
       // printf("%d %d\n", x, f);
    }
    root = x;
}
void insert(int &x, int id, int f) {
   // printf("%d %d %d   \n", x, id, f);
    if(!x) {x = id; fa[x] = f; update(x); splay(x); return ;}
    if(v[id] < v[x]) insert(ls, id, x);
    else insert(rs, id, x);
}
void clear(int x) {
    fa[x] = ls = rs = size[x] = 0;
}
void del(int x) {
    splay(x);
    if(!ls || !rs) {root = ls + rs; fa[root] = 0; clear(x); return ; }
    int now = ls;
    while(ch[now][1]) now = ch[now][1];
    splay(now);
    ch[now][1] = ch[x][1], fa[ch[x][1]] = now;
    clear(x); update(now);

}
*/

Source code, Language: C++11

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 31

Accepted

Test #1:

score: 31

Accepted

time: 0ms

memory: 10724kb

input:

100 10 1000
1 74 77 37 94 76 51 75 97 53 61 85 25 15 11 32 67 49 99 55 80 60 41 26 93 71 63 20 33 88 31 81 27 6 54 73 45 90 2 13 59 22 19 58 66 17 10 91 21 65 89 34 78 69 8 87 5 12 57 24 29 82 28 83 56 92 95 43 64 9 46 98 38 52 79 48 35 3 16 30 18 100 86 23 68 36 70 39 44 84 50 96 47 7 40 14 62 72 4...

output:

result:

ok 1000 numbers

Test #2:

score: 31

Accepted

time: 0ms

memory: 12532kb

input:

100 10 1000
1 25 81 17 41 89 59 61 23 16 32 51 45 85 49 92 5 60 3 67 100 46 93 47 26 53 69 76 88 75 34 73 44 55 37 8 10 6 77 83 95 97 71 14 2 29 36 87 7 19 79 21 68 72 96 57 11 28 50 43 35 82 38 91 13 64 9 54 39 56 62 33 52 63 84 65 31 98 27 12 94 58 70 86 15 78 99 18 66 22 80 90 30 74 4 40 24 20 42...

output:

result:

ok 1000 numbers

Test #3:

score: 31

Accepted

time: 0ms

memory: 10244kb

input:

100 10 1000
1 16 81 67 51 2 84 69 83 41 10 73 36 85 94 11 57 71 39 13 31 33 65 15 90 37 23 75 49 93 89 91 97 17 77 59 98 63 3 61 29 53 60 46 80 45 28 54 100 26 40 48 21 79 52 25 34 22 82 30 19 20 92 27 38 4 50 6 12 43 9 18 86 78 7 87 64 35 70 66 95 8 68 76 42 5 99 47 56 24 32 74 44 96 62 55 14 72 58...

output:

result:

ok 1000 numbers

Test #4:

score: 31

Accepted

time: 0ms

memory: 9944kb

input:

100 10 1000
1 81 11 72 45 96 61 33 5 75 92 43 14 74 15 87 13 31 53 41 97 85 26 88 93 63 21 17 47 65 58 54 3 73 22 77 51 57 25 32 9 95 10 35 46 50 94 76 79 2 71 4 19 83 49 44 16 6 86 18 69 23 89 91 100 40 29 30 37 48 27 64 52 38 12 24 98 55 66 60 34 68 39 36 56 62 99 7 90 82 8 67 78 59 28 80 42 84 70...

output:

result:

ok 1000 numbers

Test #5:

score: 31

Accepted

time: 3ms

memory: 13060kb

input:

100 10 1000
1 51 21 37 89 71 20 58 81 13 61 33 62 93 3 15 69 94 66 31 41 65 77 87 11 63 96 42 19 44 23 80 73 39 75 28 46 57 78 83 38 52 14 95 22 6 97 7 53 70 25 99 36 76 4 43 5 91 24 45 2 64 8 55 27 86 26 9 47 10 17 79 90 16 67 35 30 85 92 49 54 50 18 34 68 100 29 40 82 56 84 72 12 48 59 32 60 98 74...

output:

result:

ok 1000 numbers

Test #6:

score: 31

Accepted

time: 0ms

memory: 10660kb

input:

100 10 1000
1 93 71 95 6 76 81 10 97 17 61 98 33 72 54 67 41 25 20 5 45 43 77 36 91 75 57 85 46 31 52 59 86 56 29 34 53 21 26 64 11 73 19 37 39 89 99 48 79 84 66 94 9 65 27 23 47 69 3 83 55 87 14 51 40 60 58 100 24 7 49 50 13 88 16 35 4 82 18 15 42 8 44 74 96 63 78 38 92 30 12 68 70 2 90 32 80 28 22...

output:

result:

ok 1000 numbers

Test #7:

score: 31

Accepted

time: 2ms

memory: 10524kb

input:

100 10 1000
1 98 85 61 48 97 41 55 49 44 77 29 31 39 21 36 14 47 93 6 10 16 9 91 43 46 81 38 67 8 65 51 5 75 7 99 69 45 96 83 70 74 95 76 79 52 19 54 56 17 94 33 66 87 11 59 53 73 37 86 15 92 42 30 3 12 13 63 90 2 71 27 50 20 72 26 57 89 78 58 32 82 18 40 100 35 80 88 25 84 28 60 4 62 23 64 24 34 22...

output:

result:

ok 1000 numbers

Test #8:

score: 31

Accepted

time: 2ms

memory: 10168kb

input:

100 10 1000
1 11 15 81 79 18 61 13 85 21 57 27 56 70 89 73 19 67 29 46 74 91 55 3 53 93 23 16 86 77 26 64 49 87 25 51 35 66 31 37 97 39 33 7 12 41 22 62 45 52 38 95 17 10 58 48 9 36 78 59 63 76 90 34 5 50 44 83 40 47 96 80 32 99 69 2 88 14 92 24 98 43 71 75 68 54 20 6 65 42 72 8 4 82 94 30 28 84 60 ...

output:

result:

ok 1000 numbers

Test #9:

score: 31

Accepted

time: 0ms

memory: 9956kb

input:

100 10 1000
1 53 25 49 56 33 9 52 13 85 41 96 89 31 29 97 21 63 46 4 45 100 87 43 30 61 37 19 40 81 27 86 51 16 99 68 48 74 64 58 65 71 83 59 36 44 57 10 93 23 73 70 80 69 47 50 95 55 35 2 11 76 39 17 26 91 67 24 5 6 28 15 75 38 32 14 84 72 98 66 18 60 3 77 62 12 94 79 7 78 54 90 82 20 22 92 8 88 34...

output:

result:

ok 1000 numbers

Test #10:

score: 31

Accepted

time: 2ms

memory: 9952kb

input:

100 10 1000
1 99 76 93 86 53 59 13 33 46 97 85 11 45 36 41 19 7 90 31 44 51 57 43 82 91 39 37 35 17 67 50 55 56 9 2 25 29 12 48 6 71 52 5 21 23 92 18 81 65 26 87 73 63 27 78 54 16 47 75 15 100 61 64 69 28 79 38 32 89 34 3 95 66 84 77 49 58 42 96 20 83 24 74 62 60 98 70 22 94 80 72 10 14 40 30 4 8 88...

output:

result:

ok 1000 numbers

Subtask #2:

score: 41

Accepted

Test #11:

score: 41

Accepted

time: 19ms

memory: 10896kb

input:

1000 100 50000
1 225 816 1250 1677 1511 1919 44 338 994 849 1361 1251 418 1941 101 1893 185 1775 107 449 723 1191 862 275 1233 1158 1161 836 1254 1924 1717 1353 1209 1851 1641 1265 1819 1151 1633 489 629 929 1437 477 721 813 1243 1931 193 1029 966 261 67 401 1470 1993 1010 736 311 1807 39 105 436 27...

output:

result:

ok 50000 numbers

Test #12:

score: 41

Accepted

time: 20ms

memory: 10744kb

input:

1000 500 50000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...

output:

result:

ok 50000 numbers

Test #13:

score: 41

Accepted

time: 5ms

memory: 11040kb

input:

1000 1 50000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99...

output:

result:

ok 50000 numbers

Test #14:

score: 41

Accepted

time: 13ms

memory: 12916kb

input:

1000 5 50000
1 1332 1108 897 1146 921 1469 625 499 1957 1741 1419 1881 1501 661 1313 49 441 196 1997 477 1601 78 369 26 696 754 401 1486 1786 1921 1801 215 17 1577 496 1201 1169 1841 1239 501 673 1110 1894 1699 1307 887 779 1033 649 1807 801 497 1225 1181 1777 1493 1193 623 1951 617 541 1173 1061 13...

output:

result:

ok 50000 numbers

Test #15:

score: 41

Accepted

time: 11ms

memory: 10720kb

input:

1000 4 50000
1 1120 461 1267 1029 1465 262 1381 545 1545 1956 1165 846 551 1199 1751 430 1393 1131 911 1580 1163 1060 1817 1613 1937 37 101 407 369 1655 304 1933 1911 169 822 256 881 1209 685 521 1634 1011 1969 1787 828 1999 1961 1953 1601 1347 1841 914 739 1250 25 547 1201 1551 563 1857 1811 1071 1...

output:

result:

ok 50000 numbers

Test #16:

score: 41

Accepted

time: 11ms

memory: 13096kb

input:

1000 3 50000
1 1197 1833 521 1581 389 685 845 549 1257 421 700 817 1061 603 1591 331 887 400 265 647 440 1649 857 1401 1737 1021 1657 1301 371 586 1621 435 481 1601 1194 1756 1718 929 948 791 1296 1961 1423 383 1179 1955 181 961 1881 343 437 809 185 1064 1432 997 1121 782 205 1316 653 1685 276 1176 ...

output:

result:

ok 50000 numbers

Test #17:

score: 41

Accepted

time: 9ms

memory: 9860kb

input:

1000 2 50000
1 556 992 389 921 337 1489 1281 1891 1151 1701 369 105 649 1601 569 857 977 1624 901 1665 786 171 657 1461 1240 1977 1480 535 309 21 961 529 242 1345 1875 207 1376 1946 293 1721 1493 1239 595 1912 1809 17 940 631 601 591 164 1985 1706 497 1501 947 425 1917 1001 721 49 1065 1577 581 659 ...

output:

result:

ok 50000 numbers

Test #18:

score: 41

Accepted

time: 12ms

memory: 10240kb

input:

1000 6 50000
1 1626 851 389 337 1553 301 269 1342 1637 1409 515 641 123 1631 1191 885 365 1841 929 1073 1985 825 1685 165 696 1106 1761 1725 669 91 771 1857 1101 1789 1281 1731 1779 657 4 406 54 1574 163 1585 1754 1396 201 101 577 1531 1029 1569 1869 1829 1858 86 1274 141 766 759 265 1633 213 1045 1...

output:

result:

ok 50000 numbers

Test #19:

score: 41

Accepted

time: 9ms

memory: 10800kb

input:

1000 7 50000
1 272 1750 1981 609 1017 121 466 465 1826 83 1156 230 713 1945 1714 1463 17 1273 1643 749 471 1841 813 553 1299 1622 51 655 1886 561 1443 1431 1121 1441 815 1439 1281 617 1758 1873 206 1630 1947 1561 446 501 1639 1641 877 687 321 1111 1393 1401 1501 286 1101 552 383 1673 463 81 892 1217...

output:

result:

ok 50000 numbers

Test #20:

score: 41

Accepted

time: 14ms

memory: 12760kb

input:

1000 8 50000
1 795 17 367 205 386 1057 881 1080 1297 1341 1539 1645 1557 1629 393 1031 1249 256 515 1320 1865 356 721 29 1841 283 731 51 1357 1036 329 471 455 1820 694 1014 697 1062 1925 1877 1369 1549 860 1880 1561 1941 1681 1555 1625 1361 1752 960 1322 1071 1866 1651 1161 1217 866 1589 1601 1873 3...

output:

result:

ok 50000 numbers

Subtask #3:

score: 78

Accepted

Test #21:

score: 78

Accepted

time: 21ms

memory: 13480kb

input:

100000 2 100000
1 632676493 399040045 501692621 528540649 376451334 210054741 125474139 40350814 778610767 340820865 567129469 617741377 212005501 36999301 417426433 18396277 35644421 956862655 144510013 5237101 124404309 489651823 468235039 56349753 813225169 381479127 152309535 861942053 88598889 ...

output:

result:

ok 100000 numbers

Test #22:

score: 78

Accepted

time: 32ms

memory: 13480kb

input:

100000 4 100000
1 816109921 5379031 421836193 58780228 295972381 182915260 10714999 17319966 260860465 557843117 241427681 387587487 652511101 352167983 612446440 119040274 144694551 466346261 11775295 707109597 285612188 293199981 3195991 213780601 33412213 12293631 182348233 512072345 216607810 36...

output:

result:

ok 100000 numbers

Test #23:

score: 78

Accepted

time: 38ms

memory: 13068kb

input:

100000 6 100000
1 673957249 33447809 24729487 776397784 72207937 139605565 96952813 183943649 728020465 70357638 692460651 49469330 196598773 863319121 493597068 102980856 232040381 544264033 255134591 170049421 847743021 572454529 269405564 6356648 470771110 26910799 488341792 597217039 91212481 78...

output:

result:

ok 100000 numbers

Test #24:

score: 78

Accepted

time: 38ms

memory: 14272kb

input:

100000 9 100000
1 71681491 215298229 416333533 185484509 391339378 12948757 175013785 108741853 413221585 28261901 36747561 380298281 696633651 10634369 129973546 550830595 297197302 58131926 127534701 157632973 272182102 163310232 833772413 536563969 326718433 78927674 428600305 80437520 211133361 ...

output:

result:

ok 100000 numbers

Test #25:

score: 78

Accepted

time: 46ms

memory: 15476kb

input:

100000 10 100000
1 42480355 653291407 175837501 312804785 304255225 556324777 216726079 203849367 40066566 377484517 496768567 281317570 442649633 9017689 478502074 199356361 554438334 512839501 114831501 408065264 10719226 116124145 365239029 77788817 306013125 198809183 76995865 262305142 11746729...

output:

result:

ok 100000 numbers

Test #26:

score: 78

Accepted

time: 54ms

memory: 15472kb

input:

100000 12 100000
1 685641961 628450396 64467250 523085970 341130223 473491657 312740771 685461151 14800730 514551286 328687486 68484377 26693731 163988773 351612033 164300291 34418721 238734861 360706641 251288800 391022854 108147746 37318306 206910511 420236776 308161827 632453361 8590648 238043551...

output:

result:

ok 100000 numbers

Test #27:

score: 78

Accepted

time: 78ms

memory: 11048kb

input:

100000 10000 100000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 9...

output:

result:

ok 100000 numbers

Test #28:

score: 78

Accepted

time: 172ms

memory: 13484kb

input:

100000 20000 100000
1 153577 992137 53759 390161 740706 811489 904099 583101 240179 834981 582673 85410 884201 131747 677141 638091 200715 645022 381116 225121 407363 620961 89907 668592 949017 482705 279351 33033 168664 232376 403701 724033 125113 361293 715273 69828 312401 306559 869583 658101 799...

output:

result:

ok 100000 numbers

Test #29:

score: 78

Accepted

time: 77ms

memory: 15524kb

input:

100000 100 100000
1 948151 191729 559393 436735 404641 241504 659957 238832 678309 69041 345865 342621 522441 413213 349301 803641 550711 214939 804846 930705 503739 64521 994286 237956 655621 481951 934691 85721 462290 108021 40765 408624 830676 979187 772149 679329 586001 198609 947451 426191 1719...

output:

result:

ok 100000 numbers

Test #30:

score: 78

Accepted

time: 40ms

memory: 13292kb

input:

100000 10000 100000
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 ...

output:

result:

ok 100000 numbers

Test #31:

score: 78

Accepted

time: 41ms

memory: 13320kb

input:

100000 100 100000
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...

output:

result:

ok 100000 numbers

Test #32:

score: 78

Accepted

time: 42ms

memory: 11020kb

input:

100000 800 100000
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...

output:

result:

ok 100000 numbers

Test #33:

score: 78

Accepted

time: 37ms

memory: 13388kb

input:

100000 1000 100000
999 998 997 996 995 994 993 992 991 990 989 988 987 986 985 984 983 982 981 980 979 978 977 976 975 974 973 972 971 970 969 968 967 966 965 964 963 962 961 960 959 958 957 956 955 954 953 952 951 950 949 948 947 946 945 944 943 942 941 940 939 938 937 936 935 934 933 932 931 930 9...

output:

result:

ok 100000 numbers

Test #34:

score: 78

Accepted

time: 41ms

memory: 13344kb

input:

100000 10000 100000
9999 9998 9997 9996 9995 9994 9993 9992 9991 9990 9989 9988 9987 9986 9985 9984 9983 9982 9981 9980 9979 9978 9977 9976 9975 9974 9973 9972 9971 9970 9969 9968 9967 9966 9965 9964 9963 9962 9961 9960 9959 9958 9957 9956 9955 9954 9953 9952 9951 9950 9949 9948 9947 9946 9945 9944 ...

output:

result:

ok 100000 numbers

Test #35:

score: 78

Accepted

time: 39ms

memory: 12728kb

input:

100000 100000 100000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 ...

output:

result:

ok 100000 numbers

Test #36:

score: 78

Accepted

time: 37ms

memory: 13488kb

input:

100000 100000 100000
100000 99999 99998 99997 99996 99995 99994 99993 99992 99991 99990 99989 99988 99987 99986 99985 99984 99983 99982 99981 99980 99979 99978 99977 99976 99975 99974 99973 99972 99971 99970 99969 99968 99967 99966 99965 99964 99963 99962 99961 99960 99959 99958 99957 99956 99955 99...

output:

result:

ok 100000 numbers

Test #37:

score: 78

Accepted

time: 100ms

memory: 13388kb

input:

100000 1000 100000
800 90 810 563 216 241 617 96 779 119 76 410 931 847 751 380 547 219 66 379 24 999 531 862 542 26 704 317 748 511 145 80 391 395 63 799 869 660 112 817 860 812 390 222 996 737 433 758 783 883 745 591 498 864 81 527 834 385 507 451 366 972 146 122 502 991 132 875 315 261 549 463 62...

output:

result:

ok 100000 numbers

Test #38:

score: 78

Accepted

time: 43ms

memory: 13116kb

input:

100000 2000 100000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97...

output:

result:

ok 100000 numbers

Test #39:

score: 78

Accepted

time: 38ms

memory: 11176kb

input:

100000 200 100000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 ...

output:

result:

ok 100000 numbers

Test #40:

score: 78

Accepted

time: 35ms

memory: 13008kb

input:

100000 20000 100000
20000 19999 19998 19997 19996 19995 19994 19993 19992 19991 19990 19989 19988 19987 19986 19985 19984 19983 19982 19981 19980 19979 19978 19977 19976 19975 19974 19973 19972 19971 19970 19969 19968 19967 19966 19965 19964 19963 19962 19961 19960 19959 19958 19957 19956 19955 1995...

output:

result:

ok 100000 numbers

Test #41:

score: 78

Accepted

time: 43ms

memory: 12748kb

input:

100000 10000 100000
10000 9999 9998 9997 9996 9995 9994 9993 9992 9991 9990 9989 9988 9987 9986 9985 9984 9983 9982 9981 9980 9979 9978 9977 9976 9975 9974 9973 9972 9971 9970 9969 9968 9967 9966 9965 9964 9963 9962 9961 9960 9959 9958 9957 9956 9955 9954 9953 9952 9951 9950 9949 9948 9947 9946 9945...

output:

result:

ok 100000 numbers

Test #42:

score: 78

Accepted

time: 42ms

memory: 11396kb

input:

100000 5000 100000
5000 4999 4998 4997 4996 4995 4994 4993 4992 4991 4990 4989 4988 4987 4986 4985 4984 4983 4982 4981 4980 4979 4978 4977 4976 4975 4974 4973 4972 4971 4970 4969 4968 4967 4966 4965 4964 4963 4962 4961 4960 4959 4958 4957 4956 4955 4954 4953 4952 4951 4950 4949 4948 4947 4946 4945 4...

output:

result:

ok 100000 numbers

Test #43:

score: 78

Accepted

time: 37ms

memory: 13492kb

input:

100000 50 100000
50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 0 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 0 5...

output:

result:

ok 100000 numbers

Test #44:

score: 78

Accepted

time: 41ms

memory: 12892kb

input:

100000 120 100000
120 119 118 117 116 115 114 113 112 111 110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 ...

output:

result:

ok 100000 numbers

Test #45:

score: 78

Accepted

time: 30ms

memory: 11080kb

input:

100000 120 100000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 ...

output:

result:

ok 100000 numbers

Test #46:

score: 78

Accepted

time: 46ms

memory: 11100kb

input:

100000 5000 100000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97...

output:

result:

ok 100000 numbers

Test #47:

score: 78

Accepted

time: 45ms

memory: 12728kb

input:

100000 13000 100000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 9...

output:

result:

ok 100000 numbers

Test #48:

score: 78

Accepted

time: 43ms

memory: 13052kb

input:

100000 8000 100000
8000 7999 7998 7997 7996 7995 7994 7993 7992 7991 7990 7989 7988 7987 7986 7985 7984 7983 7982 7981 7980 7979 7978 7977 7976 7975 7974 7973 7972 7971 7970 7969 7968 7967 7966 7965 7964 7963 7962 7961 7960 7959 7958 7957 7956 7955 7954 7953 7952 7951 7950 7949 7948 7947 7946 7945 7...

output:

result:

ok 100000 numbers

Test #49:

score: 78

Accepted

time: 42ms

memory: 13280kb

input:

100000 800 100000
800 799 798 797 796 795 794 793 792 791 790 789 788 787 786 785 784 783 782 781 780 779 778 777 776 775 774 773 772 771 770 769 768 767 766 765 764 763 762 761 760 759 758 757 756 755 754 753 752 751 750 749 748 747 746 745 744 743 742 741 740 739 738 737 736 735 734 733 732 731 73...

output:

result:

ok 100000 numbers

Test #50:

score: 78

Accepted

time: 45ms

memory: 13212kb

input:

100000 40000 100000
40000 39999 39998 39997 39996 39995 39994 39993 39992 39991 39990 39989 39988 39987 39986 39985 39984 39983 39982 39981 39980 39979 39978 39977 39976 39975 39974 39973 39972 39971 39970 39969 39968 39967 39966 39965 39964 39963 39962 39961 39960 39959 39958 39957 39956 39955 3995...

output:

result:

ok 100000 numbers