oj.uz

Submission #767629

# Submission time Handle Problem Language Result Execution time Memory
767629 2023-06-26T23:23:43 Z ThegeekKnight16 Horses (IOI15_horses) C++17
0 / 100
 80 ms 75560 KB 
#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
typedef long long ll;
const int MAXN = 5e5 + 10;
const ll MOD = 1e9 + 7;
ll X[MAXN], Y[MAXN];

inline ll mult(ll a, ll b) {return (a * b) % MOD;}
ll exp(ll x, ll b)
{
	if (b == 0) return 1LL;
	if (b % 2) return mult(x, exp(x, b-1));
	else return exp(mult(x, x), b/2);
}

int N;
struct node
{
	ll mx, y;
	bool bigPref;
	ll val;

	node (ll MX = 0, ll YY = 0, bool BIG = false) : mx(MX), y(YY), bigPref(BIG) {val = mult(mx, y);}

	node operator+(node outro)
	{
		node resp;
		/*
			Quero ver se outro.mx * outro.y >= y, mas pode dar overflow, ent
			testo tres casos:
				se outro.y >= y, ja eh maior
				se o outro tem um prefixo grande(tive que tirar mod), tbm eh maior
				//Agr, tenho certeza que mx <= 1e9 e y <= 1e9, ent posso testar a multiplicao
				se (outro.mx * outro.y) >= y, eh maior
				senao o maior sera o proprio y.
		*/
		if (y <= outro.y) resp = node(mult(mx, outro.mx), outro.y, ((mx * outro.mx >= MOD) || bigPref || outro.bigPref));
		else if (outro.bigPref) resp = node(mult(mx, outro.mx), outro.y, true);
		else if ((outro.mx * outro.y) >= y) resp = node(mult(mx, outro.mx), outro.y, ((mx * outro.mx >= MOD) || bigPref || outro.bigPref));
		else resp = *this;
		return resp;
	}
} seg[4*MAXN];

void build(int pos, int ini, int fim)
{
	if (ini == fim)
	{
		seg[pos] = node(X[ini], Y[ini]);
		return;
	}
	int m = (ini + fim) >> 1;
	int e = 2*pos; int d = 2*pos + 1;
	build(e, ini,  m );
	build(d, m+1, fim);
	seg[pos] = seg[e] + seg[d];
}

void segUpdate(int pos, int ini, int fim, int id)
{
	if (id < ini || id > fim) return;
	if (ini == fim)
	{
		seg[pos] = node(X[ini], Y[ini]);
		return;
	}
	int m = (ini + fim) >> 1;
	int e = 2*pos; int d = 2*pos + 1;
	segUpdate(e, ini,  m , id);
	segUpdate(d, m+1, fim, id);
	seg[pos] = seg[e] + seg[d];
}


int init(int _N, int _X[], int _Y[])
{
	N = _N;
	for (int i = 1; i <= N; i++) X[i] = _X[i-1], Y[i] = _Y[i-1];
	build(1, 1, N);

	return seg[1].val;
}

int updateX(int id, int _val)
{
	++id;
	X[id] = _val;
	segUpdate(1, 1, N, id);
	return seg[1].val;
}

int updateY(int id, int _val)
{
	++id;
	Y[id] = _val;
	segUpdate(1, 1, N, id);
	return seg[1].val;
}

Compilation message

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:82:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   82 |  return seg[1].val;
      |         ~~~~~~~^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:90:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   90 |  return seg[1].val;
      |         ~~~~~~~^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:98:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   98 |  return seg[1].val;
      |         ~~~~~~~^~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 62932 KB Output is correct
2 Incorrect 25 ms 62828 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 62852 KB Output is correct
2 Incorrect 25 ms 62836 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 80 ms 75560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 62932 KB Output is correct
2 Incorrect 26 ms 62908 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 62848 KB Output is correct
2 Incorrect 27 ms 62872 KB Output isn't correct
3 Halted 0 ms 0 KB -