답안 #96484 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
96484	2019-02-09T16:10:24 Z	figter001	말 (IOI15_horses)	C++14	100 / 100	1235 ms	69220 KB

horses

#include "horses.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
const int maxn = 5e5 + 50;
const int mod = 1e9+7;

ld lgx[maxn],lgy[maxn],seg2[(1<<20)];
ll seg[(1<<20)],y[maxn],x[maxn];
int best[(1<<20)];
int n,l,r;

ld getsum(int n,int s,int e){
	if(s > r || e < l)return 0;
	if(s >= l && e <= r){
		return seg2[n];
	}
	return getsum(n*2,s,(s+e)/2) + getsum(n*2+1,(s+e)/2+1,e);
}

void build1(int n,int s,int e){
	if(s == e){
		seg[n] = x[s];
		seg2[n] = lgx[s];
		return;
	}
	build1(n*2,s,(s+e)/2);
	build1(n*2+1,(s+e)/2+1,e);
	seg[n] = (seg[n*2] * seg[n*2+1])%mod;
	seg2[n] = seg2[n*2] + seg2[n*2+1];
}

void build2(int n,int s,int e){
	if(s == e){
		best[n] = s;
		return;
	}
	build2(n*2,s,(s+e)/2);
	build2(n*2+1,(s+e)/2+1,e);
	l = 1;r = best[n*2];
	ld v = getsum(1,1,::n);
	ld left = v + lgy[r];
	r = best[n*2+1];
	v = getsum(1,1,::n);
	ld right = v + lgy[r];
	if(left >= right)best[n] = best[n*2];
	else best[n] = best[n*2+1];
}


void update1(int n,int s,int e){
	if(s > r || e < l)return;
	if(s == e){
		seg[n] = x[s];
		seg2[n] = lgx[s];
		return;
	}
	update1(n*2,s,(s+e)/2);
	update1(n*2+1,(s+e)/2+1,e);
	seg[n] = (seg[n*2] * seg[n*2+1])%mod;
	seg2[n] = (seg2[n*2] + seg2[n*2+1]);
}

void update2(int n,int s,int e){
	if(s > r || e < l)return;
	if(s == e){
		best[n] = s;
		return;
	}
	update2(n*2,s,(s+e)/2);
	update2(n*2+1,(s+e)/2+1,e);
	l = 1;r = best[n*2];
	ld left = getsum(1,1,::n) + lgy[r];
	r = best[n*2+1];
	ld right = getsum(1,1,::n) + lgy[r];
	if(left >= right)best[n] = best[n*2];
	else best[n] = best[n*2+1];
}
	
ll get(int n,int s,int e){
	if(s > r || e < l)return 1;
	if(s >= l && e <= r)return seg[n];
	return (get(n*2,s,(s+e)/2) * get(n*2+1,(s+e)/2+1,e))%mod;
}

int solve(){
	l = 1;
	r = best[1];
	return (get(1,1,n) * y[r])%mod;
}

int init(int N, int X[], int Y[]){
	n = N;
	for(int i=1;i<=n;i++){
		y[i] = Y[i-1];
		x[i] = X[i-1];
		lgx[i] = log(x[i]);
		lgy[i] = log(y[i]);
	}
	build1(1,1,n);
	build2(1,1,n);
	return solve();
}

int updateX(int pos, int val) {	
	pos++;
	x[pos] = val;
	lgx[pos] = log(x[pos]);
	l = r = pos;
	update1(1,1,n);
	update2(1,1,n);
	return solve();
}

int updateY(int pos, int val) {
	pos++;
	y[pos] = val;
	lgy[pos] = log(y[pos]);
	l = r = pos;
	update2(1,1,n);
	return solve();
}

Compilation message

