이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "horses.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef pair<int,int> ii;
const ll mod = (ll) 1e9+7;
struct segTreeMul{
ll node[2000005];
segTreeMul(){
for(int i=1;i<=2000000;i++) node[i] = 1;
}
void upd(int id,int l,int r,int pos,int val){
if (r < pos || pos < l) return;
if (l == r){
node[id] = val;
return;
}
upd(2*id,l,(l+r)/2,pos,val);
upd(2*id+1,(l+r)/2+1,r,pos,val);
node[id] = node[2*id] * node[2*id+1] % mod;
}
ll get(int id,int l,int r,int u,int v){
if (r < u || v < l) return 1;
if (u <= l && r <= v) return node[id];
return get(2*id, l, (l+r)/2, u, v) * get(2*id+1, (l+r)/2+1, r, u, v) % mod;
}
};
struct segTreeMax{
ll node[2000005];
segTreeMax(){
for(int i=1;i<=2000000;i++) node[i] = -1;
}
void upd(int id,int l,int r,int pos,int val){
if (r < pos || pos < l) return;
if (l == r){
node[id] = val;
return;
}
upd(2*id,l,(l+r)/2,pos,val);
upd(2*id+1,(l+r)/2+1,r,pos,val);
node[id] = max(node[2*id], node[2*id+1]);
}
ll get(int id,int l,int r,int u,int v){
if (r < u || v < l) return 1;
if (u <= l && r <= v) return node[id];
return max(get(2*id, l, (l+r)/2, u, v), get(2*id+1, (l+r)/2+1, r, u, v));
}
};
segTreeMul segMul;
segTreeMax segMax;
int n;
int growthNum[500005];
set <int> notOneLst;
ll getBest(){
if (notOneLst.empty())
return segMax.get(1,1,n,1,n);
vector <int> importants;
importants.push_back(n+1);
set<int>::iterator it = notOneLst.end();
ll prod = 1;
while(it != notOneLst.begin() && prod < mod){
it --;
importants.push_back(*it);
prod *= growthNum[*it];
}
if (prod < mod && importants[0] != 1)
importants.push_back(1);
//reverse(importants.begin(), importants.end());
double bestRatio = 0;
int bestPos = -1;
ll denominator = 1;
for(int i=1;i<importants.size();i++){
ll ma = segMax.get(1,1,n,importants[i], importants[i-1]-1);
if (1.0 * ma / denominator > bestRatio){
bestPos = i;
bestRatio = 1.0 * ma / denominator;
}
denominator *= growthNum[importants[i]];
}
return segMul.get(1,1,n,1,importants[bestPos]) * segMax.get(1,1,n,importants[bestPos], importants[bestPos-1]-1) % mod;
}
int init(int N, int X[], int Y[]) {
n = N;
for(int i=0;i<n;i++){
growthNum[i+1] = X[i];
if (growthNum[i+1] > 1)
notOneLst.insert(i+1);
segMul.upd(1,1,n,i+1,X[i]);
}
for(int i=0;i<n;i++){
segMax.upd(1,1,n,i+1,Y[i]);
}
return getBest();
}
int updateX(int pos, int val) {
pos++;
if (growthNum[pos] > 1) notOneLst.erase(pos);
growthNum[pos] = val;
segMul.upd(1,1,n,pos,val);
if (growthNum[pos] > 1) notOneLst.insert(pos);
return getBest();
}
int updateY(int pos, int val) {
pos++;
segMax.upd(1,1,n,pos,val);
return getBest();
}
컴파일 시 표준 에러 (stderr) 메시지
horses.cpp: In function 'long long int getBest()':
horses.cpp:78:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<importants.size();i++){
~^~~~~~~~~~~~~~~~~~
horses.cpp:80:19: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
if (1.0 * ma / denominator > bestRatio){
^~
horses.cpp:80:24: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
if (1.0 * ma / denominator > bestRatio){
^~~~~~~~~~~
horses.cpp:82:31: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
bestRatio = 1.0 * ma / denominator;
^~
horses.cpp:82:36: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
bestRatio = 1.0 * ma / denominator;
^~~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:100:16: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return getBest();
~~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:109:16: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return getBest();
~~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:115:16: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return getBest();
~~~~~~~^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |