제출 #784820

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
784820		zsombor	말 (IOI15_horses)	C++17	100 / 100	620 ms	85476 KiB

horses

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include "horses.h"
using namespace std;
using ll = long long;

struct node {
	int L, M, R;
	ll prod, mx;
};

int n;
ll MOD = 1e9 + 7;
vector <ll> x(5e5 + 1, 1);
vector <ll> y(5e5, 0);
vector <node> sgt(11e5);
vector <int> Lft(5e5 + 1, 0);
set <int> s;

void build_sgt(int a, int l, int r) {
	sgt[a].L = l;
	sgt[a].M = (l + r) / 2;
	sgt[a].R = r;
	if (r - l == 1) {
		sgt[a].prod = x[l];
		sgt[a].mx = y[l];
		return;
	}
	build_sgt(2 * a, l, sgt[a].M);
	build_sgt(2 * a + 1, sgt[a].M, r);
	sgt[a].prod = (sgt[2 * a].prod * sgt[2 * a + 1].prod) % MOD;
	sgt[a].mx = max(sgt[2 * a].mx, sgt[2 * a + 1].mx);
}

void update(int a, int i) {
	if (sgt[a].R - sgt[a].L == 1) {
		sgt[a].prod = x[i];
		sgt[a].mx = y[i];
		return;
	}
	if (i < sgt[a].M) update(2 * a, i);
	else update(2 * a + 1, i);
	sgt[a].prod = (sgt[2 * a].prod * sgt[2 * a + 1].prod) % MOD;
	sgt[a].mx = max(sgt[2 * a].mx, sgt[2 * a + 1].mx);
}

ll query_prod(int a, int l, int r) {
	if (r <= sgt[a].L || sgt[a].R <= l) return 1;
	if (l <= sgt[a].L && sgt[a].R <= r) return sgt[a].prod;
	return (query_prod(2 * a, l, r) * query_prod(2 * a + 1, l, r)) % MOD;
}

ll query_mx(int a, int l, int r) {
	if (r <= sgt[a].L || sgt[a].R <= l) return 1;
	if (l <= sgt[a].L && sgt[a].R <= r) return sgt[a].mx;
	return max(query_mx(2 * a, l, r), query_mx(2 * a + 1, l, r));
}

ll get_ans() {
	ll MX = 0, I = -1;
	for (int i = n; i > 0; i = Lft[i]) {
		MX *= x[i];
		if (MX > MOD) break;
		ll Y = query_mx(1, Lft[i], i);
		if (Y > MX) { MX = Y; I = i; }
	}
	return (query_prod(1, 0, Lft[I] + 1) * query_mx(1, Lft[I], I)) % MOD;
}

int init(int N, int X[], int Y[]) {
	n = N;
	for (int i = 0; i < n; i++) { x[i] = X[i]; y[i] = Y[i]; }
	build_sgt(1, 0, n);
	for (int i = 1; i <= n; i++) {
		Lft[i] = x[i - 1] == 1 ? Lft[i - 1] : i - 1;
		if (x[i] > 1) s.insert(i);
	}
	s.insert(n);
	return get_ans();
}

int updateX(int pos, int val) {
	if (x[pos] == 1) {
		int r = *s.upper_bound(pos);
		Lft[pos] = Lft[r];
		Lft[r] = pos;
		s.insert(pos);
	}
	if (val == 1) {
		int r = *s.upper_bound(pos);
		Lft[r] = Lft[pos];
		s.erase(pos);
	}
	x[pos] = val;
	update(1, pos);
	return get_ans();
}

int updateY(int pos, int val) {
	y[pos] = val;
	update(1, pos);
	return get_ans();
}

컴파일 시 표준 에러 (stderr) 메시지

horses.cpp: In function 'll get_ans()':
horses.cpp:69:61: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   69 |  return (query_prod(1, 0, Lft[I] + 1) * query_mx(1, Lft[I], I)) % MOD;
      |                                                             ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:81:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   81 |  return get_ans();
      |         ~~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:98:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   98 |  return get_ans();
      |         ~~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:104:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  104 |  return get_ans();
      |         ~~~~~~~^~

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 23 / 23
• Subtask 5: 23 / 23