이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "horses.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define x first
#define y second
#define MAXN 500015
#define mod 1000000007
using namespace std;
int dx[MAXN],dy[MAXN],n;
ll fast_pow(ll a,ll b){
ll ans=1;
while (b){
if (b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
struct segtree{
ll pos[4*MAXN],val[4*MAXN],val_x[4*MAXN],fac[4*MAXN];
pii remain[4*MAXN];
ll get_val(ll a=1,ll b=1,ll c=1,ll d=1){
vector<ll>vt={a,b,c,d};
ll ans=1;
for (ll i:vt){
ans=ans*i;
if (ans>1e9) return 1e9+2;
}
return ans;
}
void pull(int i){
fac[i]=fac[2*i]*fac[2*i+1]%mod;
if (get_val(remain[2*i].y,remain[2*i+1].x,val_x[2*i+1],val[2*i+1])>val[2*i]){
pos[i]=pos[2*i+1]; val[i]=val[2*i+1]; remain[i].y=remain[2*i+1].y; val_x[i]=val_x[2*i+1];
remain[i].x=get_val(remain[2*i].x,remain[2*i].y,val_x[2*i],remain[2*i+1].x);
}
else {
pos[i]=pos[2*i]; val[i]=val[2*i]; remain[i].x=remain[2*i].x; val_x[i]=val_x[2*i];
remain[i].y=get_val(remain[2*i].y,remain[2*i+1].x,remain[2*i+1].y,val_x[2*i+1]);
}
}
void build(int l,int r,int i){
if (l==r){
remain[i]={1,1};
pos[i]=l; val[i]=dy[l]; fac[i]=dx[l]; val_x[i]=dx[l];
return;
}
int mid=(l+r)>>1;
build(l,mid,2*i);
build(mid+1,r,2*i+1);
pull(i);
}
void modify_Y(int l,int r,int i,int p,ll c){
if (l==r){
val[i]=val[i]*c%mod;
return;
}
int mid=(l+r)>>1;
if (p<=mid) modify_Y(l,mid,2*i,p,c);
else modify_Y(mid+1,r,2*i+1,p,c);
pull(i);
}
void modify_X(int l,int r,int i,int p,ll c){
if (l==r){
fac[i]=fac[i]*c%mod;
val_x[i]=val_x[i]*c%mod;
return;
}
int mid=(l+r)>>1;
if (p<=mid) modify_X(l,mid,2*i,p,c);
else modify_X(mid+1,r,2*i+1,p,c);
pull(i);
}
ll query(int l,int r,int i,int ql,int qr){
if (ql<=l&&qr>=r) return fac[i];
int mid=(l+r)>>1;
if (qr<=mid) return query(l,mid,2*i,ql,qr);
else if (ql>mid) return query(mid+1,r,2*i+1,ql,qr);
else return query(l,mid,2*i,ql,qr)*query(mid+1,r,2*i+1,ql,qr)%mod;
}
void debug(int l,int r,int i){
cout<<l<<" ~ "<<r<<" : "<<fac[i]<<" best "<<pos[i]<<","<<val[i]<<","<<val_x[i]<<" remain : "<<remain[i].x<<' '<<remain[i].y<<'\n';
if (l==r) return;
int mid=(l+r)>>1;
debug(l,mid,2*i);
debug(mid+1,r,2*i+1);
}
}seg;
int init(int N, int X[], int Y[]) {
n=N;
for (int i=1;i<=n;i++){
dx[i]=X[i-1]; dy[i]=Y[i-1];
}
seg.build(1,n,1);
ll best=seg.pos[1];
ll ans=seg.query(1,n,1,1,best)*dy[best]%mod;
return ans;
}
int updateX(int pos, int val) {
pos++;
ll inv=fast_pow(dx[pos],mod-2);
dx[pos]=val;
seg.modify_X(1,n,1,pos,inv);
seg.modify_X(1,n,1,pos,val);
ll best=seg.pos[1];
ll ans=seg.query(1,n,1,1,best)*dy[best]%mod;
//cout<<"modify_X "<<best<<" "<<ans<<'\n';
//seg.debug(1,n,1);
return ans;
}
int updateY(int pos, int val) {
pos++;
ll inv=fast_pow(dy[pos],mod-2);
dy[pos]=val;
seg.modify_Y(1,n,1,pos,inv);
seg.modify_Y(1,n,1,pos,val);
ll best=seg.pos[1];
ll ans=seg.query(1,n,1,1,best)*dy[best]%mod;
//cout<<"modify_Y "<<best<<" "<<ans<<'\n';
//seg.debug(1,n,1);
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
horses.cpp: In member function 'long long int segtree::get_val(long long int, long long int, long long int, long long int)':
horses.cpp:29:8: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
29 | if (ans>1e9) return 1e9+2;
| ^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:98:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
98 | ll ans=seg.query(1,n,1,1,best)*dy[best]%mod;
| ^~~~
horses.cpp:99:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
99 | return ans;
| ^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:109:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
109 | ll ans=seg.query(1,n,1,1,best)*dy[best]%mod;
| ^~~~
horses.cpp:112:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
112 | return ans;
| ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:122:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
122 | ll ans=seg.query(1,n,1,1,best)*dy[best]%mod;
| ^~~~
horses.cpp:125:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
125 | return ans;
| ^~~
# | 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... |