oj.uz

Submission #1000279

# Submission time Handle Problem Language Result Execution time Memory
1000279 2024-06-17T07:57:25 Z jer033 Horses (IOI15_horses) C++17
0 / 100
 1500 ms 15296 KB 
#include "horses.h"
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
const ll MOD = 1'000'000'007;
const ll INF = 1'000'000'006;
const int pus = 524288;

ll regmul(ll a, ll b)
{
	return (a*b)%MOD;
}

ll boundmul(ll a, ll b)
{
	return min(INF, a*b);
}

ll modpow(ll x, int y)
{
	if (y==0)
		return 1;
	if (y==1)
		return x;
	ll z = modpow(x, y/2);
	z = regmul(z, z);
	if (y%2)
		z = regmul(z, x);
	return z;
}

ll modinv(ll a, ll b)
{
	return regmul(a, modpow(b, MOD-2));
}

vector<int> x;
vector<int> y;
int n;

int segtree[1048576];

void setupsegtree()
{
	for (int i=0; i<n; i++)
	{
		segtree[pus+i] = y[i];
	}
	for (int i=pus-1; i>=1; i--)
	{
		segtree[i] = max(segtree[2*i], segtree[2*i+1]);
	}
}

void updatesegtree(int index, int newval)
{
	index = pus+index;
	segtree[index] = newval;
	while (index!=0)
	{
		index = index/2;
		segtree[index] = max(segtree[2*index], segtree[2*index+1]);
	}
	segtree[0] = 0;
}

int rangequery(int indexa, int indexb)
{
	if (indexa>indexb)
		return -1;
	indexa = indexa+pus;
	indexb = indexb+pus;
	int ans = -1;
	while ((indexb-indexa)>=5)
	{
		if ((indexa%2)==1)
		{
			ans = max(segtree[indexa], ans);
			indexa++;
		}
		if ((indexb%2)==0)
		{
			ans = max(segtree[indexb], ans);
			indexb--;
		}
		indexa = indexa/2;
		indexb = indexb/2;
	}
	for (int i=indexa; i<=indexb; i++)
		ans = max(segtree[i], ans);
	return ans;
}

priority_queue<int> nonone;
vector<int> candidates;
vector<int> mybes;
ll c;

void initpq()
{
	while (not nonone.empty())
		nonone.pop();
	candidates.clear();
	mybes.clear();
	c = 1;
	for (int i=0; i<n; i++)
	{
		if (x[i]>1)
		{
			nonone.push(i);
			c = regmul(c, x[i]);
		}
	}
	int j = 0;
	while ((j<30) and (not nonone.empty()))
	{
		candidates.push_back(nonone.top());
		c = modinv(c, x[nonone.top()]);
		nonone.pop();
		j++;
	}
	//reverse the list
	vector<int> newcandidates;
	for (int i=j-1; i>=0; i--)
	{
		newcandidates.push_back(candidates[i]);
	}
	candidates = newcandidates;

	for (int i=0; i<j; i++)
	{
		if (i!=(j-1))
		{
			mybes.push_back(rangequery(candidates[i], candidates[i+1]-1));
		}
		else
		{
			mybes.push_back(rangequery(candidates[i], n-1));
		}
	}
}

ll solve()
{
	int m = candidates.size();
	if (m==0)
		return rangequery(0, n-1);
	ll isans = 1;
	ll safe = x[candidates[0]];
	ll bes = mybes[0];
	ll currmul = 1;
	for (int i=1; i<m; i++)
	{
		if (boundmul(boundmul(currmul, x[candidates[i]]), mybes[i])>=bes)
		{
			safe = regmul(safe, currmul);
			safe = regmul(safe, x[candidates[i]]);
			isans = boundmul(safe, currmul);
			isans = boundmul(safe, x[candidates[i]]);
			currmul = 1;
			bes = mybes[i];
		}
		else
		{
			currmul = boundmul(currmul, x[candidates[i]]);
		}
	}
	isans = boundmul(isans, bes);
	isans = boundmul(isans, c);
	ll secans = rangequery(0, candidates[0]-1);
	if (secans>isans)
		return secans;
	return regmul(c, regmul(safe, bes));
}

int init(int N, int X[], int Y[]) {
	for (int i=0; i<N; i++)
	{
		x.push_back(X[i]);
		y.push_back(Y[i]);
	}
	n=N;
	setupsegtree();
    initpq();
	return solve();
}

int updateX(int pos, int val) {	
	x[pos] = val;
	setupsegtree();
	initpq();
	return solve();
}

int updateY(int pos, int val) {
	y[pos] = val;
	setupsegtree();
	initpq();
	/*
	updatesegtree(pos, val);
	int j = candidates.size();
	for (int i=0; i<j; i++)
	{
		if (i!=(j-1))
		{
			if ((candidates[i]<=pos) and (pos<candidates[i+1]))
				mybes[i] = rangequery(candidates[i], candidates[i+1]-1);
		}
		else
		{
			if (candidates[i]<=pos)
				mybes[i] = rangequery(candidates[i], n-1);
		}
	}*/

	return solve();
}

Compilation message

horses.cpp: In function 'll solve()':
horses.cpp:145:25: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  145 |  int m = candidates.size();
      |          ~~~~~~~~~~~~~~~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:185:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  185 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:192:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  192 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:216:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  216 |  return solve();
      |         ~~~~~^~

Subtask #1
0 / 17.0

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

Subtask #2
0 / 17.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1568 ms 15296 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 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Incorrect 1 ms 2652 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

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