QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#647762#7434. 冷たい部屋、一人piggy123TL 2820ms245964kbC++208.3kb2024-10-17 15:35:572024-10-17 15:35:59

Judging History

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

  • [2024-10-17 15:35:59]
  • 评测
  • 测评结果:TL
  • 用时:2820ms
  • 内存:245964kb
  • [2024-10-17 15:35:57]
  • 提交

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...

output:


result: