| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 298188 |
2020-09-12T14:21:36 Z |
TMJN |
말 (IOI15_horses) |
C++17 |
|
520 ms |
90380 KB |
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
constexpr long long mod=1000000007;
pair<long double,long long> treemax[1<<20],treeupd[1<<20];
int N,*X,*Y;
long double dx[500000],dy[500000];
long long pw(long long x,int y){
long long a=1;
while(y){
if(y&1)a=a*x%mod;
x=x*x%mod;
y/=2;
}
return a;
}
long long modinv(long long x){
return pw(x,mod-2);
}
void update(int k,int l,int r,int p,int q,long long val,long double ln){
if(q<l||r<p)return;
else if(p<=l&&r<=q){
treemax[k].second*=val;
treemax[k].second%=mod;
treemax[k].first+=ln;
treeupd[k].second*=val;
treeupd[k].second%=mod;
treeupd[k].first+=ln;
}
else{
treemax[k+k].second*=treeupd[k].second;
treemax[k+k+1].second*=treeupd[k].second;
treemax[k+k].second%=mod;
treemax[k+k+1].second%=mod;
treeupd[k+k].second*=treeupd[k].second;
treeupd[k+k+1].second*=treeupd[k].second;
treeupd[k+k].second%=mod;
treeupd[k+k+1].second%=mod;
treemax[k+k].first+=treeupd[k].first;
treemax[k+k+1].first+=treeupd[k].first;
treeupd[k+k].first+=treeupd[k].first;
treeupd[k+k+1].first+=treeupd[k].first;
treeupd[k].second=1;
treeupd[k].first=0;
update(k+k,l,(l+r)/2,p,q,val,ln);
update(k+k+1,(l+r)/2+1,r,p,q,val,ln);
treemax[k]=max(treemax[k+k],treemax[k+k+1]);
}
}
int init(int n, int x[], int y[]) {
N=n;
X=x;
Y=y;
long double ld=0;
long long ll=1;
for(int i=0;i<N;i++){
dx[i]=logl(X[i]);
dy[i]=logl(Y[i]);
ll*=X[i];
ll%=mod;
ld+=dx[i];
treemax[i+(1<<19)]={ld+dy[i],ll*Y[i]%mod};
}
for(int i=(1<<19)-1;i;i--){
treemax[i]=max(treemax[i+i],treemax[i+i+1]);
treeupd[i]={0,1};
}
return treemax[1].second;
}
int updateX(int pos, int val) {
long double ld=logl(val);
update(1,0,(1<<19)-1,pos,N-1,val*modinv(X[pos])%mod,ld-dx[pos]);
X[pos]=val;
dx[pos]=ld;
return treemax[1].second;
}
int updateY(int pos, int val) {
long double ld=logl(val);
update(1,0,(1<<19)-1,pos,pos,val*modinv(Y[pos])%mod,ld-dy[pos]);
Y[pos]=val;
dy[pos]=ld;
return treemax[1].second;
}
Compilation message
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:75:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
75 | return treemax[1].second;
| ~~~~~~~~~~~^~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:83:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
83 | return treemax[1].second;
| ~~~~~~~~~~~^~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:91:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
91 | return treemax[1].second;
| ~~~~~~~~~~~^~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
28 ms |
33152 KB |
Output is correct |
| 2 |
Correct |
34 ms |
33164 KB |
Output is correct |
| 3 |
Correct |
29 ms |
33144 KB |
Output is correct |
| 4 |
Correct |
27 ms |
33144 KB |
Output is correct |
| 5 |
Correct |
29 ms |
33212 KB |
Output is correct |
| 6 |
Correct |
28 ms |
33144 KB |
Output is correct |
| 7 |
Correct |
27 ms |
33152 KB |
Output is correct |
| 8 |
Correct |
27 ms |
33152 KB |
Output is correct |
| 9 |
Correct |
28 ms |
33280 KB |
Output is correct |
| 10 |
Correct |
28 ms |
33176 KB |
Output is correct |
| 11 |
Correct |
28 ms |
33144 KB |
Output is correct |
| 12 |
Correct |
28 ms |
33152 KB |
Output is correct |
| 13 |
Correct |
28 ms |
33232 KB |
Output is correct |
| 14 |
Correct |
30 ms |
33152 KB |
Output is correct |
| 15 |
Correct |
27 ms |
33144 KB |
Output is correct |
| 16 |
Correct |
27 ms |
33144 KB |
Output is correct |
| 17 |
Correct |
28 ms |
33144 KB |
Output is correct |
| 18 |
Correct |
27 ms |
33152 KB |
Output is correct |
| 19 |
Correct |
27 ms |
33144 KB |
Output is correct |
| 20 |
Correct |
27 ms |
33152 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
27 ms |
33144 KB |
Output is correct |
| 2 |
Correct |
28 ms |
33144 KB |
Output is correct |
| 3 |
Correct |
28 ms |
33152 KB |
Output is correct |
| 4 |
Correct |
30 ms |
33272 KB |
Output is correct |
| 5 |
Correct |
28 ms |
33152 KB |
Output is correct |
| 6 |
Correct |
27 ms |
33152 KB |
Output is correct |
| 7 |
Correct |
28 ms |
33152 KB |
Output is correct |
| 8 |
Correct |
28 ms |
33152 KB |
Output is correct |
| 9 |
Correct |
28 ms |
33144 KB |
Output is correct |
| 10 |
Correct |
29 ms |
33144 KB |
Output is correct |
| 11 |
Correct |
29 ms |
33176 KB |
Output is correct |
| 12 |
Correct |
28 ms |
33152 KB |
Output is correct |
| 13 |
Correct |
29 ms |
33152 KB |
Output is correct |
| 14 |
Correct |
28 ms |
33144 KB |
Output is correct |
| 15 |
Correct |
27 ms |
33144 KB |
Output is correct |
| 16 |
Correct |
28 ms |
33152 KB |
Output is correct |
| 17 |
Correct |
28 ms |
33152 KB |
Output is correct |
| 18 |
Correct |
28 ms |
33144 KB |
Output is correct |
| 19 |
Correct |
27 ms |
33144 KB |
Output is correct |
| 20 |
Correct |
28 ms |
33144 KB |
Output is correct |
| 21 |
Correct |
29 ms |
33272 KB |
Output is correct |
| 22 |
Correct |
28 ms |
33144 KB |
Output is correct |
| 23 |
Correct |
29 ms |
33280 KB |
Output is correct |
| 24 |
Correct |
30 ms |
33272 KB |
Output is correct |
| 25 |
Correct |
29 ms |
33272 KB |
Output is correct |
| 26 |
Correct |
29 ms |
33272 KB |
Output is correct |
| 27 |
Correct |
29 ms |
33272 KB |
Output is correct |
| 28 |
Correct |
31 ms |
33272 KB |
Output is correct |
| 29 |
Correct |
30 ms |
33272 KB |
Output is correct |
| 30 |
Correct |
30 ms |
33272 KB |
Output is correct |
| 31 |
Correct |
30 ms |
33272 KB |
Output is correct |
| 32 |
Correct |
29 ms |
33280 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
251 ms |
69388 KB |
Output is correct |
| 2 |
Correct |
496 ms |
85704 KB |
Output is correct |
| 3 |
Correct |
466 ms |
86264 KB |
Output is correct |
| 4 |
Correct |
514 ms |
86136 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
28 ms |
33144 KB |
Output is correct |
| 2 |
Correct |
28 ms |
33148 KB |
Output is correct |
| 3 |
Correct |
28 ms |
33144 KB |
Output is correct |
| 4 |
Correct |
27 ms |
33144 KB |
Output is correct |
| 5 |
Correct |
27 ms |
33176 KB |
Output is correct |
| 6 |
Correct |
28 ms |
33152 KB |
Output is correct |
| 7 |
Correct |
28 ms |
33272 KB |
Output is correct |
| 8 |
Correct |
28 ms |
33152 KB |
Output is correct |
| 9 |
Correct |
27 ms |
33152 KB |
Output is correct |
| 10 |
Correct |
28 ms |
33144 KB |
Output is correct |
| 11 |
Correct |
27 ms |
33144 KB |
Output is correct |
| 12 |
Correct |
28 ms |
33152 KB |
Output is correct |
| 13 |
Correct |
27 ms |
33144 KB |
Output is correct |
| 14 |
Correct |
28 ms |
33144 KB |
Output is correct |
| 15 |
Correct |
28 ms |
33144 KB |
Output is correct |
| 16 |
Correct |
28 ms |
33144 KB |
Output is correct |
| 17 |
Correct |
28 ms |
33144 KB |
Output is correct |
| 18 |
Correct |
29 ms |
33144 KB |
Output is correct |
| 19 |
Correct |
30 ms |
33144 KB |
Output is correct |
| 20 |
Correct |
29 ms |
33168 KB |
Output is correct |
| 21 |
Correct |
29 ms |
33152 KB |
Output is correct |
| 22 |
Correct |
28 ms |
33152 KB |
Output is correct |
| 23 |
Correct |
30 ms |
33280 KB |
Output is correct |
| 24 |
Correct |
29 ms |
33272 KB |
Output is correct |
| 25 |
Correct |
30 ms |
33280 KB |
Output is correct |
| 26 |
Correct |
38 ms |
33280 KB |
Output is correct |
| 27 |
Correct |
30 ms |
33272 KB |
Output is correct |
| 28 |
Correct |
36 ms |
33272 KB |
Output is correct |
| 29 |
Correct |
31 ms |
33272 KB |
Output is correct |
| 30 |
Correct |
32 ms |
33272 KB |
Output is correct |
| 31 |
Correct |
30 ms |
33280 KB |
Output is correct |
| 32 |
Correct |
29 ms |
33272 KB |
Output is correct |
| 33 |
Correct |
172 ms |
82552 KB |
Output is correct |
| 34 |
Correct |
181 ms |
82680 KB |
Output is correct |
| 35 |
Correct |
165 ms |
68856 KB |
Output is correct |
| 36 |
Correct |
205 ms |
68984 KB |
Output is correct |
| 37 |
Correct |
168 ms |
82020 KB |
Output is correct |
| 38 |
Correct |
145 ms |
69272 KB |
Output is correct |
| 39 |
Correct |
133 ms |
69240 KB |
Output is correct |
| 40 |
Correct |
160 ms |
69496 KB |
Output is correct |
| 41 |
Correct |
140 ms |
69368 KB |
Output is correct |
| 42 |
Correct |
159 ms |
69248 KB |
Output is correct |
| 43 |
Correct |
137 ms |
69056 KB |
Output is correct |
| 44 |
Correct |
143 ms |
74744 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
30 ms |
33152 KB |
Output is correct |
| 2 |
Correct |
37 ms |
33144 KB |
Output is correct |
| 3 |
Correct |
30 ms |
33152 KB |
Output is correct |
| 4 |
Correct |
29 ms |
33152 KB |
Output is correct |
| 5 |
Correct |
28 ms |
33152 KB |
Output is correct |
| 6 |
Correct |
28 ms |
33184 KB |
Output is correct |
| 7 |
Correct |
28 ms |
33144 KB |
Output is correct |
| 8 |
Correct |
37 ms |
33144 KB |
Output is correct |
| 9 |
Correct |
30 ms |
33144 KB |
Output is correct |
| 10 |
Correct |
29 ms |
33152 KB |
Output is correct |
| 11 |
Correct |
29 ms |
33144 KB |
Output is correct |
| 12 |
Correct |
28 ms |
33152 KB |
Output is correct |
| 13 |
Correct |
28 ms |
33144 KB |
Output is correct |
| 14 |
Correct |
28 ms |
33152 KB |
Output is correct |
| 15 |
Correct |
28 ms |
33144 KB |
Output is correct |
| 16 |
Correct |
28 ms |
33272 KB |
Output is correct |
| 17 |
Correct |
27 ms |
33152 KB |
Output is correct |
| 18 |
Correct |
28 ms |
33144 KB |
Output is correct |
| 19 |
Correct |
28 ms |
33232 KB |
Output is correct |
| 20 |
Correct |
28 ms |
33152 KB |
Output is correct |
| 21 |
Correct |
28 ms |
33152 KB |
Output is correct |
| 22 |
Correct |
27 ms |
33144 KB |
Output is correct |
| 23 |
Correct |
31 ms |
33280 KB |
Output is correct |
| 24 |
Correct |
30 ms |
33272 KB |
Output is correct |
| 25 |
Correct |
31 ms |
33296 KB |
Output is correct |
| 26 |
Correct |
32 ms |
33272 KB |
Output is correct |
| 27 |
Correct |
29 ms |
33272 KB |
Output is correct |
| 28 |
Correct |
30 ms |
33272 KB |
Output is correct |
| 29 |
Correct |
29 ms |
33280 KB |
Output is correct |
| 30 |
Correct |
29 ms |
33272 KB |
Output is correct |
| 31 |
Correct |
29 ms |
33268 KB |
Output is correct |
| 32 |
Correct |
31 ms |
33280 KB |
Output is correct |
| 33 |
Correct |
258 ms |
70148 KB |
Output is correct |
| 34 |
Correct |
509 ms |
85732 KB |
Output is correct |
| 35 |
Correct |
478 ms |
86008 KB |
Output is correct |
| 36 |
Correct |
520 ms |
85880 KB |
Output is correct |
| 37 |
Correct |
176 ms |
82808 KB |
Output is correct |
| 38 |
Correct |
177 ms |
82808 KB |
Output is correct |
| 39 |
Correct |
160 ms |
68984 KB |
Output is correct |
| 40 |
Correct |
161 ms |
69024 KB |
Output is correct |
| 41 |
Correct |
160 ms |
82168 KB |
Output is correct |
| 42 |
Correct |
142 ms |
69496 KB |
Output is correct |
| 43 |
Correct |
131 ms |
69368 KB |
Output is correct |
| 44 |
Correct |
150 ms |
69624 KB |
Output is correct |
| 45 |
Correct |
130 ms |
69624 KB |
Output is correct |
| 46 |
Correct |
133 ms |
69368 KB |
Output is correct |
| 47 |
Correct |
136 ms |
69112 KB |
Output is correct |
| 48 |
Correct |
130 ms |
74744 KB |
Output is correct |
| 49 |
Correct |
485 ms |
90380 KB |
Output is correct |
| 50 |
Correct |
489 ms |
90104 KB |
Output is correct |
| 51 |
Correct |
287 ms |
81272 KB |
Output is correct |
| 52 |
Correct |
328 ms |
80888 KB |
Output is correct |
| 53 |
Correct |
492 ms |
88440 KB |
Output is correct |
| 54 |
Correct |
380 ms |
73368 KB |
Output is correct |
| 55 |
Correct |
293 ms |
71544 KB |
Output is correct |
| 56 |
Correct |
353 ms |
79352 KB |
Output is correct |
| 57 |
Correct |
256 ms |
72364 KB |
Output is correct |
| 58 |
Correct |
264 ms |
72756 KB |
Output is correct |
| 59 |
Correct |
131 ms |
74832 KB |
Output is correct |
