oj.uz

Submission #1000229

# Submission time Handle Problem Language Result Execution time Memory
1000229 2024-06-17T06:47:55 Z jer033 Horses (IOI15_horses) C++17
0 / 100
 66 ms 16688 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]);
	}
}

int rangequery(int indexa, int indexb)
{
	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()
{
	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, 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));
		}
	}
}

ll solve()
{
	int m = candidates.size();
	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]]);
			currmul = 1;
			bes = mybes[i];
		}
		else
		{
			currmul = boundmul(currmul, x[candidates[i]]);
		}
	}
	return 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;
	return solve();
}

int updateY(int pos, int val) {
	y[pos] = val;
	return solve();
}

Compilation message

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

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2472 KB Output is correct
4 Correct 2 ms 2488 KB Output is correct
5 Runtime error 3 ms 4700 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Runtime error 5 ms 4536 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Runtime error 3 ms 4544 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Runtime error 3 ms 4548 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -