oj.uz

Submission #1085538

# Submission time Handle Problem Language Result Execution time Memory
1085538 2024-09-08T11:45:53 Z 4QT0R Horses (IOI15_horses) C++17
20 / 100
 213 ms 78008 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[500002];

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;
		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:67:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   67 |  return ans(max_tree[1].ind);
      |             ~~~~~~~~~~~~^~~
horses.cpp:67:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   67 |  return ans(max_tree[1].ind);
      |         ~~~^~~~~~~~~~~~~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:89:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   89 |  return ans(max_tree[1].ind);
      |             ~~~~~~~~~~~~^~~
horses.cpp:89:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   89 |  return ans(max_tree[1].ind);
      |         ~~~^~~~~~~~~~~~~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:119:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  119 |  return ans(max_tree[1].ind);
      |             ~~~~~~~~~~~~^~~
horses.cpp:119:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  119 |  return ans(max_tree[1].ind);
      |         ~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 35164 KB Output is correct
2 Correct 11 ms 35164 KB Output is correct
3 Correct 11 ms 35368 KB Output is correct
4 Correct 10 ms 35164 KB Output is correct
5 Correct 11 ms 35348 KB Output is correct
6 Correct 11 ms 35164 KB Output is correct
7 Correct 11 ms 35164 KB Output is correct
8 Correct 11 ms 35364 KB Output is correct
9 Correct 10 ms 35288 KB Output is correct
10 Correct 11 ms 35160 KB Output is correct
11 Correct 10 ms 35296 KB Output is correct
12 Incorrect 11 ms 35164 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 35164 KB Output is correct
2 Correct 10 ms 35304 KB Output is correct
3 Correct 9 ms 35164 KB Output is correct
4 Correct 10 ms 35164 KB Output is correct
5 Correct 15 ms 35164 KB Output is correct
6 Correct 11 ms 35160 KB Output is correct
7 Correct 10 ms 35260 KB Output is correct
8 Correct 11 ms 35164 KB Output is correct
9 Correct 12 ms 35264 KB Output is correct
10 Correct 11 ms 35164 KB Output is correct
11 Correct 12 ms 35384 KB Output is correct
12 Incorrect 12 ms 35164 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 67156 KB Output is correct
2 Correct 211 ms 78008 KB Output is correct
3 Correct 213 ms 69136 KB Output is correct
4 Correct 182 ms 73020 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 35164 KB Output is correct
2 Correct 10 ms 35180 KB Output is correct
3 Correct 10 ms 35164 KB Output is correct
4 Correct 10 ms 35164 KB Output is correct
5 Correct 10 ms 35164 KB Output is correct
6 Correct 15 ms 35164 KB Output is correct
7 Correct 10 ms 35380 KB Output is correct
8 Correct 11 ms 35164 KB Output is correct
9 Correct 11 ms 35308 KB Output is correct
10 Correct 9 ms 35164 KB Output is correct
11 Correct 11 ms 35164 KB Output is correct
12 Incorrect 11 ms 35304 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 35164 KB Output is correct
2 Correct 10 ms 35164 KB Output is correct
3 Correct 10 ms 35160 KB Output is correct
4 Correct 11 ms 35164 KB Output is correct
5 Correct 10 ms 35292 KB Output is correct
6 Correct 11 ms 35164 KB Output is correct
7 Correct 10 ms 35164 KB Output is correct
8 Correct 10 ms 35284 KB Output is correct
9 Correct 10 ms 35160 KB Output is correct
10 Correct 10 ms 35368 KB Output is correct
11 Correct 10 ms 35160 KB Output is correct
12 Incorrect 13 ms 35164 KB Output isn't correct
13 Halted 0 ms 0 KB -