| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 774457 |
2023-07-05T18:13:11 Z |
1ne |
말 (IOI15_horses) |
C++14 |
|
91 ms |
51492 KB |
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
vector<long long>cur;
const int mod = 1e9 + 7;
long long inf = 1e9 + 5;
vector<long long>x,y;
long long ans = 1;
struct dataa{
long long vx = 1,vy = 1,ans = 1,vxx = 1;
void add(long long left,long long right,long long val,int op){
if (op == 1){
vx = val;
vxx = val;
}
else{
vy = val;
}
ans = min(inf,vx * vy);
//sum += val *(right - left + 1);
}
};
long long power(long long a,long long b){
long long result =1;
while(b>0){
if(b&1)result=(result*a)%mod; //if you want you can add mod here!
a=(a*a)%mod; //here also.
b>>=1;// shifted one bit similar to divide by 2 :)
}
return result;}
//if m is prime then a^n = a^(n%(mod-1));
struct Segment_Tree{
vector<dataa>tree;
void build(long long node,long long left,long long right,vector<long long>&arr,vector<long long>&brr,long long n){
if (left == right){
tree[node].vx = arr[left];
tree[node].vy = brr[left];
tree[node].ans = min(inf,arr[left] * brr[left]);
tree[node].vxx = arr[left];
return ;
}
long long mid = (left + right)>>1;
long long z = node + ((mid - left + 1)<<1);
build(node + 1,left,mid,arr,brr,n);
build(z,mid + 1,right,arr,brr,n);
tree[node] = combine(tree[node + 1],tree[z]);
}
void init(long long n,vector<long long>&arr,vector<long long>&brr){
tree.resize(2*n - 1);
build(0,0,n-1,arr,brr,n);
}
dataa combine(dataa left,dataa right){
dataa res;
res.vx = min(left.vx * right.vx,inf);
res.vy = right.vy;
res.ans = max(left.ans,min(left.vx * right.ans,inf));
res.vxx = (left.vxx * right.vxx)%mod;
return res;
}
dataa query(long long node,long long left,long long right,long long qleft,long long qright){
if (qright<left|| qleft > right)return {0,0,0,0};
if (qleft<=left && qright>=right){
return tree[node];
}
long long mid = (left + right)>>1;
long long z = node + ((mid - left + 1)<<1);
return combine(query(node + 1,left,mid,qleft,qright),query(z,mid + 1,right,qleft,qright));
}
void update(long long node,long long left,long long right,long long uleft,long long uright,long long v,int op){
if (left > uright || right < uleft) return;
if (uleft <= left && right <=uright){
tree[node].add(left,right,v,op);
return;
}
long long mid = (left + right)>>1;
long long z = node + ((mid - left + 1)<<1);
if (uleft<=mid){
update(node + 1,left,mid,uleft,uright,v,op);
}
if (uright > mid){
update(z,mid + 1,right,uleft,uright,v,op);
}
tree[node] = combine(tree[node + 1],tree[z]);
}
};
int n;
int valid = -1;
Segment_Tree st;
int init(int N, int X[], int Y[]) {
cur.resize(N);
n = N;
for (int i = 0;i<n;++i){
x.push_back(X[i]);
y.push_back(Y[i]);
}
st.init(n,x,y);
long long v = 1;
for (int i = 0;i<N;++i){
bool ok = true;
long long u = 1;
if (st.query(0,0,n - 1,i + 1,n - 1).ans > y[i]){
ok = false;
}
v = (v * x[i])%mod;
if (ok){
valid = i;
return ans = (v * y[i])%mod;
}
}
// return 0;
}
int updateX(int pos, int val) {
st.update(0,0,n - 1,pos,pos,val,1);
if (pos <= valid){
ans = ((ans * power(x[pos],mod - 2))%mod * val)%mod;
x[pos] = val;
}
else if (x[pos] >= val){
x[pos] = val;
}
else{
ans = ((ans * power(y[valid],mod - 2))%mod);
x[pos] = val;
while(valid < n - 1 && st.query(0,0,n - 1,valid + 1,n - 1).ans > y[valid]){
++valid;
ans = (ans * x[valid])%mod;
}
ans = (ans * y[valid])%mod;
}
return ans;
}
int updateY(int pos, int val) {
st.update(0,0,n - 1,pos,pos,val,2);
if (pos < valid){
y[pos] = val;
if (st.query(0,0,n - 1,pos + 1,n - 1).ans < y[pos]){
ans = (st.query(0,0,n - 1,0,pos).vxx * y[pos])%mod;
valid = pos;
}
}
else {
ans = ((ans * power(y[valid],mod - 2))%mod);
y[pos] = val;
while(valid < n - 1 && st.query(0,0,n - 1,valid + 1,n - 1).ans > y[valid]){
++valid;
ans = (ans * x[valid])%mod;
}
ans = (ans * y[valid])%mod;
}
return ans;
}
Compilation message
horses.cpp: In member function 'void dataa::add(long long int, long long int, long long int, int)':
horses.cpp:11:21: warning: unused parameter 'left' [-Wunused-parameter]
11 | void add(long long left,long long right,long long val,int op){
| ~~~~~~~~~~^~~~
horses.cpp:11:36: warning: unused parameter 'right' [-Wunused-parameter]
11 | void add(long long left,long long right,long long val,int op){
| ~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:108:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
108 | return ans = (v * y[i])%mod;
| ~~~~^~~~~~~~~~~~~~~~
horses.cpp:101:13: warning: unused variable 'u' [-Wunused-variable]
101 | long long u = 1;
| ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:132:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
132 | return ans;
| ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:153:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
153 | return ans;
| ^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:112:1: warning: control reaches end of non-void function [-Wreturn-type]
112 | }
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
91 ms |
51492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
296 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
