oj.uz

Submission #96484

# Submission time Handle Problem Language Result Execution time Memory
96484 2019-02-09T16:10:24 Z figter001 Horses (IOI15_horses) C++14
100 / 100
 1235 ms 69220 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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