QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #358461 | #3503. Misspelling | Rikku_eq | 100 ✓ | 894ms | 873044kb | C++14 | 3.9kb | 2024-03-19 20:00:30 | 2024-03-19 20:00:31 |
Judging History
answer
#include <bits/stdc++.h>
#define sum(u) (tr[u].cnt[0]+tr[u].cnt[1])
#define ls(u) tr[u].ls
#define rs(u) tr[u].rs
#define N 500005
#define M 30
#define mod 1000000007
using namespace std;
typedef long long ll;
int n, m, rt, tot, rec[2];
struct Seg { int ls, rs, cnt[2]; } tr[N*2];
struct Pnt { int u, l, r; };
vector <Pnt> vec;
struct Lim { int l, r, tg; } p[N];
vector <int> lim[N];
ll f[N][M], g[N][M], pr[2][N][M], sumg[N][M], sump[2][N][M];
ll ans;
void buildST (int &u, int l, int r)
{
if (!u) { u=++tot; }
if (l==r) { return; }
int md=(l+r)/2;
buildST(ls(u), l, md);
buildST(rs(u), md+1, r);
}
void add (int u, int l, int r, int id, int tg, int num)
{
if (l==r) { tr[u].cnt[tg]+=num; return; }
int md=(l+r)/2;
if (id<=md) { add(ls(u), l, md, id, tg, num); }
else { add(rs(u), md+1, r, id, tg, num); }
tr[u].cnt[tg]=tr[ls(u)].cnt[tg]+tr[rs(u)].cnt[tg];
}
void dfs (int u, int l, int r, int ql, int qr)
{
if (l>qr || r<ql) { return; }
if (ql<=l && r<=qr) { vec.push_back((Pnt){ u, l, r }); return; }
int md=(l+r)/2;
dfs(ls(u), l, md, ql, qr);
dfs(rs(u), md+1, r, ql, qr);
}
int qry0 (int u, int l, int r)
{
if (l==r) { rec[0]=(tr[u].cnt[0]!=0); rec[1]=(tr[u].cnt[1]!=0); return l; }
int md=(l+r)/2;
if (sum(rs(u))) { return qry0(rs(u), md+1, r); }
else { return qry0(ls(u), l, md); }
}
int find0 (int ql, int qr)
{
vec.clear();
dfs(rt, 1, n, ql, qr);
for (int i=vec.size()-1; i>=0; i--) {
int u=vec[i].u, l=vec[i].l, r=vec[i].r;
if (sum(u)!=0) { return qry0(u, l, r); }
}
return 0;
}
int qry1 (int u, int l, int r, int tg)
{
if (l==r) { return l; }
int md=(l+r)/2;
if (tr[rs(u)].cnt[tg]) { return qry1(rs(u), md+1, r, tg); }
else { return qry1(ls(u), l, md, tg); }
}
int find1 (int ql, int qr, int tg)
{
vec.clear();
dfs(rt, 1, n, ql, qr);
for (int i=vec.size()-1; i>=0; i--) {
int u=vec[i].u, l=vec[i].l, r=vec[i].r;
if (tr[u].cnt[tg^1]) { return qry1(u, l, r, tg^1); }
}
return 0;
}
ll cal (int i)
{
for (int j=2; j<=26; j++) { pr[1][i][j]=(pr[1][i][j-1]+f[i][j-1])%mod; }
ll tmp=(pr[1][i][26]+f[i][26])%mod;
for (int j=25; j>=1; j--) { pr[0][i][j]=(pr[0][i][j+1]+f[i][j+1])%mod; }
for (int j=1; j<=26; j++) { g[i][j]=(tmp-f[i][j])%mod; }
for (int j=1; j<=26; j++) { sump[0][i][j]=((i ? sump[0][i-1][j] : 0)+pr[0][i][j])%mod; }
for (int j=1; j<=26; j++) { sump[1][i][j]=((i ? sump[1][i-1][j] : 0)+pr[1][i][j])%mod; }
for (int j=1; j<=26; j++) { sumg[i][j]=((i ? sumg[i-1][j] : 0)+g[i][j])%mod; }
return tmp;
}
int main ()
{
// freopen("0test.in", "r", stdin);
// freopen("0test.out", "w", stdout);
scanf("%d %d", &n, &m);
buildST(rt, 1, n);
for (int i=1; i<=m; i++) {
int u, v; scanf("%d %d", &u, &v);
if (u<v) { p[i]=(Lim){ u, v, 0 }; }
else { p[i]=(Lim){ v, u, 1 }; }
lim[p[i].r].push_back(i);
add(rt, 1, n, p[i].l, p[i].tg, 1);
}
for (int i=1; i<=26; i++) { f[0][i]=1; }
ans+=cal(0); ans%=mod;
for (int i=1; i<=n; i++) {
for (int j=0; j<(int)lim[i].size(); j++) {
int id=lim[i][j];
add(rt, 1, n, p[id].l, p[id].tg, -1);
}
int pos0=find0(1, i);
bool cur=(rec[0] ? 0 : 1);
int pos1=find1(1, i, cur);
for (int j=1; j<=26; j++) {
if (!pos0) { f[i][j]+=sumg[i-1][j]; f[i][j]%=mod; continue; }
else { f[i][j]+=sumg[i-1][j]-sumg[pos0-1][j]; f[i][j]%=mod; }
if (rec[0] && rec[1]) { continue; }
if (!pos1) { f[i][j]+=sump[cur][pos0-1][j]; f[i][j]%=mod; }
else { f[i][j]+=sump[cur][pos0-1][j]-sump[cur][pos1-1][j]; f[i][j]%=mod; }
}
if (i<n) { ans+=cal(i); ans%=mod; }
}
ans=(ans+mod)%mod;
printf("%lld\n", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 8
Accepted
Test #1:
score: 8
Accepted
time: 0ms
memory: 15668kb
input:
10 9 3 4 4 2 6 2 7 6 7 8 8 5 5 10 10 9 9 1
output:
344750796
result:
ok single line: '344750796'
Test #2:
score: 0
Accepted
time: 0ms
memory: 15656kb
input:
10 9 3 7 7 4 4 9 6 9 8 6 8 5 5 10 10 1 1 2
output:
1506401
result:
ok single line: '1506401'
Test #3:
score: 0
Accepted
time: 3ms
memory: 15656kb
input:
10 10 2 8 1 5 9 3 3 9 2 9 7 10 7 3 7 8 4 1 5 6
output:
351
result:
ok single line: '351'
Test #4:
score: 0
Accepted
time: 3ms
memory: 15556kb
input:
10 90 5 2 4 2 3 6 1 10 7 1 10 9 1 7 2 3 10 3 7 6 8 5 5 3 9 1 6 3 8 1 3 5 6 2 5 1 2 10 2 8 8 7 3 4 6 7 3 10 4 8 7 3 1 8 2 9 9 2 3 2 9 6 2 1 1 9 1 5 8 3 4 5 8 10 4 3 9 8 2 6 10 2 3 7 4 9 8 9 7 5 5 7 10 5 9 4 1 4 10 7 9 10 9 7 6 10 7 9 2 4 5 9 2 7 1 3 3 9 6 9 2 5 6 1 9 3 7 10 5 10 8 4 8 6 3 8 8 2 3 1 5...
output:
26
result:
ok single line: '26'
Test #5:
score: 0
Accepted
time: 3ms
memory: 18084kb
input:
10 1 4 2
output:
960864167
result:
ok single line: '960864167'
Test #6:
score: 0
Accepted
time: 0ms
memory: 17564kb
input:
10 5 6 3 9 4 4 10 9 5 9 2
output:
1682226
result:
ok single line: '1682226'
Test #7:
score: 0
Accepted
time: 0ms
memory: 17580kb
input:
2 1 1 2
output:
351
result:
ok single line: '351'
Test #8:
score: 0
Accepted
time: 0ms
memory: 17720kb
input:
2 2 2 1 1 2
output:
26
result:
ok single line: '26'
Subtask #2:
score: 20
Accepted
Dependency #1:
100%
Accepted
Test #9:
score: 20
Accepted
time: 3ms
memory: 17916kb
input:
200 100 1 30 10 179 12 115 15 117 17 161 19 84 22 146 23 46 27 188 29 108 37 69 39 48 41 55 44 158 47 63 50 71 51 91 54 107 55 148 56 61 58 71 61 186 62 92 63 168 65 158 66 145 67 90 71 95 73 125 76 101 79 196 80 104 82 153 84 98 85 111 86 143 88 107 90 177 91 111 92 99 93 177 94 123 95 113 96 128 9...
output:
141223392
result:
ok single line: '141223392'
Test #10:
score: 0
Accepted
time: 0ms
memory: 17916kb
input:
200 100 2 182 3 188 4 67 5 177 7 189 10 123 11 33 13 155 15 58 20 33 22 158 23 47 25 143 26 153 29 158 32 98 35 178 38 64 39 63 41 186 43 134 45 158 46 196 47 119 52 130 55 89 56 109 59 111 60 161 62 161 66 84 69 142 76 105 78 147 79 200 81 162 85 105 86 132 87 177 89 105 90 102 91 161 92 104 93 194...
output:
324576383
result:
ok single line: '324576383'
Test #11:
score: 0
Accepted
time: 3ms
memory: 18024kb
input:
200 200 1 4 2 98 5 145 6 89 10 40 12 154 14 142 15 115 17 153 18 199 19 23 20 137 21 152 23 155 25 145 27 56 28 48 29 86 30 66 31 127 32 184 35 137 36 177 40 115 45 192 46 196 47 71 49 174 50 195 52 185 53 57 54 123 56 161 61 130 62 79 63 103 65 171 67 120 68 186 74 84 75 118 77 157 78 197 80 139 83...
output:
169274437
result:
ok single line: '169274437'
Test #12:
score: 0
Accepted
time: 3ms
memory: 17868kb
input:
200 200 1 152 3 147 4 21 7 146 10 174 12 89 13 154 17 165 18 96 19 71 20 55 23 100 24 162 25 127 28 99 29 166 32 43 34 55 36 159 37 167 38 113 40 116 42 47 43 146 44 97 46 102 49 180 50 197 51 119 52 115 55 124 56 102 57 73 59 187 61 157 62 167 63 143 66 136 67 160 71 195 72 147 74 169 78 163 81 190...
output:
117351
result:
ok single line: '117351'
Test #13:
score: 0
Accepted
time: 0ms
memory: 17936kb
input:
200 199 5 6 6 10 10 11 11 12 12 13 13 16 16 19 19 23 23 24 24 28 28 30 30 32 32 35 35 38 38 41 41 47 47 51 51 54 54 55 55 59 59 60 60 61 61 62 62 64 64 65 65 66 66 67 67 68 68 75 75 77 77 79 79 80 80 82 82 86 86 87 87 89 89 90 90 91 91 92 92 93 93 95 95 97 97 100 100 102 102 103 103 108 108 109 109 ...
output:
585503549
result:
ok single line: '585503549'
Test #14:
score: 0
Accepted
time: 0ms
memory: 19356kb
input:
200 199 2 3 3 7 7 8 8 9 9 12 12 13 13 16 16 18 18 20 20 21 21 22 22 75 75 25 25 29 29 31 31 32 32 33 33 35 35 39 39 40 40 41 41 43 43 45 45 46 46 47 47 49 49 50 50 52 52 53 53 55 55 59 59 60 60 63 63 65 65 67 67 69 69 70 70 73 73 74 74 76 76 78 78 82 82 83 83 84 84 91 91 94 94 98 98 100 100 101 101 ...
output:
240485564
result:
ok single line: '240485564'
Test #15:
score: 0
Accepted
time: 3ms
memory: 19044kb
input:
200 200 141 177 64 183 31 25 196 113 105 6 163 71 38 149 198 64 140 55 113 55 103 60 50 123 145 88 123 54 95 1 65 102 187 74 56 46 169 119 11 40 192 44 42 129 80 8 145 161 182 179 162 62 183 172 63 134 43 3 121 53 71 148 154 153 122 48 77 21 195 54 46 78 111 17 166 200 186 73 66 110 46 57 174 142 47...
output:
351
result:
ok single line: '351'
Test #16:
score: 0
Accepted
time: 0ms
memory: 18360kb
input:
200 10000 70 186 2 197 148 118 47 79 29 27 65 83 96 143 57 173 55 193 123 62 157 57 17 137 4 110 143 124 84 111 83 97 91 110 147 25 44 72 9 47 28 136 116 107 109 195 2 49 167 129 169 125 153 59 68 91 5 43 167 59 193 199 38 75 109 21 173 93 43 108 52 108 140 118 5 123 150 41 48 145 161 41 69 177 53 1...
output:
26
result:
ok single line: '26'
Test #17:
score: 0
Accepted
time: 0ms
memory: 19184kb
input:
200 1 9 162
output:
424803593
result:
ok single line: '424803593'
Test #18:
score: 0
Accepted
time: 0ms
memory: 18660kb
input:
200 100 139 171 104 173 71 168 139 166 159 182 176 2 71 103 59 131 25 70 12 23 49 127 100 108 171 128 187 59 29 190 16 32 131 63 146 186 188 56 51 117 98 169 38 25 46 43 189 103 155 83 151 7 28 114 125 158 158 190 104 29 142 173 198 106 28 8 54 39 35 121 175 17 4 47 183 108 157 124 4 178 12 2 103 22...
output:
11515858
result:
ok single line: '11515858'
Subtask #3:
score: 29
Accepted
Test #19:
score: 29
Accepted
time: 489ms
memory: 873044kb
input:
500000 499999 5 6 6 7 7 11 11 15 15 18 18 20 20 21 21 22 22 23 23 27 27 28 28 29 29 30 30 32 32 33 33 35 35 36 36 37 37 43 43 44 44 46 46 47 47 48 48 49 49 51 51 52 52 53 53 54 54 58 58 61 61 63 63 64 64 65 65 66 66 69 69 70 70 76 76 77 77 78 78 80 80 81 81 83 83 87 87 88 88 90 90 92 92 93 93 96 96 ...
output:
19934265
result:
ok single line: '19934265'
Test #20:
score: 0
Accepted
time: 507ms
memory: 873044kb
input:
500000 499999 2 4 4 5 5 7 7 8 8 9 9 10 10 13 13 14 14 15 15 16 16 19 19 27 27 29 29 30 30 35 35 37 37 39 39 42 42 44 44 45 45 48 48 51 51 54 54 56 56 57 57 58 58 60 60 62 62 63 63 64 64 65 65 66 66 70 70 71 71 74 74 75 75 76 76 77 77 80 80 82 82 85 85 86 86 93 93 94 94 96 96 98 98 100 100 101 101 10...
output:
564937410
result:
ok single line: '564937410'
Test #21:
score: 0
Accepted
time: 592ms
memory: 873044kb
input:
500000 499999 1 2 2 4 4 5 5 6 6 8 8 9 9 11 11 12 12 14 14 18 18 19 19 20 20 21 21 24 24 25 25 27 27 29 29 30 30 31 31 33 33 37 37 38 38 39 39 41 41 42 42 46 46 49 49 50 50 52 52 55 55 57 57 59 59 60 60 61 61 62 62 63 63 66 66 69 69 70 70 71 71 75 75 76 76 80 80 84 84 87 87 91 91 93 93 94 94 96 96 10...
output:
502112931
result:
ok single line: '502112931'
Test #22:
score: 0
Accepted
time: 575ms
memory: 872896kb
input:
500000 499999 4 7 7 8 8 9 9 10 10 11 11 12 12 14 14 15 15 16 16 17 17 18 18 19 19 21 21 22 22 23 23 24 24 27 27 30 30 31 31 32 32 33 33 35 35 36 36 39 39 40 40 44 44 45 45 46 46 48 48 49 49 50 50 51 51 52 52 53 53 54 54 56 56 57 57 58 58 59 59 60 60 61 61 62 62 64 64 65 65 66 66 67 67 68 68 69 69 75...
output:
624913928
result:
ok single line: '624913928'
Test #23:
score: 0
Accepted
time: 543ms
memory: 872892kb
input:
500000 499999 1 3 3 4 4 5 5 6 6 8 8 9 9 10 10 12 12 14 14 15 15 19 19 21 21 25 25 28 28 29 29 30 30 31 31 32 32 33 33 34 34 36 36 37 37 42 42 45 45 46 46 48 48 49 49 50 50 54 54 56 56 57 57 58 58 61 61 67 67 68 68 70 70 71 71 73 73 74 74 75 75 76 76 78 78 79 79 80 80 82 82 84 84 85 85 87 87 93 93 96...
output:
855869095
result:
ok single line: '855869095'
Test #24:
score: 0
Accepted
time: 24ms
memory: 51380kb
input:
20000 19999 1 2 2 4 4 5 5 7 7 9 9 13 13 14 14 15 15 16 16 17 17 20 20 21 21 22 22 25 25 27 27 28 28 29 29 33 33 34 34 39 39 40 40 42 42 44 44 46 46 47 47 48 48 49 49 50 50 51 51 52 52 55 55 60 60 62 62 68 68 69 69 70 70 71 71 72 72 74 74 75 75 77 77 83 83 87 87 88 88 90 90 91 91 96 96 98 98 100 100 ...
output:
898746113
result:
ok single line: '898746113'
Test #25:
score: 0
Accepted
time: 3ms
memory: 19032kb
input:
200 199 2 3 3 7 7 9 9 11 11 18 18 21 21 22 22 23 23 24 24 25 25 26 26 29 29 30 30 33 33 35 35 36 36 38 38 39 39 46 46 47 47 48 48 50 50 53 53 56 56 58 58 60 60 61 61 64 64 66 66 68 68 70 70 73 73 76 76 79 79 80 80 81 81 84 84 85 85 89 89 90 90 92 92 94 94 96 96 97 97 98 98 115 115 102 102 103 103 10...
output:
27130982
result:
ok single line: '27130982'
Test #26:
score: 0
Accepted
time: 0ms
memory: 18948kb
input:
10 9 6 3 3 10 10 7 7 2 2 5 5 8 8 1 1 4 4 9
output:
26
result:
ok single line: '26'
Test #27:
score: 0
Accepted
time: 852ms
memory: 867848kb
input:
500000 499999 187564 40668 40668 349455 349455 236165 236165 234125 234125 19156 19156 200503 200503 27193 27193 229119 229119 106828 106828 441617 441617 199617 199617 267010 267010 351798 351798 4127 4127 462764 462764 499225 499225 40019 40019 40149 40149 492337 492337 129118 129118 403985 403985...
output:
26
result:
ok single line: '26'
Subtask #4:
score: 32
Accepted
Dependency #2:
100%
Accepted
Test #28:
score: 32
Accepted
time: 15ms
memory: 52224kb
input:
20000 10000 1 12498 2 4890 6 9894 7 15113 8 12798 9 16884 10 6938 12 15913 16 4036 17 15990 21 17803 23 9296 26 15532 27 11655 28 4917 30 10019 34 8147 38 7054 39 6590 40 16560 42 1907 46 14882 49 5312 50 948 51 15792 54 10799 56 11267 57 3435 58 4153 60 12999 61 2732 63 9843 65 10202 66 3849 67 142...
output:
369758197
result:
ok single line: '369758197'
Test #29:
score: 0
Accepted
time: 14ms
memory: 50864kb
input:
20000 10000 1 17010 2 18781 4 11109 8 2058 13 10906 15 9073 16 14488 17 4884 18 15611 19 13307 21 7806 22 17478 24 2977 25 9350 26 6404 28 9309 30 7448 32 1314 34 13282 36 1373 39 18651 40 16157 45 10951 46 5477 48 10260 53 4304 55 7122 56 7494 59 3195 60 10750 61 13704 64 5115 65 6449 66 5063 69 19...
output:
56370275
result:
ok single line: '56370275'
Test #30:
score: 0
Accepted
time: 28ms
memory: 51112kb
input:
20000 20000 3 3236 6 13425 8 3371 10 9439 11 11507 12 4731 16 12434 19 17949 20 11515 23 8855 24 15088 25 3794 28 11409 30 3204 31 6800 32 6352 35 15984 36 2910 38 17511 39 17219 44 2242 46 18082 50 19446 51 12846 53 2963 54 10533 55 9740 56 12873 57 2075 59 2697 60 9177 61 3427 63 11293 64 11314 65...
output:
414297581
result:
ok single line: '414297581'
Test #31:
score: 0
Accepted
time: 23ms
memory: 52244kb
input:
20000 20000 1 19622 2 18715 3 15480 10 2083 16 13213 20 6930 22 19258 27 16603 29 14229 32 5176 33 13224 36 15473 43 7354 50 9775 56 15428 57 18981 58 1735 60 18441 61 8311 70 555 71 5180 76 10361 78 17745 80 10592 83 13378 84 18317 86 7652 88 1522 89 5707 90 928 93 19826 96 15979 99 6498 101 8911 1...
output:
273114958
result:
ok single line: '273114958'
Test #32:
score: 0
Accepted
time: 201ms
memory: 60720kb
input:
20000 500000 2 18077 6 17981 9 778 10 19349 12 9884 13 14104 14 15761 15 6769 16 1301 17 8697 25 7729 27 16532 28 4220 30 1526 33 15877 36 10598 37 6815 38 18213 41 16213 43 976 44 11718 45 2164 47 3247 49 11421 53 9218 56 5247 57 17044 59 16386 60 15592 61 14989 62 12087 63 17163 65 6765 66 13443 6...
output:
586816696
result:
ok single line: '586816696'
Test #33:
score: 0
Accepted
time: 12ms
memory: 52792kb
input:
20000 19999 1 6 6 9 9 11 11 12 12 13 13 14 14 16 16 17 17 18 18 19 19 24 24 26 26 28 28 31 31 32 32 33 33 37 37 38 38 39 39 40 40 42 42 44 44 45 45 46 46 47 47 48 48 50 50 51 51 55 55 56 56 58 58 62 62 66 66 67 67 70 70 71 71 73 73 74 74 78 78 80 80 83 83 84 84 88 88 93 93 94 94 96 96 98 98 99 99 10...
output:
172699320
result:
ok single line: '172699320'
Test #34:
score: 0
Accepted
time: 24ms
memory: 51256kb
input:
20000 19999 3 4 4 5 5 7 7 8 8 9 9 13 13 15 15 16 16 17 17 18 18 21 21 22 22 24 24 26 26 27 27 28 28 32 32 33 33 35 35 36 36 40 40 44 44 45 45 46 46 47 47 48 48 49 49 51 51 54 54 56 56 57 57 59 59 63 63 66 66 67 67 68 68 75 75 76 76 77 77 78 78 79 79 80 80 82 82 85 85 86 86 88 88 89 89 91 91 92 92 93...
output:
138494046
result:
ok single line: '138494046'
Test #35:
score: 0
Accepted
time: 28ms
memory: 50988kb
input:
20000 20000 17225 18820 19023 4426 1549 5808 8031 258 8875 18803 821 15565 3370 7643 12898 11201 12694 13996 10473 19436 8055 11900 4206 19808 17936 19501 9638 6083 13177 9355 19546 12713 16338 3368 2931 3650 8848 19718 1716 428 18304 1960 18547 3729 2579 8093 19095 3557 11576 3075 2884 13380 7967 8...
output:
240325860
result:
ok single line: '240325860'
Test #36:
score: 0
Accepted
time: 216ms
memory: 60900kb
input:
20000 500000 14607 6292 18938 4062 9080 13191 11270 10022 18829 2386 19683 12913 883 3681 622 4689 17839 15959 17 15584 7386 5772 13206 4449 13094 3791 1998 15201 13078 16764 5381 10843 19913 5236 12052 3890 8443 7865 1797 737 1814 11333 18476 12615 8215 1859 445 12729 14480 3769 7245 18846 7994 195...
output:
26
result:
ok single line: '26'
Test #37:
score: 0
Accepted
time: 21ms
memory: 51376kb
input:
20000 1 10950 9228
output:
626578574
result:
ok single line: '626578574'
Test #38:
score: 0
Accepted
time: 7ms
memory: 51056kb
input:
20000 15000 5211 15066 11521 10959 6434 8566 788 13707 16754 17439 15500 13844 7305 2240 9897 10966 9699 4054 331 4312 11813 9992 19145 13060 464 17245 8606 10165 891 7896 6986 18185 8726 12554 1488 9950 3494 13115 11859 15139 18070 7160 4788 4664 16387 7584 2268 4058 2000 6547 10556 2836 13570 1079...
output:
158017938
result:
ok single line: '158017938'
Test #39:
score: 0
Accepted
time: 23ms
memory: 51964kb
input:
20000 10000 16180 19337 16936 5104 562 11284 17705 2614 14217 14640 18771 7902 4629 14350 10781 19982 5794 16841 5663 8598 12292 4969 16458 15032 9835 16885 13994 16992 13306 15767 12486 15957 10934 2240 5047 2938 4223 2214 13869 18052 6488 9132 5479 13001 7895 3914 14666 13050 294 13080 16420 10605...
output:
818833189
result:
ok single line: '818833189'
Test #40:
score: 0
Accepted
time: 20ms
memory: 50688kb
input:
20000 5000 11206 4505 5181 2065 16968 6945 6410 3848 14832 17160 913 7819 2471 8196 16403 4748 14964 7838 12746 18457 9303 16028 17629 7368 13584 13222 13111 6034 5125 19229 3788 5708 5268 3528 8008 14222 8876 13738 8557 8000 17564 19101 1389 14127 1775 13435 15327 1444 11886 9846 6208 8528 4617 113...
output:
15905073
result:
ok single line: '15905073'
Subtask #5:
score: 11
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Test #41:
score: 11
Accepted
time: 612ms
memory: 860720kb
input:
500000 250000 3 134857 5 472819 6 33637 7 264857 8 30671 13 470140 17 112998 19 196477 22 262970 23 72130 25 165886 26 398558 29 243310 30 489865 31 409197 38 338668 40 337398 41 693 43 126674 44 491366 45 351893 46 240057 51 33944 53 151936 54 312222 55 466767 56 342191 57 262777 58 126907 60 29419...
output:
924317962
result:
ok single line: '924317962'
Test #42:
score: 0
Accepted
time: 572ms
memory: 860716kb
input:
500000 250000 1 492082 3 73408 4 287609 5 265086 6 393555 7 74906 8 279580 9 190523 11 439175 18 114182 21 70409 23 301322 25 122141 27 88837 28 439584 29 467669 33 12956 34 165894 36 196044 38 278671 39 129140 41 330025 43 130223 44 440665 45 23460 46 43510 48 164130 50 299052 54 387050 57 50419 58...
output:
363040296
result:
ok single line: '363040296'
Test #43:
score: 0
Accepted
time: 843ms
memory: 866832kb
input:
500000 500000 2 315445 3 85299 4 48395 5 251350 9 362282 10 184411 11 346211 13 305230 14 303826 15 167351 17 228398 20 405993 21 355002 23 52526 24 429492 25 52829 26 110081 32 492931 33 111128 36 49253 37 430927 39 313524 40 418747 41 11321 42 419146 44 489190 46 422344 47 436789 48 180684 50 3092...
output:
747201642
result:
ok single line: '747201642'
Test #44:
score: 0
Accepted
time: 813ms
memory: 866776kb
input:
500000 500000 2 234448 3 112500 5 492912 7 166900 11 247336 15 410256 16 444662 18 175545 19 79998 20 312204 24 30788 25 416593 29 293143 30 421895 35 438179 37 315741 38 142057 40 177037 41 72274 42 498181 43 313680 44 185603 46 11068 49 205240 51 347182 52 75257 53 236030 54 363418 57 195864 58 27...
output:
16239419
result:
ok single line: '16239419'
Test #45:
score: 0
Accepted
time: 492ms
memory: 873028kb
input:
500000 499999 1 3 3 4 4 8 8 10 10 13 13 15 15 17 17 19 19 21 21 23 23 26 26 28 28 29 29 32 32 38 38 39 39 40 40 45 45 50 50 54 54 58 58 60 60 62 62 64 64 67 67 70 70 71 71 73 73 74 74 75 75 76 76 78 78 82 82 88 88 89 89 90 90 91 91 94 94 95 95 97 97 98 98 99 99 100 100 101 101 102 102 104 104 105 10...
output:
598934924
result:
ok single line: '598934924'
Test #46:
score: 0
Accepted
time: 548ms
memory: 873044kb
input:
500000 499999 2 7 7 9 9 11 11 13 13 15 15 18 18 19 19 22 22 25 25 26 26 30 30 32 32 35 35 37 37 39 39 43 43 44 44 45 45 52 52 58 58 62 62 64 64 65 65 67 67 69 69 74 74 77 77 79 79 80 80 81 81 85 85 86 86 87 87 89 89 90 90 91 91 98 98 103 103 104 104 114 114 116 116 118 118 120 120 121 121 124 124 12...
output:
271829008
result:
ok single line: '271829008'
Test #47:
score: 0
Accepted
time: 555ms
memory: 873044kb
input:
500000 499999 2 3 3 4 4 6 6 11 11 12 12 13 13 15 15 20 20 21 21 23 23 27 27 29 29 30 30 39 39 42 42 43 43 44 44 45 45 46 46 47 47 53 53 54 54 55 55 58 58 59 59 60 60 62 62 64 64 66 66 67 67 68 68 69 69 77 77 78 78 79 79 80 80 82 82 84 84 85 85 86 86 87 87 89 89 92 92 93 93 94 94 95 95 97 97 98 98 99...
output:
930420562
result:
ok single line: '930420562'
Test #48:
score: 0
Accepted
time: 894ms
memory: 866384kb
input:
500000 500000 104719 385681 442316 160676 253844 367584 72590 496014 285563 238063 6357 315558 409856 429577 134892 354482 3148 28860 162136 499563 328064 140363 442837 262689 113621 474936 111094 490617 486474 348519 300513 391542 143543 96741 382979 168158 61724 175401 234833 92940 379640 3139 106...
output:
79326
result:
ok single line: '79326'
Test #49:
score: 0
Accepted
time: 368ms
memory: 851828kb
input:
500000 1 200561 44994
output:
509120988
result:
ok single line: '509120988'
Test #50:
score: 0
Accepted
time: 760ms
memory: 864256kb
input:
500000 375000 235998 54161 342652 239890 360735 495826 214088 432796 46540 216140 23202 382188 170588 431484 158417 28461 490013 83398 269300 40102 155401 179923 52175 280059 207279 239370 225104 118492 24709 448117 96884 268613 389857 312704 14182 210122 148274 81925 195440 288694 33478 261747 7790...
output:
39789711
result:
ok single line: '39789711'
Test #51:
score: 0
Accepted
time: 629ms
memory: 862140kb
input:
500000 250000 374803 130468 297168 262303 184483 342436 57712 86246 411251 85643 364966 441004 300210 140315 362089 445447 170398 8210 132300 113695 293344 344453 145705 71611 98409 37251 81027 149857 455220 258062 290136 194764 266717 136385 240962 270587 162998 443522 272063 153555 434982 482748 3...
output:
856794879
result:
ok single line: '856794879'
Test #52:
score: 0
Accepted
time: 523ms
memory: 856676kb
input:
500000 125000 241201 473811 1366 103849 266306 276634 215805 184316 427074 96311 476377 404414 168931 365274 216121 370335 171081 99414 46857 28929 410005 484468 477450 117300 362315 198700 267229 450188 337456 257759 177119 363852 97249 372751 450150 352178 290233 244920 486322 255792 379789 411441...
output:
390985382
result:
ok single line: '390985382'
Extra Test:
score: 0
Extra Test Passed