QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#647762 | #7434. 冷たい部屋、一人 | piggy123 | TL | 2820ms | 245964kb | C++20 | 8.3kb | 2024-10-17 15:35:57 | 2024-10-17 15:35:59 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a[500005],lg[500005],ans[500005],n,m;
int b[20][500005],c[20][500005];
struct qry {
ll l,r,id;
} p[500005],p2[500005];
vector<int> col[500005];
vector<pair<int,int>> CC[500005];
const ll S=1000;
ll S2=0;
struct block {
const ll B=800;
int tag[805],z[500005];
void add(ll pos,ll v) {
z[pos]+=v;
tag[(pos-1)/B+1]+=v;
}
ll query(ll pos) {
ll v=(pos-1)/B+1,r=(n-1)/B+1,ans=0;
for (ll i=v+1; i<=r; i++)ans+=tag[i];
for (ll i=pos; i<=v*B; i++)ans+=z[i];
return ans;
}
} B;
inline ll getmx(ll l,ll r) {
ll k=lg[r-l+1];
return max(c[k][l],c[k][r-(1<<k)+1]);
}
inline ll getmi(ll l,ll r) {
ll k=lg[r-l+1];
return min(b[k][l],b[k][r-(1<<k)+1]);
}
int v[1000005],cnt[1000005],d[1000005],nxt[1000005],to[1000005],T;
vector<qry> Q[1000005];
struct CHAIN {
int vis[1000005],ano[1000005],top;
array<ll,3> stk[1000005];
ll gx;
inline void init(ll len) {
for (ll i=0; i<=len; i++)vis[i]=0,ano[i]=i;
top=0,gx=0;
}
inline void link(ll a) {
ll l=ano[a],r=ano[a+1];
gx+=(a-l+1)*(r-a);
ano[l]=r,ano[r]=l;
stk[++top]= {l,r,a};
// cout<<"?" <<a<<" "<< sz[a]<<" "<<sz[a+1]<<"\n";
}
inline void add(ll pos) {
vis[d[pos]]++;
if (vis[d[pos]]==2) {
link(d[pos]);
}
}
inline void del(ll pos) {
vis[d[pos]]--;
if (vis[d[pos]]==1) {
redo(d[pos]);
}
}
inline void redo(ll d) {
auto tp=stk[top--];
gx-=(tp[2]-tp[0]+1)*(tp[1]-tp[2]);
ano[tp[0]]=tp[2];
ano[tp[1]]=tp[2]+1;
}
} C;
#define fread fread_unlocked
#define fwrite fwrite_unlocked
const int LEN=1<<25;int ED1=-1;
char Buf[LEN],*OP=Buf,*ED=Buf,Buf1[LEN+2];
inline void flush(){fwrite(Buf1,1,ED1+1,stdout),ED1=-1;}
inline char gc(){return (OP==ED)?(ED=(OP=Buf)+fread(Buf,1,LEN,stdin),*OP++):(*OP++);}
inline void pc(char ch){Buf1[ED1==LEN?(flush(),ED1=0):++ED1]=ch;}
inline int read(){
int x=0;char ch=gc();
while(!isdigit(ch)) ch=gc();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=gc();
return x;
}
inline void write(unsigned long long x){
if(x==0){pc('0');pc('\n');return;}
char ch[20];short cnt=-1;
while(x){
ch[++cnt]=(char)((x%10)^48);
x/=10;
}
for(int i=cnt;i>=0;--i) pc(ch[i]);
pc('\n');
}
int main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
n=read(),m=read();
for (ll i=1; i<=n; i++) {
a[i]=read();
col[a[i]].push_back(i);
}
for (ll i=1; i<=n; i++) {
if (i>1)lg[i]=lg[i>>1]+1;
b[0][i]=read();
c[0][i]=b[0][i];
}
for (ll i=1; i<=19; i++) {
for (ll j=1; j+(1ll<<i)-1<=n; j++) {
b[i][j]=min(b[i-1][j],b[i-1][j+(1ll<<(i-1))]);
c[i][j]=max(c[i-1][j],c[i-1][j+(1ll<<(i-1))]);
}
}
for (ll i=1; i<=m; i++) {
p[i].l=read(),p[i].r=read();
p[i].id=i;
}
for (ll i=1; i<=n; i++) {
if (col[i].size()<=S) {
for (ll j=0; j+1<(ll)col[i].size(); j++) {
CC[getmx(col[i][j],col[i][j+1])].push_back({i,j});
// for (ll k=j+1; k<(ll)col[i].size(); k++) {
// ll mi=getmi(col[i][j],col[i][k]),mx=getmx(col[i][j],col[i][k]);
//// CC[.emplace_back(mi);
// ++TT;
// V[TT]=mi;
// nxt1[TT]=head[mx];
// head[mx]=TT;
//
// }
}
}
}
sort(p+1,p+1+m,[](qry a,qry b) {
return a.r<b.r;
});
ll ps=0;
for (ll i=1; i<=m; i++) {
while (ps+1<=n&&ps+1<=p[i].r) {
for (pair<ll,ll> j:CC[ps+1]) {
ll mi=getmi(col[j.first][j.second],col[j.first][j.second+1]),mx=ps+1;
for (ll k=j.second; k>=0; k--) {
ll pmi=mi,pmx=mx;
for (ll l=j.second+1; l+1<=col[j.first].size(); l++) {
if (l==j.second+1){
}else{
ll tmx=getmx(col[j.first][l-1],col[j.first][l]),tmi=getmi(col[j.first][l-1],col[j.first][l]);
if (tmx>=pmx)break;
pmx=max(pmx,tmx);
pmi=min(pmi,tmi);
}
if (pmx!=ps+1)break;
B.add(pmi,1);
}
if (k!=0) {
mx=max(mx,getmx(col[j.first][k-1],col[j.first][k]));
mi=min(mi,getmi(col[j.first][k-1],col[j.first][k]));
}
if (mx!=ps+1)break;
}
}
ps++;
}
ans[p[i].id]+=B.query(p[i].l);
}
for (ll i=1; i<=n; i++) {
if (col[i].size()>S) {
T=i;
ll N=col[i].size();
vector<ll> book;
for (ll j=0; j+1<N; j++) {
ll mi=getmi(col[i][j],col[i][j+1]),mx=getmx(col[i][j],col[i][j+1]);
book.push_back(mi);
book.push_back(mx);
}
sort(book.begin(),book.end());
book.erase(unique(book.begin(),book.end()),book.end());
for (ll j=0; j+1<N; j++) {
ll mi=getmi(col[i][j],col[i][j+1]),mx=getmx(col[i][j],col[i][j+1]);
++cnt[lower_bound(book.begin(),book.end(),mi)-book.begin()+1];
++cnt[lower_bound(book.begin(),book.end(),mx)-book.begin()+1];
}
for (ll j=1; j<=(ll)book.size(); j++)cnt[j]+=cnt[j-1];
ll lim=cnt[book.size()];
for (ll j=0; j+1<N; j++) {
ll mi=getmi(col[i][j],col[i][j+1]),mx=getmx(col[i][j],col[i][j+1]);
ll mip=lower_bound(book.begin(),book.end(),mi)-book.begin()+1;
ll mxp=lower_bound(book.begin(),book.end(),mx)-book.begin()+1;
d[cnt[mip]--]=j;
to[cnt[mip]+1]=mi;
d[cnt[mxp]--]=j;
to[cnt[mxp]+1]=mx;
}
ll ps=0;
for (ll j=1; j<=n; j++) {
while (ps+1<=lim&&to[ps+1]<=j)ps++;
nxt[j]=ps;
}
S2=0.7*lim/sqrt(m)+1;
for (ll j=1; j<=m; j++) {
p2[j].l=nxt[p[j].l-1]+1,p2[j].r=nxt[p[j].r],p2[j].id=p[j].id;
if (p2[j].l<=p2[j].r) {
if ((p2[j].l-1)/S2==(p2[j].r-1)/S2) {
C.init(N);
for (ll k=p2[j].l; k<=p2[j].r; k++) {
C.add(k);
}
ans[p2[j].id]+=C.gx;
} else {
Q[(p2[j].l-1)/S2+1].push_back(p2[j]);
}
}
}
for (ll j=1; j<=(lim-1)/S2+1; j++) {
if (!Q[j].size())continue;
ll lb=j*S2;
C.init(N);
ll L=lb+1,R=lb;
// cout<<(j-1)*S2+1<<"~"<<j*S2<<":\n";
for (qry k:Q[j]) {
// cout<<k.l<<","<<k.r<<"\n";
while (R<k.r)C.add(++R);
while (L>k.l)C.add(--L);
ans[k.id]+=C.gx;
while (L<lb+1)C.del(L++);
}
}
for (ll j=0; j<=lim; j++)cnt[j]=to[j]=nxt[j]=d[j]=0,Q[j].clear();
}
}
for (ll i=1; i<=m; i++) {
write(ans[i]);
}
return flush(),0;
}
/*
■■■■■ ■■ ■■■ ■■■ ■ ■ ■ ■■■■ ■■■■
■ ■■ ■■ ■ ■■ ■ ■■ ■ ■ ■■ ■ ■■ ■■ ■
■ ■ ■■ ■ ■ ■ ■ ■ ■ ■■■ ■■ ■■ ■ ■■
■ ■ ■■ ■ ■ ■ ■ ■ ■ ■■ ■ ■■ ■■
■ ■ ■■ ■ ■ ■■ ■■ ■■ ■
■ ■■ ■■ ■ ■■■ ■ ■■■ ■■ ■■ ■■ ■■■
■■■■■ ■■ ■ ■ ■ ■ ■■ ■■ ■■ ■■
■ ■■ ■ ■ ■ ■ ■■ ■■ ■■ ■
■ ■■ ■ ■ ■ ■ ■■ ■■ ■ ■ ■■
■ ■■ ■■ ■■ ■■ ■■ ■■ ■■ ■ ■■ ■■
■ ■■ ■■■■ ■■■■ ■■ ■■ ■■■■■■ ■■■■
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 40428kb
input:
100 100 4 1 5 1 2 1 7 5 3 7 2 3 6 6 5 3 2 2 4 1 6 5 6 2 2 2 7 6 1 3 6 3 5 6 7 6 1 2 3 3 4 2 1 1 5 4 4 3 6 7 1 1 6 1 5 6 2 3 7 4 2 4 6 7 7 3 5 3 7 2 3 3 5 1 4 7 1 2 2 5 2 2 4 3 4 7 2 7 7 3 7 3 6 6 5 4 5 4 7 6 93 52 12 70 25 36 18 37 27 99 68 40 84 3 76 57 60 19 33 41 92 87 58 13 15 43 28 63 64 59 31 ...
output:
1 0 13 71 1 1 3 7 0 0 2 1 3 20 12 6 61 24 1 0 0 2 3 19 0 0 6 2 0 0 4 1 135 0 19 1 1 29 14 39 1 0 1 7 7 0 12 3 0 1 0 1 1 5 0 28 14 19 2 1 0 0 6 5 0 0 2 7 5 1 2 2 0 1 11 1 0 1 0 10 0 0 5 1 33 1 17 2 1 22 20 1 2 0 0 16 0 1 1 15
result:
ok 100 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 42528kb
input:
100 100 8 8 2 8 8 12 11 8 5 5 5 1 7 6 6 11 3 13 1 12 2 2 4 1 11 13 10 7 1 2 4 3 1 12 1 5 13 8 1 5 12 5 12 4 6 3 5 4 8 3 4 1 4 3 9 2 11 9 4 8 12 3 5 13 13 1 9 12 2 13 8 13 4 13 12 5 12 13 2 6 4 4 1 6 6 9 12 7 4 3 10 7 1 7 7 10 4 12 3 9 96 87 12 73 74 78 99 76 7 77 54 88 90 86 95 94 31 83 27 11 66 91 ...
output:
0 6 2 0 0 1 16 1 1 10 7 9 2 8 2 1 3 5 0 7 2 0 2 0 1 0 7 0 0 1 108 0 0 0 6 4 1 0 2 13 0 3 0 10 0 0 1 21 0 18 0 11 0 8 13 9 0 0 0 11 12 2 1 0 2 16 1 7 0 16 0 2 3 7 0 2 10 1 4 2 6 0 0 6 3 0 0 0 5 7 0 0 6 0 7 0 4 0 3 0
result:
ok 100 numbers
Test #3:
score: 0
Accepted
time: 4ms
memory: 38432kb
input:
100 100 13 4 2 1 1 2 1 39 20 1 1 1 33 1 1 1 9 37 21 7 14 58 1 3 19 29 40 56 2 1 3 1 42 1 1 13 1 3 5 4 49 1 1 8 8 3 1 14 1 1 2 6 17 3 2 2 2 9 3 1 17 90 1 1 1 1 8 14 17 16 1 33 15 20 46 22 2 20 11 1 28 3 1 4 1 17 3 9 10 2 1 2 2 6 1 1 3 17 27 2 86 82 24 49 50 32 63 20 53 11 60 1 16 27 15 14 12 88 52 17...
output:
1 84 13 0 7 4 26 1 9 1 7 3 10 0 7 3 6 4 4 0 13 1 0 4 4 0 40 22 36 0 5 6 0 37 28 213 1 6 10 4 0 3 5 0 3 5 25 2 0 1 3 12 1 39 0 8 4 2 6 0 6 4 23 17 0 0 4 13 6 6 0 0 6 10 11 30 0 7 10 10 101 0 1 0 62 0 10 100 26 4 5 1 24 0 1 4 15 3 0 6
result:
ok 100 numbers
Test #4:
score: 0
Accepted
time: 3ms
memory: 40692kb
input:
100 100 1 1 1 1 1 36 58 18 15 1 1 2 1 1 1 1 4 10 9 2 2 4 28 1 2 1 2 2 28 27 12 6 3 10 1 1 2 1 1 2 7 40 1 4 8 17 16 3 5 1 2 2 16 5 6 1 5 3 4 11 1 1 11 51 11 4 3 7 14 16 1 11 1 2 8 3 4 1 1 3 2 5 21 7 3 10 2 2 1 20 23 1 3 6 1 1 15 3 34 1 8 1 2 3 92 48 11 43 9 71 69 5 6 7 12 26 31 45 80 83 14 16 17 25 2...
output:
29 1 9 19 6 1 3 2 0 16 15 2 11 14 24 191 25 21 33 34 19 2 0 0 11 32 1 9 2 16 24 28 9 0 123 4 6 0 13 69 271 15 47 6 0 121 0 1 15 1 9 61 0 63 10 2 2 13 55 25 12 2 40 4 3 39 14 15 0 15 2 48 6 0 0 6 0 5 0 11 3 1 78 9 12 0 0 14 15 38 7 3 0 12 10 0 1 6 0 22
result:
ok 100 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 38468kb
input:
100 100 1 15 6 12 6 13 8 8 3 5 14 5 7 13 8 1 1 3 8 5 4 7 9 1 1 7 4 14 7 5 4 6 7 5 11 6 4 14 8 11 12 9 12 14 10 12 9 14 14 11 12 12 11 8 5 11 10 6 13 5 6 4 6 15 10 2 13 12 7 15 9 14 15 1 9 9 8 4 5 2 2 5 13 14 12 5 9 13 7 12 1 1 1 7 10 5 11 4 4 6 17 65 39 50 77 97 44 15 72 11 8 59 74 14 1 3 5 68 21 4 ...
output:
24 5 0 4 0 1 0 0 2 0 2 11 0 13 12 3 19 0 0 0 5 1 0 0 14 0 9 0 1 22 7 25 44 0 7 0 0 3 27 1 0 0 8 3 0 0 2 2 18 26 63 15 2 28 0 1 8 10 18 19 4 0 0 5 0 0 3 15 5 63 5 8 29 0 14 8 7 2 3 1 1 1 2 1 6 8 0 0 19 0 20 0 3 11 0 4 6 5 55 0
result:
ok 100 numbers
Test #6:
score: 0
Accepted
time: 4ms
memory: 63332kb
input:
5000 5000 2 29 12 10 25 32 45 18 16 38 41 50 8 32 54 37 18 29 37 42 9 38 25 43 35 5 47 20 32 35 8 14 8 37 30 16 45 19 14 33 14 31 31 33 28 12 11 49 32 6 11 4 50 39 3 55 25 26 13 40 41 44 31 31 18 19 25 18 29 19 21 1 52 19 2 53 39 55 11 27 54 22 16 49 12 23 41 22 34 38 40 20 5 35 43 40 29 14 20 40 6 ...
output:
21908 618 65611 229 7839 55433 12508 4205 5 12239 31375 1958 20 2290 29810 13020 12234 5752 14318 13451 122 0 109 3852 26843 12709 11522 14307 45468 886 5020 6667 21808 3367 637 593 37 5078 2698 61 364 20500 88231 2311 39 2487 18627 3425 194 4845 54212 84095 14695 8 67509 4364 312 23989 3876 86722 1...
result:
ok 5000 numbers
Test #7:
score: 0
Accepted
time: 8ms
memory: 65336kb
input:
5000 5000 15 86 121 63 26 26 74 43 35 32 48 131 61 120 103 48 101 1 70 97 130 105 30 38 68 141 85 141 108 17 143 106 47 90 4 68 63 8 79 26 10 66 48 61 18 75 62 84 80 113 20 27 109 102 32 13 20 63 12 53 112 146 33 27 49 110 55 132 121 67 75 18 38 80 140 62 7 20 104 4 42 91 67 20 127 77 13 141 64 3 28...
output:
0 132 8 26 0 32 1 61 40 0 0 0 0 18 49 15 0 14 2 63 24 9 10 94 10 21 1 2 1 6 17 21 1 83 19 9 0 21 67 8 13 0 0 0 13 1 0 21 0 13 1 123 0 0 8 0 0 10 14 2 32 2 8 53 29 0 23 6 6 0 0 13 0 1 0 3 0 0 1 0 5 15 15 0 4 4 1 0 1 0 0 2 1 0 0 0 0 1 2 1 11 23 45 1 0 9 14 104 60 8 3 1 2 38 34 32 1 0 0 38 27 18 62 0 5...
result:
ok 5000 numbers
Test #8:
score: 0
Accepted
time: 4ms
memory: 65492kb
input:
5000 5000 342 3 498 1667 87 63 8 215 1 25 67 5 7 600 1 1 51 14 6 1990 7 2707 105 637 5 805 328 74 1 57 316 236 6 1 1 700 965 2 493 21 12 2 1 1626 1 1352 11 109 1 2253 70 4 788 55 140 1 2 1 57 21 1 530 3060 62 266 86 32 1861 1 173 2 2 234 1 402 1392 101 9 7 1 8 3 8 137 46 4 17 212 1 4 10 6 1389 200 4...
output:
31295 316 211 102 965 1000 240 6385 76 10466 792 35 1756 169788 1195 1314 387 227 1144 30655 418 111933 122174 553 30337 24 67 125165 1286 28309 2796 6724 354 4078 17 138 11139 1 56797 1 2093 300 103019 8 257 28645 121966 128335 119276 5970 21 122331 475 103019 4 298 179 32016 121637 194237 53 12189...
result:
ok 5000 numbers
Test #9:
score: 0
Accepted
time: 3ms
memory: 67600kb
input:
5000 5000 27 32 25 415 15 148 94 43 16 3 71 1 11 33 159 1196 1069 752 1937 1 35 29 12 1 389 38 8 49 1 1 582 7 1274 30 9 123 68 14 3 7 88 4 11 3126 176 1304 6 659 118 128 1 537 100 784 225 42 37 36 2 15 2 359 411 60 4 261 1 3 61 11 88 154 2674 162 1014 1875 1 3 139 3 196 8 67 99 187 559 2 1 459 10 1 ...
output:
85 28 1761 27 50 45 0 43 1 3 5 4 15 425 0 1 7 23 1 42 0 0 7 51 3 27 28 3 26 0 58 82 53 494 9 88 33 33 17 49 9 0 63 105 0 9 17 1 252 11 3 107 1 2 0 0 17 24 5 414 0 70 98 40 29 553 216 521 2 246 0 122 6 14 0 4 70 310 72 23 191 115 5 3 12 0 0 6292 10 64 16 8 17 28 0 3 157 1 3 32 64 0 26 14 307 1 19 26 ...
result:
ok 5000 numbers
Test #10:
score: 0
Accepted
time: 4ms
memory: 63324kb
input:
5000 5000 11 23 46 15 52 41 22 12 24 42 36 22 61 6 21 31 43 15 11 54 20 58 57 39 51 14 2 41 35 20 16 12 9 25 39 8 60 32 20 60 51 52 19 34 19 60 33 48 17 42 12 50 38 4 30 16 48 49 55 58 57 5 39 61 39 32 51 14 2 10 57 43 41 8 12 5 58 36 14 34 32 17 49 24 60 58 55 60 25 18 6 3 44 47 7 17 24 5 10 35 7 1...
output:
608 171 30 6024 1921 142 1462 718 16 5 2 143 1939 971 40 59 3345 98 679 54 405 318 55 399 28 642 1481 0 58 1874 1591 0 1076 3357 465 3566 763 532 2615 337 0 1842 140 588 1753 0 197 3945 1753 33 1868 105 33 167 917 0 1895 45 1364 3626 1555 235 30 1964 4545 5583 360 214 530 263 1895 892 18 823 99 2593...
result:
ok 5000 numbers
Test #11:
score: 0
Accepted
time: 318ms
memory: 106556kb
input:
200000 200000 450 380 429 292 321 431 244 311 46 303 35 470 556 53 249 617 400 730 447 823 508 364 616 659 843 840 80 572 310 461 342 805 733 267 441 810 191 675 618 165 380 64 359 514 592 304 551 679 492 484 24 355 489 456 61 590 445 588 470 836 493 213 730 417 675 436 496 393 677 10 397 143 573 44...
output:
19810 486331 568929 123972 48879 617941 1254986 1109929 112192 594018 0 560940 13348 1728346 38662 16235 53474 756623 447220 925352 1878 8672 17371 853 144927 1300294 114644 72 104581 59 386661 1138358 1613460 160107 493876 88493 1693729 248416 553305 21021 174725 39537 35619 7653 270063 863775 2837...
result:
ok 200000 numbers
Test #12:
score: 0
Accepted
time: 633ms
memory: 153304kb
input:
200000 200000 19366 9283 162 4589 57 291 1 3 12 278 10 672 3 26 4 1 162500 668 1239 4473 2202 126 7615 9046 4210 1277 6 931 7 73 788 1779 8309 782 4 31785 414 4639 13637 753 5 1 66995 9 38399 9 1 38 7 12 111 88737 1020 1 219 3 18605 3 42958 22 1 7920 1 7602 12 320 1 2 329 3404 15 47 1 10 4 3 983 3 5...
output:
440126 282 5429197 709291 5127 2951009 400986 565805 754707 2118055 127676 1607596 171368 92820 2 4965288 28727 63187 22785 404331 227909 4610858 756314 12642 4605795 397393 826002 1800167 1312 5656 9753611 681410 1586016 424984 171353 13210 429893 450975 1468748 3678835 519882 4292364 92744 5540792...
result:
ok 200000 numbers
Test #13:
score: 0
Accepted
time: 334ms
memory: 111648kb
input:
200000 200000 439 423 431 156 500 66 55 258 324 478 379 397 378 100 69 435 473 107 68 141 14 135 325 472 366 383 86 435 510 2 369 91 237 13 498 125 229 161 150 291 294 340 402 448 133 376 151 450 383 468 440 244 428 335 386 260 98 416 131 59 237 420 442 261 203 180 217 287 108 39 76 375 372 161 42 2...
output:
569 1 5 17 49 25 24 44 129 3 104 3 0 11 39 28 290 1097 3 1 77 6 36 0 116 4 1 102 125 2163 31 439 20 447 66 59 826 162 102 0 7 55 45 81 18 9 82 60 22 176 0 1 1 0 91 99 69 222 196 1 393 9 11 221 20 102 205 10 81 6 54 11 25 133 13 12 2 651 33 55 1938 168 70 309 45 16 6 529 48 113 8 96 0 106 122 18 32 4...
result:
ok 200000 numbers
Test #14:
score: 0
Accepted
time: 405ms
memory: 110680kb
input:
200000 200000 228 251 350 336 5 294 243 346 149 70 40 9 9 268 345 368 321 208 297 400 99 393 47 74 6 165 186 342 213 88 342 154 69 299 338 343 284 369 244 383 222 193 29 258 57 330 318 182 208 267 19 126 399 176 130 234 269 371 157 197 323 22 353 54 42 254 74 51 229 273 184 110 259 20 83 331 198 237...
output:
2066 494364 362367 20912 855182 132 41752 296700 354499 26447 3 115816 101126 1021 363411 47287 335332 2514 169274 546403 72927 11625 542095 947423 35177 424 4563575 599876 30536 498643 4201818 4048867 252836 330747 765363 615466 149218 481706 20491 35466 29582 208375 32004 106458 4375 575738 353105...
result:
ok 200000 numbers
Test #15:
score: 0
Accepted
time: 608ms
memory: 157268kb
input:
200000 200000 529 141913 5 89617 14 3437 2 1 47497 26 25158 38 70376 3 3954 2 2 58116 22 92 2004 35533 2 908 2 643 666 18673 232 8 34661 11 42 1 5 1 1049 5 2 10293 18 8 8 5620 21 2 4 10659 119 2188 1978 71 162 3 3 2 31252 28033 64 6 294 7 3326 45122 5434 8116 57988 1 23569 97887 49962 3454 2 2 480 6...
output:
23983 53979 1436596 16997571 1849218 4330384 42931 106130 106774 17167976 190194 764660 1089913 316708 637652 109551 34800179 3372756 395432 5732 310738 133719 9364240 4342982 670 126462 36177 10534603 52948 883715 7770045 1061371 915042 76879 4908113 548469 18353972 7923425 162716 186 33185683 4862...
result:
ok 200000 numbers
Test #16:
score: 0
Accepted
time: 2798ms
memory: 237500kb
input:
500000 500000 56054 23 60793 11447 170 694 1350 2 15432 3 1236 18 1695 154949 53632 1 2899 49094 47 67 1 1855 6706 5285 3785 100381 165 109319 23 350651 103 660 2248 2863 69 696 49937 432 1 6 49527 652 1 48 18 106771 93430 68421 638 780 9 189 100 15425 13255 1 5 1992 1440 176 260 81151 277 22129 101...
output:
1416 109646 7847304 24025484 2001948 32059390 84 4983 1828175 3876641 486 637776 984571 154650 2267349 71978 1845917 296695 2290975 2109104 328351 13561619 1359093 472126 681282 3766969 10241540 1095889 5489462 18533 456271 1015402 196375 4571 2261507 22012378 390562 925535 1107831 8930689 29763 752...
result:
ok 500000 numbers
Test #17:
score: 0
Accepted
time: 2820ms
memory: 245964kb
input:
500000 500000 4 1864 2 12 260 54595 3896 101 82389 44574 4038 115410 13 19168 17255 4 2 4 18 37 44 103 1 68042 80389 17853 21354 27 1 7395 1 12707 200068 24850 23476 133591 6 91036 14483 2281 1336 115 85 81 342 4387 5 1 34 5 17 215 105 8778 11 26 11 2 45 25 834 1 6 130 182083 95 10894 543 1355 2 152...
output:
39052 6579785 1847540 13884 19698977 229347 34291951 23087713 105421 44616293 9406921 11554132 18708 45803401 538457 41087 19089 9942808 8960008 10523103 19869104 1767445 147365 11494908 274087 26092656 1892653 371098 327901 1884781 27656378 133755 6718 30437601 267942 4107744 25226025 11850329 3738...
result:
ok 500000 numbers
Test #18:
score: -100
Time Limit Exceeded
input:
500000 500000 375 43 74 8 444 393 118 78 298 260 202 195 233 369 453 161 125 264 343 420 39 363 197 97 382 263 193 64 385 58 127 303 65 268 154 198 91 255 221 97 169 385 157 47 24 431 146 107 194 294 79 54 33 417 117 453 406 15 427 176 344 47 42 79 340 311 129 349 190 437 157 31 227 165 42 121 21 41...