oj.uz

Submission #1085553

# Submission time Handle Problem Language Result Execution time Memory
1085553 2024-09-08T11:59:40 Z 4QT0R Horses (IOI15_horses) C++17
100 / 100
 245 ms 78160 KB 
#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
#define ll long long
#define ld long double

struct node{
	ld sum;
	ld max_pref;
	ll ind;
};

const ll mod=1e9+7;

const ll base=1<<19;
node max_tree[2*base];
ll xprod[2*base];
ll cost[base+1];

ll fast_pow(ll a, ll b){
	if (b==1)return a;
	ll cur=fast_pow(a,b/2);
	cur=(cur*cur)%mod;
	if (b&1)cur=(cur*a)%mod;
	return cur;
}

void start(int v){
	if (v>=base){
		if (!xprod[v])xprod[v]=1;
		if (!cost[v-base])cost[v-base]=1;
		return;
	}
	start(2*v);
	start(2*v+1);
	xprod[v]=(xprod[2*v]*xprod[2*v+1])%mod;
	max_tree[v]=max_tree[2*v];
	if (max_tree[v].sum+max_tree[2*v+1].max_pref>max_tree[v].max_pref){
		max_tree[v].max_pref=max_tree[v].sum+max_tree[2*v+1].max_pref;
		max_tree[v].ind=max_tree[2*v+1].ind;
	}
	max_tree[v].sum+=max_tree[2*v+1].sum;
}

void mult(ll &a, ll b){
	a=(a*b)%mod;
}

ll ans(int v){
	ll odp=cost[v];
	v+=base+1;
	while(v>1){
		if (v&1)mult(odp,xprod[v-1]);
		v>>=1;
	}
	return odp;
}

int init(int n, int x[], int y[]){
	for (int i = 1; i<=n; i++){
		cost[i]=y[i-1];
		xprod[i+base]=x[i-1];
		max_tree[i+base].sum=logl(x[i-1])+logl(y[i-1])-logl(i==1?1:y[i-2]);
		max_tree[i+base].max_pref=max_tree[i+base].sum;
		max_tree[i+base].ind=i;
	}
	start(1);
	return ans(max_tree[1].ind);
}

int updateX(int pos, int val){
	pos++;
	int v=pos+base;
	xprod[v]=val;
	max_tree[v].sum=logl(val)+logl(cost[pos])-logl(cost[pos-1]);
	max_tree[v].max_pref=max_tree[v].sum;
	v>>=1;
	while(v){
		xprod[v]=xprod[2*v];
		mult(xprod[v],xprod[2*v+1]);

		max_tree[v]=max_tree[2*v];
		if (max_tree[v].sum+max_tree[2*v+1].max_pref>max_tree[v].max_pref){
			max_tree[v].max_pref=max_tree[v].sum+max_tree[2*v+1].max_pref;
			max_tree[v].ind=max_tree[2*v+1].ind;
		}
		max_tree[v].sum+=max_tree[2*v+1].sum;
		v>>=1;
	}
	return ans(max_tree[1].ind);
}

int updateY(int pos, int val){
	pos++;
	int v=pos+base;
	int v2=pos+1+base;
	cost[pos]=val;
	max_tree[v].sum=logl(xprod[v])+logl(cost[pos])-logl(cost[pos-1]);
	max_tree[v].max_pref=max_tree[v].sum;
	v>>=1;
	max_tree[v2].sum=logl(xprod[v2])+logl(cost[pos+1])-logl(cost[pos]);
	max_tree[v2].max_pref=max_tree[v2].sum;
	v2>>=1;
	while(v){
		max_tree[v]=max_tree[2*v];
		if (max_tree[v].sum+max_tree[2*v+1].max_pref>max_tree[v].max_pref){
			max_tree[v].max_pref=max_tree[v].sum+max_tree[2*v+1].max_pref;
			max_tree[v].ind=max_tree[2*v+1].ind;
		}
		max_tree[v].sum+=max_tree[2*v+1].sum;
		v>>=1;
		max_tree[v2]=max_tree[2*v2];
		if (max_tree[v2].sum+max_tree[2*v2+1].max_pref>max_tree[v2].max_pref){
			max_tree[v2].max_pref=max_tree[v2].sum+max_tree[2*v2+1].max_pref;
			max_tree[v2].ind=max_tree[2*v2+1].ind;
		}
		max_tree[v2].sum+=max_tree[2*v2+1].sum;
		v2>>=1;
	}
	return ans(max_tree[1].ind);
}

Compilation message

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:68:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   68 |  return ans(max_tree[1].ind);
      |             ~~~~~~~~~~~~^~~
