oj.uz

Submission #1000259

# Submission time Handle Problem Language Result Execution time Memory
1000259 2024-06-17T07:28:02 Z jer033 Horses (IOI15_horses) C++17
17 / 100
 1500 ms 17344 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)
{
	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 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(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:143:25: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  143 |  int m = candidates.size();
      |          ~~~~~~~~~~~~~~~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:175:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  175 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:182:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  182 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:206:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  206 |  return solve();
      |         ~~~~~^~

Subtask #1
17.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 2648 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2500 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 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 Correct 1 ms 2652 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 2652 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 1 ms 2652 KB Output is correct

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 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 1 ms 2652 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2648 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 2648 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 1 ms 2652 KB Output is correct
21 Correct 3 ms 2648 KB Output is correct
22 Correct 7 ms 2676 KB Output is correct
23 Correct 361 ms 2652 KB Output is correct
24 Correct 356 ms 2904 KB Output is correct
25 Correct 381 ms 2708 KB Output is correct
26 Correct 378 ms 2652 KB Output is correct
27 Incorrect 357 ms 2896 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1565 ms 17344 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 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2492 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 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 Correct 1 ms 2652 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 2500 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 1 ms 2652 KB Output is correct
21 Correct 3 ms 2652 KB Output is correct
22 Correct 7 ms 2652 KB Output is correct
23 Correct 354 ms 2652 KB Output is correct
24 Correct 357 ms 2676 KB Output is correct
25 Correct 379 ms 2652 KB Output is correct
26 Correct 382 ms 2652 KB Output is correct
27 Incorrect 354 ms 2648 KB Output isn't correct
28 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 2492 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2552 KB Output is correct
7 Correct 1 ms 2648 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 2648 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 2652 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 1 ms 2464 KB Output is correct
21 Correct 3 ms 2652 KB Output is correct
22 Correct 6 ms 2668 KB Output is correct
23 Correct 357 ms 2648 KB Output is correct
24 Correct 361 ms 2648 KB Output is correct
25 Correct 376 ms 2648 KB Output is correct
26 Correct 373 ms 2652 KB Output is correct
27 Incorrect 341 ms 2648 KB Output isn't correct
28 Halted 0 ms 0 KB -