oj.uz

Submission #1000333

# Submission time Handle Problem Language Result Execution time Memory
1000333 2024-06-17T09:07:28 Z jer033 Horses (IOI15_horses) C++17
17 / 100
 226 ms 22768 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(bool first)
{
	if (first)
	{
		c = 1;
		for (int i=0; i<n; i++)
		{
			if (x[i]>1)
			{
				nonone.push(i);
				c = regmul(c, x[i]);
			}
		}
	}
	else
	{
		mybes.clear();
		int m = candidates.size();
		for (int i=0; i<m; i++)
		{
			c = regmul(c, candidates[i]);
		}
		candidates.clear();
	}
	int j = 0;
	while ((j<30) and (not nonone.empty()))
	{
		int q = nonone.top();
		if (x[q]>1)
		{
			candidates.push_back(nonone.top());
			c = modinv(c, x[nonone.top()]);
			j++;
		}
		nonone.pop();
	}
	//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]]);
		}
	}
	ll doubans = regmul(c, regmul(safe, bes));
	return modinv(doubans, 2);
}
 
int init(int N, int X[], int Y[]) {
	x.push_back(2);
	y.push_back(1);
	for (int i=0; i<N; i++)
	{
		x.push_back(X[i]);
		y.push_back(Y[i]);
	}
	n=N+1;
	setupsegtree();
    initpq(1);
	return solve();
}
 
int updateX(int pos, int val) {	
	pos++;
	ll oldval = x[pos];
	x[pos] = val;
	int m = candidates.size();
	//Update the ff:
	//pq nonone
	//vector candidates
	//vector mybes
	//ll c

	//Take into account:
	//Is pos >= candidates[0] ?
	//Is val 1?
	//Is candidates full?
	if (val==1)
	{
		nonone.push(pos);
	}
	c = regmul(modinv(c, oldval), val);

	initpq(0);

	return solve();
}
 
int updateY(int pos, int val) {
	pos++;
	y[pos] = val;
	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 'void initpq(bool)':
horses.cpp:114:26: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  114 |   int m = candidates.size();
      |           ~~~~~~~~~~~~~~~^~
horses.cpp: In function 'll solve()':
horses.cpp:156:25: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  156 |  int m = candidates.size();
      |          ~~~~~~~~~~~~~~~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:191:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  191 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:198:25: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  198 |  int m = candidates.size();
      |          ~~~~~~~~~~~~~~~^~
horses.cpp:217:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  217 |  return solve();
      |         ~~~~~^~
horses.cpp:198:6: warning: unused variable 'm' [-Wunused-variable]
  198 |  int m = candidates.size();
      |      ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:224:25: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  224 |  int j = candidates.size();
      |          ~~~~~~~~~~~~~~~^~
horses.cpp:239:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  239 |  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 2 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 2 ms 2652 KB Output is correct
6 Correct 2 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 2496 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 2 ms 2652 KB Output is correct
14 Correct 1 ms 2500 KB Output is correct
15 Correct 2 ms 2648 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 2648 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 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2544 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 2 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 2904 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 2648 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 2492 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 1 ms 2648 KB Output is correct
21 Incorrect 1 ms 2652 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 17712 KB Output is correct
2 Incorrect 226 ms 22768 KB Output isn't correct
3 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 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 2496 KB Output is correct
17 Correct 1 ms 2496 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 2648 KB Output is correct
21 Incorrect 2 ms 2652 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 2 ms 2648 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 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 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
21 Incorrect 1 ms 2652 KB Output isn't correct
22 Halted 0 ms 0 KB -