horses.cpp:68:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   68 |  return ans(max_tree[1].ind);
      |         ~~~^~~~~~~~~~~~~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:90:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   90 |  return ans(max_tree[1].ind);
      |             ~~~~~~~~~~~~^~~
horses.cpp:90:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   90 |  return ans(max_tree[1].ind);
      |         ~~~^~~~~~~~~~~~~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:120:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  120 |  return ans(max_tree[1].ind);
      |             ~~~~~~~~~~~~^~~
horses.cpp:120:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  120 |  return ans(max_tree[1].ind);
      |         ~~~^~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 37200 KB Output is correct
2 Correct 23 ms 37228 KB Output is correct
3 Correct 24 ms 37208 KB Output is correct
4 Correct 25 ms 37284 KB Output is correct
5 Correct 23 ms 37256 KB Output is correct
6 Correct 21 ms 37208 KB Output is correct
7 Correct 20 ms 37212 KB Output is correct
8 Correct 23 ms 37264 KB Output is correct
9 Correct 23 ms 37204 KB Output is correct
10 Correct 22 ms 37212 KB Output is correct
11 Correct 23 ms 37212 KB Output is correct
12 Correct 25 ms 37184 KB Output is correct
13 Correct 21 ms 37360 KB Output is correct
14 Correct 21 ms 37204 KB Output is correct
15 Correct 22 ms 37284 KB Output is correct
16 Correct 22 ms 37200 KB Output is correct
17 Correct 24 ms 37204 KB Output is correct
18 Correct 23 ms 37212 KB Output is correct
19 Correct 22 ms 37212 KB Output is correct
20 Correct 22 ms 37204 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 37204 KB Output is correct
2 Correct 20 ms 37212 KB Output is correct
3 Correct 21 ms 37212 KB Output is correct
4 Correct 34 ms 37204 KB Output is correct
5 Correct 23 ms 37192 KB Output is correct
6 Correct 21 ms 37208 KB Output is correct
7 Correct 20 ms 37320 KB Output is correct
8 Correct 23 ms 37200 KB Output is correct
9 Correct 22 ms 37352 KB Output is correct
10 Correct 28 ms 37328 KB Output is correct
11 Correct 22 ms 37428 KB Output is correct
12 Correct 24 ms 37232 KB Output is correct
13 Correct 23 ms 37292 KB Output is correct
14 Correct 27 ms 37212 KB Output is correct
15 Correct 29 ms 37320 KB Output is correct
16 Correct 26 ms 37268 KB Output is correct
17 Correct 22 ms 37388 KB Output is correct
18 Correct 22 ms 37212 KB Output is correct
19 Correct 24 ms 37356 KB Output is correct
20 Correct 22 ms 37376 KB Output is correct
21 Correct 24 ms 37372 KB Output is correct
22 Correct 27 ms 37212 KB Output is correct
23 Correct 34 ms 37468 KB Output is correct
24 Correct 22 ms 37400 KB Output is correct
25 Correct 22 ms 37468 KB Output is correct
26 Correct 22 ms 37468 KB Output is correct
27 Correct 23 ms 37276 KB Output is correct
28 Correct 25 ms 37404 KB Output is correct
29 Correct 24 ms 37460 KB Output is correct
30 Correct 22 ms 37456 KB Output is correct
31 Correct 31 ms 37352 KB Output is correct
32 Correct 22 ms 37468 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 69456 KB Output is correct
2 Correct 233 ms 77040 KB Output is correct
3 Correct 232 ms 69124 KB Output is correct
4 Correct 200 ms 72948 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 37288 KB Output is correct
2 Correct 28 ms 37320 KB Output is correct
3 Correct 21 ms 37212 KB Output is correct
4 Correct 25 ms 37396 KB Output is correct
5 Correct 20 ms 37212 KB Output is correct
6 Correct 22 ms 37292 KB Output is correct
7 Correct 23 ms 37212 KB Output is correct
8 Correct 20 ms 37244 KB Output is correct
9 Correct 21 ms 37200 KB Output is correct
10 Correct 22 ms 37212 KB Output is correct
11 Correct 21 ms 37312 KB Output is correct
12 Correct 23 ms 37212 KB Output is correct
13 Correct 21 ms 37212 KB Output is correct
14 Correct 22 ms 37208 KB Output is correct
15 Correct 23 ms 37200 KB Output is correct
16 Correct 22 ms 37212 KB Output is correct
17 Correct 22 ms 37212 KB Output is correct
18 Correct 20 ms 37432 KB Output is correct
19 Correct 21 ms 37212 KB Output is correct
20 Correct 20 ms 37416 KB Output is correct
21 Correct 22 ms 37212 KB Output is correct
22 Correct 21 ms 37212 KB Output is correct
23 Correct 23 ms 37428 KB Output is correct
24 Correct 23 ms 37316 KB Output is correct
25 Correct 23 ms 37464 KB Output is correct
26 Correct 24 ms 37356 KB Output is correct
27 Correct 22 ms 37268 KB Output is correct
28 Correct 23 ms 37468 KB Output is correct
29 Correct 20 ms 37376 KB Output is correct
30 Correct 21 ms 37452 KB Output is correct
31 Correct 24 ms 37316 KB Output is correct
32 Correct 22 ms 37468 KB Output is correct
33 Correct 135 ms 68580 KB Output is correct
34 Correct 129 ms 68692 KB Output is correct
35 Correct 120 ms 75708 KB Output is correct
36 Correct 129 ms 75600 KB Output is correct
37 Correct 126 ms 66848 KB Output is correct
38 Correct 119 ms 67668 KB Output is correct
39 Correct 116 ms 66640 KB Output is correct
40 Correct 139 ms 70736 KB Output is correct
41 Correct 127 ms 66900 KB Output is correct
42 Correct 119 ms 66796 KB Output is correct
43 Correct 132 ms 70988 KB Output is correct
44 Correct 126 ms 71116 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37200 KB Output is correct
2 Correct 22 ms 37236 KB Output is correct
3 Correct 23 ms 37208 KB Output is correct
4 Correct 23 ms 37212 KB Output is correct
5 Correct 21 ms 37200 KB Output is correct
6 Correct 20 ms 37212 KB Output is correct
7 Correct 20 ms 37212 KB Output is correct
8 Correct 21 ms 37212 KB Output is correct
9 Correct 20 ms 37212 KB Output is correct
10 Correct 22 ms 37212 KB Output is correct
11 Correct 22 ms 37212 KB Output is correct
12 Correct 20 ms 37212 KB Output is correct
13 Correct 22 ms 37212 KB Output is correct
14 Correct 21 ms 37212 KB Output is correct
15 Correct 20 ms 37212 KB Output is correct
16 Correct 20 ms 37268 KB Output is correct
17 Correct 21 ms 37208 KB Output is correct
18 Correct 22 ms 37376 KB Output is correct
19 Correct 20 ms 37296 KB Output is correct
20 Correct 23 ms 37212 KB Output is correct
21 Correct 21 ms 37340 KB Output is correct
22 Correct 20 ms 37212 KB Output is correct
23 Correct 23 ms 37468 KB Output is correct
24 Correct 23 ms 37464 KB Output is correct
25 Correct 22 ms 37468 KB Output is correct
26 Correct 23 ms 37516 KB Output is correct
27 Correct 21 ms 37468 KB Output is correct
28 Correct 20 ms 37404 KB Output is correct
29 Correct 22 ms 37464 KB Output is correct
30 Correct 21 ms 37468 KB Output is correct
31 Correct 22 ms 37464 KB Output is correct
32 Correct 23 ms 37356 KB Output is correct
33 Correct 209 ms 69560 KB Output is correct
34 Correct 221 ms 78160 KB Output is correct
35 Correct 236 ms 69404 KB Output is correct
36 Correct 196 ms 73228 KB Output is correct
37 Correct 137 ms 68692 KB Output is correct
38 Correct 135 ms 68688 KB Output is correct
39 Correct 139 ms 75604 KB Output is correct
40 Correct 129 ms 75544 KB Output is correct
41 Correct 126 ms 66900 KB Output is correct
42 Correct 128 ms 68012 KB Output is correct
43 Correct 126 ms 66768 KB Output is correct
44 Correct 141 ms 70736 KB Output is correct
45 Correct 125 ms 66896 KB Output is correct
46 Correct 118 ms 66728 KB Output is correct
47 Correct 127 ms 71088 KB Output is correct
48 Correct 129 ms 70964 KB Output is correct
49 Correct 241 ms 70736 KB Output is correct
50 Correct 235 ms 70736 KB Output is correct
51 Correct 199 ms 77384 KB Output is correct
52 Correct 204 ms 76880 KB Output is correct
53 Correct 245 ms 68944 KB Output is correct
54 Correct 180 ms 69480 KB Output is correct
55 Correct 175 ms 67720 KB Output is correct
56 Correct 193 ms 72428 KB Output is correct
57 Correct 203 ms 68432 KB Output is correct
58 Correct 180 ms 68944 KB Output is correct
59 Correct 134 ms 71052 KB Output is correct