oj.uz

Submission #1039454

# Submission time Handle Problem Language Result Execution time Memory
1039454 2024-07-30T22:46:59 Z HappyCapybara Horses (IOI15_horses) C++17
0 / 100
 1500 ms 73044 KB 
#include "horses.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long

int n;
vector<pair<int,double>> stl;
vector<double> lazy;
vector<ll> stm;
vector<int> x, y;

void updatem(int pos, int val, int node=1, int tl=0, int tr=n-1){
	if (tl == tr){
		stm[node] = val;
		return;
	}
	int tm = (tl+tr)/2;
	if (pos <= tm) updatem(pos, val, node*2, tl, tm);
	else updatem(pos, val, node*2+1, tm+1, tr);
	stm[node] = (stm[node*2]*stm[node*2+1]) % 1000000007;
}

int querym(int l, int r, int node=1, int tl=0, int tr=n-1){
	//cout << l << " " << r << " " << tl << " " << tr << "\n";
	if (l <= tl && tr <= r) return stm[node];
	int tm = (tl+tr)/2;
	int res = 1;
	if (l <= tm) res = (res*querym(l, r, node*2, tl, tm)) % 1000000007;
	if (tm+1 <= r) res = (res*querym(l, r, node*2+1, tm+1, tr)) % 1000000007;
	return res;
}

void prop(int node, int tl, int tr){
	stl[node].second += lazy[node];
	if (tl != tr){
		lazy[node*2] += lazy[node];
		lazy[node*2+1] += lazy[node];
	}
	lazy[node] = 0;
}

pair<int,double> merge(int a, int b){
	if (stl[a].second > stl[b].second) return stl[a];
	return stl[b];
}

void updatel(int l, int r, double val, int node=1, int tl=0, int tr=n-1){
	if (l <= tl && tr <= r){
		lazy[node] += val;
		prop(node, tl, tr);
		return;
	}
	prop(node, tl, tr);
	int tm = (tl+tr)/2;
	if (l <= tm) updatel(l, r, val, node*2, tl, tm);
	if (tm+1 <= r) updatel(l, r, val, node*2+1, tm+1, tr);
	stl[node] = merge(node*2, node*2+1);
}

void updatelp(int pos, double val, int node=1, int tl=0, int tr=n-1){
	prop(node, tl, tr);
	if (tl == tr){
		stl[node].first = pos;
		stl[node].second += val;
		return;
	}
	int tm = (tl+tr)/2;
	if (pos <= tm) updatelp(pos, val, node*2, tl, tm);
	else updatelp(pos, val, node*2+1, tm+1, tr);
	stl[node] = merge(node*2, node*2+1);
}

int init(int N, int X[], int Y[]){
	n = N;
	stl.resize(4*N, {-1, 0});
	lazy.resize(4*N, 0);
	stm.resize(4*N, 1);
	x.resize(N);
	y.resize(N);
	for (int i=0; i<N; i++){
		y[i] = Y[i];
		x[i] = X[i];
		updatem(i, X[i]);
		updatelp(i, Y[i]);
		updatel(i, N-1, log(X[i]));
		/*for (int j=1; j<4*N; j++){
			cout << stl[j].first << " " << stl[j].second << " | ";
			if ((j+1) == pow(2, floor(log2(j+1)))) cout << "\n";
		}
		cout << "\n\n";*/
	}

	double curd = 0, bsfd = 0;
	ll cur = 1, bsf = 0;
	for (int i=0; i<N; i++){
		curd += log(x[i]);
		cur = (cur*x[i]) % 1000000007;
		if (curd+log(Y[i]) > bsfd){
			bsfd = curd+log(Y[i]);
			bsf = (cur*y[i]) % 1000000007;
		}
	}
	return bsf;

	return querym(0, stl[1].first)*y[stl[1].first] % 1000000007;
}

int updateX(int pos, int val){
	updatel(pos, n-1, log(val)-log(x[pos]));
	x[pos] = val;

	double curd = 0, bsfd = 0;
	ll cur = 1, bsf = 0;
	for (int i=0; i<n; i++){
		curd += log(x[i]);
		cur = (cur*x[i]) % 1000000007;
		if (curd+log(y[i]) > bsfd){
			bsfd = curd+log(y[i]);
			bsf = (cur*y[i]) % 1000000007;
		}
	}
	return bsf;

	return querym(0, stl[1].first)*y[stl[1].first] % 1000000007;
}

int updateY(int pos, int val){
	updatelp(pos, val-y[pos]);
	y[pos] = val;

	double curd = 0, bsfd = 0;
	ll cur = 1, bsf = 0;
	for (int i=0; i<n; i++){
		curd += log(x[i]);
		cur = (cur*x[i]) % 1000000007;
		if (curd+log(y[i]) > bsfd){
			bsfd = curd+log(y[i]);
			bsf = (cur*y[i]) % 1000000007;
		}
	}
	return bsf;

	return querym(0, stl[1].first)*y[stl[1].first] % 1000000007;
}

Compilation message

horses.cpp: In function 'int querym(int, int, int, int, int)':
horses.cpp:26:41: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
   26 |  if (l <= tl && tr <= r) return stm[node];
      |                                         ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:104:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  104 |  return bsf;
      |         ^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:123:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  123 |  return bsf;
      |         ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:142:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  142 |  return bsf;
      |         ^~~

Subtask #1
0 / 17.0

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

Subtask #2
0 / 17.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1578 ms 73044 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
0 / 23.0

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