이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int maxn = 5e5 + 20;
const int mod = 1e9 + 7;
int maxy[maxn * 4] , mulx[maxn * 4] , t[maxn * 4] , n;
int x[maxn];
void updx(int p , int val , int s = 0 , int e = n , int v = 1)
{
if(e - s < 2)
{
mulx[v] = val;
t[v] = val > 1;
return;
}
int m = (s + e) / 2;
if(p < m)
updx(p , val , s , m , 2 * v);
else
updx(p , val , m , e , 2 * v + 1);
mulx[v] = 1LL * mulx[2 * v] * mulx[2 * v + 1] % mod;
t[v] = t[2 * v] + t[2 * v + 1];
}
void updy(int p , int val , int s = 0 , int e = n , int v = 1)
{
if(e - s < 2)
{
maxy[v] = val;
return;
}
int m = (s + e) / 2;
if(p < m)
updy(p , val , s , m , 2 * v);
else
updy(p , val , m , e , 2 * v + 1);
maxy[v] = max(maxy[2 * v] , maxy[2 * v + 1]);
}
int getx(int l , int r , int s = 0 , int e = n , int v = 1)
{
if(l <= s && e <= r)
return mulx[v];
else if(r <= s || e <= l)
return 1;
int m = (s + e) / 2;
return 1LL * getx(l , r , s , m , 2 * v) * getx(l , r , m , e , 2 * v + 1) % mod;
}
int gety(int l , int r , int s = 0 , int e = n , int v = 1)
{
if(l <= s && e <= r)
return maxy[v];
if(r <= s || e <= l)
return 0;
int m = (s + e) / 2;
return max(gety(l , r , s , m , 2 * v) , gety(l , r , m , e , 2 * v + 1));
}
void ux(int p , int val)
{
x[p] = val;
updx(p , val);
}
vector<int> tmp;
void get(int k = 35 , int s = 0 , int e = n , int v = 1)
{
if(k <= 0 || !t[v])
return;
if(e - s < 2)
{
tmp.pb(s);
return;
}
int m = (s + e) / 2;
get(k , m , e , 2 * v + 1);
k -= t[2 * v + 1];
get(k , s , m , 2 * v);
}
int solve()
{
tmp.clear();
get();
if(tmp.empty())
return gety(0 , n);
reverse(tmp.begin() , tmp.end());
int m = tmp.size();
tmp.pb(n);
vector<int> y;
for(int i = 0; i < m; i++)
y.pb(gety(tmp[i] , tmp[i + 1]));
for(int i = 0; i < m; i++)
{
bool good = 1;
ll mul = 1;
for(int j = i + 1; j < m && good; j++)
{
mul = min((ll)2e9 , 1LL * mul * x[tmp[j]]);
if(y[i] <= mul * y[j])
good = 0;
}
if(good)
return 1LL * getx(0 , tmp[i] + 1) * y[i] % mod;
}
return -1;
}
int init(int N, int X[], int Y[])
{
n = N;
for(int i = 0; i < n; i++)
{
ux(i , X[i]);
updy(i , Y[i]);
}
return solve();
}
int updateX(int pos, int val)
{
ux(pos , val);
return solve();
}
int updateY(int pos, int val)
{
updy(pos , val);
return solve();
}
컴파일 시 표준 에러 (stderr) 메시지
horses.cpp: In function 'void updx(int, int, int, int, int)':
horses.cpp:31:48: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
mulx[v] = 1LL * mulx[2 * v] * mulx[2 * v + 1] % mod;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int getx(int, int, int, int, int)':
horses.cpp:61:77: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return 1LL * getx(l , r , s , m , 2 * v) * getx(l , r , m , e , 2 * v + 1) % mod;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int solve()':
horses.cpp:108:18: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
int m = tmp.size();
~~~~~~~~^~
horses.cpp:128:45: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return 1LL * getx(0 , tmp[i] + 1) * y[i] % mod;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
# | 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... |