horses.cpp: In function 'ld getsum(int, int, int)':
horses.cpp:16:28: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 ld getsum(int n,int s,int e){
                            ^
horses.cpp:14:5: note: shadowed declaration is here
 int n,l,r;
     ^
horses.cpp: In function 'void build1(int, int, int)':
horses.cpp:24:30: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 void build1(int n,int s,int e){
                              ^
horses.cpp:14:5: note: shadowed declaration is here
 int n,l,r;
     ^
horses.cpp: In function 'void build2(int, int, int)':
horses.cpp:36:30: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 void build2(int n,int s,int e){
                              ^
horses.cpp:14:5: note: shadowed declaration is here
 int n,l,r;
     ^
horses.cpp: In function 'void update1(int, int, int)':
horses.cpp:54:31: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 void update1(int n,int s,int e){
                               ^
horses.cpp:14:5: note: shadowed declaration is here
 int n,l,r;
     ^
horses.cpp: In function 'void update2(int, int, int)':
horses.cpp:67:31: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 void update2(int n,int s,int e){
                               ^
horses.cpp:14:5: note: shadowed declaration is here
 int n,l,r;
     ^
horses.cpp: In function 'll get(int, int, int)':
horses.cpp:83:25: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 ll get(int n,int s,int e){
                         ^
horses.cpp:14:5: note: shadowed declaration is here
 int n,l,r;
     ^
horses.cpp: In function 'int solve()':
horses.cpp:92:28: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return (get(1,1,n) * y[r])%mod;
         ~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	380 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	380 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	424 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	2 ms	376 KB	Output is correct
19	Correct	2 ms	376 KB	Output is correct
20	Correct	2 ms	376 KB	Output is correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	380 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	380 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	2 ms	376 KB	Output is correct
19	Correct	2 ms	376 KB	Output is correct
20	Correct	2 ms	376 KB	Output is correct
21	Correct	2 ms	376 KB	Output is correct
22	Correct	2 ms	376 KB	Output is correct
23	Correct	4 ms	504 KB	Output is correct
24	Correct	4 ms	504 KB	Output is correct
25	Correct	4 ms	504 KB	Output is correct
26	Correct	3 ms	508 KB	Output is correct
27	Correct	4 ms	504 KB	Output is correct
28	Correct	4 ms	504 KB	Output is correct
29	Correct	4 ms	504 KB	Output is correct
30	Correct	5 ms	504 KB	Output is correct
31	Correct	4 ms	504 KB	Output is correct
32	Correct	4 ms	504 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	662 ms	57444 KB	Output is correct
2	Correct	773 ms	57504 KB	Output is correct
3	Correct	847 ms	57464 KB	Output is correct
4	Correct	922 ms	57540 KB	Output is correct

Subtask #4
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	504 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	2 ms	376 KB	Output is correct
19	Correct	2 ms	380 KB	Output is correct
20	Correct	2 ms	376 KB	Output is correct
21	Correct	2 ms	376 KB	Output is correct
22	Correct	2 ms	376 KB	Output is correct
23	Correct	4 ms	504 KB	Output is correct
24	Correct	4 ms	504 KB	Output is correct
25	Correct	4 ms	504 KB	Output is correct
26	Correct	3 ms	504 KB	Output is correct
27	Correct	4 ms	504 KB	Output is correct
28	Correct	3 ms	504 KB	Output is correct
29	Correct	4 ms	504 KB	Output is correct
30	Correct	4 ms	504 KB	Output is correct
31	Correct	4 ms	504 KB	Output is correct
32	Correct	4 ms	424 KB	Output is correct
33	Correct	337 ms	56664 KB	Output is correct
34	Correct	331 ms	56568 KB	Output is correct
35	Correct	361 ms	56596 KB	Output is correct
36	Correct	294 ms	56580 KB	Output is correct
37	Correct	318 ms	56696 KB	Output is correct
38	Correct	275 ms	56568 KB	Output is correct
39	Correct	288 ms	56412 KB	Output is correct
40	Correct	281 ms	56568 KB	Output is correct
41	Correct	271 ms	56568 KB	Output is correct
42	Correct	276 ms	56824 KB	Output is correct
43	Correct	224 ms	56480 KB	Output is correct
44	Correct	226 ms	62840 KB	Output is correct

Subtask #5
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	372 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	2 ms	376 KB	Output is correct
19	Correct	2 ms	376 KB	Output is correct
20	Correct	2 ms	376 KB	Output is correct
21	Correct	2 ms	376 KB	Output is correct
22	Correct	2 ms	376 KB	Output is correct
23	Correct	5 ms	504 KB	Output is correct
24	Correct	4 ms	504 KB	Output is correct
25	Correct	4 ms	504 KB	Output is correct
26	Correct	3 ms	504 KB	Output is correct
27	Correct	4 ms	504 KB	Output is correct
28	Correct	4 ms	504 KB	Output is correct
29	Correct	4 ms	504 KB	Output is correct
30	Correct	4 ms	504 KB	Output is correct
31	Correct	0 ms	504 KB	Output is correct
32	Correct	17 ms	508 KB	Output is correct
33	Correct	684 ms	57432 KB	Output is correct
34	Correct	776 ms	57464 KB	Output is correct
35	Correct	970 ms	57520 KB	Output is correct
36	Correct	983 ms	57464 KB	Output is correct
37	Correct	358 ms	56696 KB	Output is correct
38	Correct	319 ms	56568 KB	Output is correct
39	Correct	328 ms	56696 KB	Output is correct
40	Correct	284 ms	56568 KB	Output is correct
41	Correct	329 ms	56568 KB	Output is correct
42	Correct	275 ms	56568 KB	Output is correct
43	Correct	313 ms	56440 KB	Output is correct
44	Correct	318 ms	56696 KB	Output is correct
45	Correct	277 ms	56608 KB	Output is correct
46	Correct	285 ms	56708 KB	Output is correct
47	Correct	230 ms	56568 KB	Output is correct
48	Correct	232 ms	62852 KB	Output is correct
49	Correct	1137 ms	62640 KB	Output is correct
50	Correct	1105 ms	62472 KB	Output is correct
51	Correct	705 ms	69220 KB	Output is correct
52	Correct	556 ms	68748 KB	Output is correct
53	Correct	1235 ms	60940 KB	Output is correct
54	Correct	656 ms	61432 KB	Output is correct
55	Correct	836 ms	59640 KB	Output is correct
56	Correct	713 ms	64360 KB	Output is correct
57	Correct	808 ms	60180 KB	Output is correct
58	Correct	810 ms	60920 KB	Output is correct
59	Correct	244 ms	62840 KB	Output is correct

답안 #96484

Compilation message

Subtask #1 17.0 / 17.0

Subtask #2 17.0 / 17.0

Subtask #3 20.0 / 20.0

Subtask #4 23.0 / 23.0

Subtask #5 23.0 / 23.0

Subtask #1
17.0 / 17.0

Subtask #2
17.0 / 17.0

Subtask #3
20.0 / 20.0

Subtask #4
23.0 / 23.0

Subtask #5
23.0 / 23.0