제출 #288477

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
288477		amoo_safar	말 (IOI15_horses)	C++17	100 / 100	935 ms	49144 KiB

horses

#include "horses.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 5e5 + 10;
const int MX = 1e9 + 1;
const int Mod = 1e9 + 7;

ll mul(ll a, ll b){
	return (a * b) % Mod;
}
ll bin_pow(ll b, ll p){
	ll res = 1;
	for(ll j = 1, pw = b; j <= p; j <<= 1, pw = mul(pw, pw))
		if(j & p)
			res = mul(res, pw);
	return res;
}
ll inv(ll x){
	return bin_pow(x, Mod - 2);
}


int n;
set<int> Big;
ll dp[N];
ll X[N], Y[N];

ll fen[N];
void Add(ll idx, ll x){
	idx += 2;
	for(; idx < N; idx += (idx & (-idx)))
		fen[idx] = mul(fen[idx], x);
}
ll Get(ll idx){
	if(idx < 0) return 1;

	idx += 2;
	ll res = 1;
	for(; idx; idx -= (idx & (-idx)))
		res = mul(res, fen[idx]);
	return res;
}

ll seg[N << 2];
void Change(int id, int idx, ll x, int L = 0, int R = N){
	if(L + 1 == R){
		seg[id] = x;
		return ;
	}
	int mid = (L + R) >> 1;
	if(idx < mid)
		Change(id << 1, idx, x, L, mid);
	else 
		Change(id << 1 | 1, idx, x, mid, R);
	seg[id] = max(seg[id << 1], seg[id << 1 | 1]);
}
ll Max(int id, int l, int r, int L = 0, int R = N){
	if(r <= L || R <= l) return 0;
	if(l <= L && R <= r) return seg[id];
	int mid = (L + R) >> 1;
	return max(Max(id << 1, l, r, L, mid), Max(id << 1 | 1, l, r, mid, R));
}


ll Calc(){
	dp[n] = 0;
	Big.insert(0);
	int pos, la = n;
	for(auto it = Big.rbegin(); it != Big.rend(); it ++){
		pos = *it;
	//for(int pos = n - 1; pos >= 0; pos --){	
		dp[pos] = X[pos] * max(Max(1, pos, la), dp[la]);
		//dp[pos] = X[pos] * max(Y[pos], dp[la]);
		
		//assert((X[pos] > 1 || pos == 0));
		if(dp[pos] >= MX)
			return mul(dp[pos] % Mod, Get(pos - 1));
		
		la = pos;
	}
	return dp[0] % Mod;
}

int init(int _n, int _X[], int _Y[]) {

	fill(fen, fen + N, 1);
	Big.clear();

	n = _n;
	for(int i = 0; i < n; i++){
		X[i] = _X[i]; Y[i] = _Y[i];
		Change(1, i, Y[i]);
		Add(i, X[i]);
		if(X[i] > 1) Big.insert(i);
	}
	return Calc();
}

int updateX(int pos, int val) {	
	Big.erase(pos);
	Add(pos, mul(inv(X[pos]), val) );
	X[pos] = val;
	if(val > 1)
		Big.insert(pos);
	return Calc();
}

int updateY(int pos, int val) {
	Y[pos] = val;
	Change(1, pos, val);
	return Calc();
}

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

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:101:13: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  101 |  return Calc();
      |         ~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:110:13: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  110 |  return Calc();
      |         ~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:116:13: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  116 |  return Calc();
      |         ~~~~^~

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