| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 418585 |
2021-06-05T14:57:02 Z |
Chaska |
Horses (IOI15_horses) |
C++11 |
|
116 ms |
29892 KB |
#include "horses.h"
#include <bits/stdc++.h>
#define fo(a,b,c) for (int a=b;a<=c;a++)
using namespace std;
const int MAXN = 5e5+5,mod = 1e9+7;
typedef long long ll;
int n,x[MAXN],y[MAXN];
ll st[4*MAXN],r;
void ini(int no,int in,int fin)
{
if (in == fin) {
st[no] = x[in];
return;
}
int mid=(in+fin)/2;
ini(no*2+1,in,mid);
ini(no*2+2,mid+1,fin);
st[no] = st[no*2+1]*st[no*2+2];
st[no]%= mod;
return;
}
void get(int no,int in,int fin,int u,int v)
{
if (fin < u || in > v) return;
if (u<=in && fin <= v){
r *= st[no];
r %= mod;
return;
}
int mid=(in+fin)/2;
get(no*2+1,in,mid,u,v);
get(no*2+2,mid+1,fin,u,v);
return;
}
void upd(int no,int in,int fin,int u,int v)
{
if (fin < u || in > u) return;
if (u<=in && fin <= u){
st[no] = v;
return;
}
int mid=(in+fin)/2;
upd(no*2+1,in,mid,u,v);
upd(no*2+2,mid+1,fin,u,v);
st[no] = st[no*2+1]*st[no*2+2];
st[no]%= mod;
return;
}
int sol()
{
ll k = 0; /// respuesta optima, empezando en pos = -1
ll res = -1; // indice res optima
ll q=1; // caballos
fo(i,max(0,n-35),n-1) {
q *= x[i];
if (k<=q) {
res = i;
k = y[i];
q = 1;
} else {
q *= y[i];
if (k<=q) {
res = i;
k = y[i];
q = 1;
} else {
q /= y[i];
}
}
}
r=1;
get(0,0,n-1,0,res);
r %= mod;
r *= y[res];
r %= mod;
return r;
}
int init(int N, int X[], int Y[]) {
n = N;
fo(i,0,n-1) x[i] = X[i];
fo(i,0,n-1) y[i] = Y[i];
ini(0,0,n-1);
return sol();
}
int updateX(int pos, int val) {
x[pos] = val;
upd(0,0,n-1,pos,val);
return sol();
}
int updateY(int pos, int val) {
y[pos] = val;
return sol();
}
Compilation message
horses.cpp: In function 'int sol()':
horses.cpp:72:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
72 | get(0,0,n-1,0,res);
| ^~~
horses.cpp:76:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
76 | return r;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
0 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
0 ms |
204 KB |
Output is correct |
| 12 |
Correct |
1 ms |
204 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
0 ms |
204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
204 KB |
Output is correct |
| 17 |
Correct |
1 ms |
204 KB |
Output is correct |
| 18 |
Correct |
0 ms |
204 KB |
Output is correct |
| 19 |
Correct |
1 ms |
204 KB |
Output is correct |
| 20 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
0 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
0 ms |
204 KB |
Output is correct |
| 11 |
Correct |
1 ms |
204 KB |
Output is correct |
| 12 |
Correct |
0 ms |
204 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
204 KB |
Output is correct |
| 17 |
Correct |
1 ms |
204 KB |
Output is correct |
| 18 |
Correct |
1 ms |
204 KB |
Output is correct |
| 19 |
Correct |
1 ms |
204 KB |
Output is correct |
| 20 |
Correct |
0 ms |
204 KB |
Output is correct |
| 21 |
Correct |
1 ms |
204 KB |
Output is correct |
| 22 |
Correct |
0 ms |
204 KB |
Output is correct |
| 23 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 24 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
18904 KB |
Output is correct |
| 2 |
Correct |
116 ms |
29892 KB |
Output is correct |
| 3 |
Correct |
77 ms |
20988 KB |
Output is correct |
| 4 |
Correct |
116 ms |
24952 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| 9 |
Correct |
0 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
1 ms |
204 KB |
Output is correct |
| 12 |
Correct |
1 ms |
204 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
0 ms |
204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
204 KB |
Output is correct |
| 17 |
Correct |
1 ms |
204 KB |
Output is correct |
| 18 |
Correct |
1 ms |
204 KB |
Output is correct |
| 19 |
Correct |
1 ms |
204 KB |
Output is correct |
| 20 |
Correct |
0 ms |
204 KB |
Output is correct |
| 21 |
Correct |
1 ms |
204 KB |
Output is correct |
| 22 |
Correct |
1 ms |
204 KB |
Output is correct |
| 23 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 24 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
0 ms |
204 KB |
Output is correct |
| 11 |
Correct |
1 ms |
204 KB |
Output is correct |
| 12 |
Correct |
1 ms |
204 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
204 KB |
Output is correct |
| 17 |
Correct |
0 ms |
204 KB |
Output is correct |
| 18 |
Correct |
0 ms |
204 KB |
Output is correct |
| 19 |
Correct |
1 ms |
204 KB |
Output is correct |
| 20 |
Correct |
1 ms |
204 KB |
Output is correct |
| 21 |
Correct |
1 ms |
204 KB |
Output is correct |
| 22 |
Correct |
1 ms |
204 KB |
Output is correct |
| 23 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 24 |
Halted |
0 ms |
0 KB |
- |
