답안 #1042012

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1042012	2024-08-02T12:12:56 Z	fv3	말 (IOI15_horses)	C++14	37 / 100	1500 ms	67808 KB

horses

#include <bits/stdc++.h>
#include "horses.h"

using namespace std;
typedef long long ll;

const ll mod = 1e9 + 7;
int N; vector<ll> X, Y;

int nt = 1;
vector<ll> st;
vector<ll> st_mod;
vector<ll> st_mx;

set<int> notOne;

int mx_index = 0;

ll get_range(int l, int r, int k, int x, int y)
{
	if (y < l || x > r) return 1;
	if (x >= l && y <= r) return st[k];
	int c = (x + y) / 2;
	return get_range(l, r, k*2, x, c) * get_range(l, r, k*2|1, c+1, y);
}

ll get_mod_range(int l, int r, int k, int x, int y)
{
	if (y < l || x > r) return 1;
	if (x >= l && y <= r) return st_mod[k];
	int c = (x + y) / 2;
	return (get_mod_range(l, r, k*2, x, c) * get_mod_range(l, r, k*2|1, c+1, y)) % mod;
}

ll get_max_range(int l, int r, int k, int x, int y)
{
	if (y < l || x > r) return 1;
	if (x >= l && y <= r) return st_mx[k];
	int c = (x + y) / 2;
	return max(get_max_range(l, r, k*2, x, c), get_max_range(l, r, k*2|1, c+1, y));	
}

int get_full_max()
{
	ll res = (X[0] * Y[0]) % mod, cnt = X[0];
	mx_index = 0;

	for (int i = 1; i < N; i++)
	{
		cnt = (cnt * X[i]) % mod;
		ll last_mult = Y[mx_index];

		ll mult_range = get_range(mx_index + 1, i, 1, 0, nt - 1); 

		if (mult_range >= last_mult || mult_range * Y[i] >= last_mult)
		{
			res = (cnt * Y[i]) % mod;
			mx_index = i;
		}
	}

	return (int)res;
}

int get_max()
{
	// Find the value of s
	// Go left 60 non-one steps
	int c = 0;
	int s = N - 1;
	while (s > 0 && c < 60)
	{
		c++;
		if (X[s] > 1)
		{
			s--;
			continue;
		}

		auto it = notOne.lower_bound(s);
		if (it == notOne.begin())
		{
			s = 0;
			break;
		}
		s = *--it;
	}


	mx_index = s;
	ll cnt = get_mod_range(0, s, 1, 0, nt - 1);
	ll res = (cnt * Y[s]) % mod;
	for (int i = s + 1; i < N; )
	{
		ll last_mult = Y[mx_index];
		ll mult_range = get_range(mx_index + 1, i, 1, 0, nt - 1); 
		if (X[i] == 1)
		{
			int r = *notOne.lower_bound(i);
			int mx_in_range = get_max_range(i, r-1, 1, 0, nt-1); 
			ll val =  Y[mx_in_range];

			if (mult_range * Y[mx_in_range] >= last_mult)
			{
				res = (cnt * Y[mx_in_range]) % mod;
				mx_index = i;
			}

			i = r;
			continue;
		}

		cnt = (cnt * X[i]) % mod;
		if (mult_range >= last_mult || mult_range * Y[i] >= last_mult)
		{
			res = (cnt * Y[i]) % mod;
			mx_index = i;
		}
		i++;
	}

	return (int)res;
}

int init(int n, int x[], int y[]) 
{
	N = n;
	X.resize(N);
	Y.resize(N);

	for (int i = 0; i < N; i++)
	{
		X[i] = x[i];
		Y[i] = y[i];

		if (Y[i] > 1)
			notOne.insert(i);
	}

	while (nt < N) nt <<= 1;
	st = st_mx = st_mod = vector<ll>(2 * nt, 1);
	for (int i = 0; i < N; i++)
	{
		st[nt + i] = X[i];
		st_mod[nt + i] = X[i];
		st_mx[nt + i] = Y[i];
	}
	for (int i = nt-1; i >= 1; i--)
	{
		st[i] = st[i*2] * st[i*2|1];
		st_mod[i] = (st_mod[i*2] * st_mod[i*2|1]) % mod;
		st_mx[i] = max(st_mx[i*2], st_mx[i*2|1]);
	}

	return get_full_max();
}

int updateX(int pos, int val) 
{
	if (X[pos] > 1)
		notOne.erase(pos);

	X[pos] = val;
	if (val > 1)
		notOne.insert(pos);
	pos += nt;
	st[pos] = val;
	st_mod[pos] = val;

	for (pos /= 2; pos >= 1; pos /= 2)
	{
		st[pos] = st[pos*2] * st[pos*2|1];
		st_mod[pos] = (st_mod[pos*2] * st_mod[pos*2|1]) % mod;
	}

	return get_max();
}

int updateY(int pos, int val) 
{
	Y[pos] = val;

	pos += nt;
	st_mx[pos] = val;

	for (pos /= 2; pos >= 1; pos /= 2)
	{
		st_mx[pos] = max(st_mx[pos*2], st_mx[pos*2|1]);
	}

	return get_max();
}

Compilation message

horses.cpp: In function 'int get_max()':
horses.cpp:100:35: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  100 |    int mx_in_range = get_max_range(i, r-1, 1, 0, nt-1);
      |                      ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
horses.cpp:101:7: warning: unused variable 'val' [-Wunused-variable]
  101 |    ll val =  Y[mx_in_range];
      |       ^~~

Subtask #1
17.0 / 17.0

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	440 KB	Output is correct
6	Correct	348 KB	Output is correct
7	Correct	444 KB	Output is correct
8	Correct	348 KB	Output is correct
9	Correct	348 KB	Output is correct
10	Correct	348 KB	Output is correct
11	Correct	436 KB	Output is correct
12	Correct	348 KB	Output is correct
13	Correct	436 KB	Output is correct
14	Correct	348 KB	Output is correct
15	Correct	348 KB	Output is correct
16	Correct	348 KB	Output is correct
17	Correct	348 KB	Output is correct
18	Correct	348 KB	Output is correct
19	Correct	444 KB	Output is correct
20	Correct	348 KB	Output is correct

Subtask #2
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	368 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	436 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	1 ms	344 KB	Output is correct
21	Execution timed out	1533 ms	600 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	438 ms	39888 KB	Output is correct
2	Correct	584 ms	67808 KB	Output is correct
3	Correct	469 ms	42064 KB	Output is correct
4	Correct	590 ms	65360 KB	Output is correct

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	440 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Execution timed out	1598 ms	348 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

Subtask #5
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	436 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	436 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	436 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	344 KB	Output is correct
20	Correct	0 ms	344 KB	Output is correct
21	Execution timed out	1595 ms	604 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

답안 #1042012

Compilation message

Subtask #1 17.0 / 17.0

Subtask #2 0 / 17.0

Subtask #3 20.0 / 20.0

Subtask #4 0 / 23.0

Subtask #5 0 / 23.0

Subtask #1
17.0 / 17.0

Subtask #2
0 / 17.0

Subtask #3
20.0 / 20.0

Subtask #4
0 / 23.0

Subtask #5
0 / 23.0