제출 #387393

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
387393		alishahali1382	Horses (IOI15_horses)	C++14	100 / 100	353 ms	45420 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define debug2(x, y) {cerr<<#x<<", "<<#y<<" = "<<x<<", "<<y<<"\n";}
#define pb push_back
#define all(x) x.begin(), x.end()

const int mod=1000000007;
const int MAXN=500010, LOG=20;

int n, m, k;
ll X[MAXN], Y[MAXN], zarbx=1;
int seg[MAXN<<1];
set<int> st;

void Set(int pos, int val){
	for (seg[pos+=n]=val; pos>1; pos>>=1) seg[pos>>1]=max(seg[pos], seg[pos^1]);
}
int Get(int l, int r){
	int res=0;
	for (l+=n, r+=n; l<r; l>>=1, r>>=1){
		if (l&1) res=max(res, seg[l++]);
		if (r&1) res=max(res, seg[--r]);
	}
	return res;
}
ll powmod(ll a, ll b){
	ll res=1;
	for (; b; b>>=1, a=a*a%mod) if (b&1) res=res*a%mod;
	return res;
}
int Solve(){
	auto it=st.end();
	ll ansx=1, ansy=0, xx=1;
	while (it!=st.begin()){
		it--;
		int i=*it, y=Get(i, n);
		// debug2(i, y)
		if (xx*ansy<ansx*y){
			ansx=xx;
			ansy=y;
		}
		xx*=X[i];
		if (xx>=1000000000) break ;
	}
	return zarbx*powmod(ansx, mod-2)%mod*ansy%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];
		if (X[i]>1 || !i){
			zarbx=zarbx*X[i]%mod;
			st.insert(i);
		}
		Set(i, Y[i]);
	}
	return Solve();
}
int updateX(int pos, int val) {	
	st.erase(pos);
	zarbx=zarbx*powmod(X[pos], mod-2)%mod;
	X[pos]=val;
	if (X[pos]>1 || !pos){
		zarbx=zarbx*X[pos]%mod;
		st.insert(pos);
	}
	return Solve();
}
int updateY(int pos, int val) {
	Y[pos]=val;
	Set(pos, val);
	return Solve();
}

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

horses.cpp: In function 'int Solve()':
horses.cpp:51:43: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   51 |  return zarbx*powmod(ansx, mod-2)%mod*ansy%mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:63:13: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   63 |   Set(i, Y[i]);
      |          ~~~^

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