# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
60111 |
2018-07-23T16:47:39 Z |
istlemin |
Horses (IOI15_horses) |
C++14 |
|
334 ms |
125888 KB |
#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;
ll n;
vi x;
vi y;
ll mod = 1e9+7;
class OldNode{
public:
ll val = 1;
ll dn,up;
OldNode *left;
OldNode *right;
OldNode(ll _dn,ll _up,vi &init){
dn = _dn;
up = _up;
if(dn+1!=up){
left = new OldNode(dn,(dn+up)/2,init);
right = new OldNode((dn+up)/2,up,init);
val = left->val*right->val;
} else {
val = init[dn];
}
}
ll update(ll a,ll v){
if(dn>a||up<=a) return val;
if(dn+1==up) {
return val = v;
}
return val = (left->update(a,v)*right->update(a,v))%mod;
}
ll query(ll a,ll b){
if(dn>=b||up<=a) return 1;
if(a<=dn&&up<=b) return val;
return (left->query(a,b)*right->query(a,b))%mod;
}
};
pair<double,ll> op1(pair<double,ll> a,double b){
return {a.first+b,a.second};
}
class Node{
public:
pair<double,ll> val = {0,0};
double toPush = 0;
ll dn,up;
Node *left;
Node *right;
Node(ll _dn,ll _up,vector<double> &init){
dn = _dn;
up = _up;
val.second = up-1;
if(dn+1!=up){
left = new Node(dn,(dn+up)/2,init);
right = new Node((dn+up)/2,up,init);
val = max(left->val,right->val);
} else {
val.first = init[dn];
}
}
void push(){
if(dn+1==up) return;
left->val=op1(left->val,toPush);
right->val=op1(right->val,toPush);
left->toPush+=toPush;
right->toPush+=toPush;
toPush = 0;
}
pair<double,ll> update(ll a,ll b,double v){
if(dn>=b||up<=a) return val;
if(a<=dn&&up<=b) {
val=op1(val,v);
toPush+=v;
return val;
}
push();
return val = max(left->update(a,b,v),right->update(a,b,v));
}
pair<double,ll> query(ll a,ll b){
if(dn>=b||up<=a) return {-1e18,0};
if(a<=dn&&up<=b) return val;
push();
return max(left->query(a,b),right->query(a,b));
}
};
Node *st;
OldNode *stMul;
ll getAns(){
ll index = st->query(0,n).second;
ll ans = (stMul->query(0,index+1)*y[index])%mod;
//cout<<ans<<endl;
return ans;
}
int init(int N, int X[], int Y[]) {
n = N;
x.resize(n,1);
y.resize(n,1);
rep(i,0,n) x[i] = X[i];
rep(i,0,n) y[i] = Y[i];
vector<double> stD(n);
stD[0] = log(x[0]);
rep(i,1,n) stD[i] = log(x[i]) + stD[i-1];
rep(i,0,n) stD[i] += log(y[i]);
st = new Node(0,N,stD);
stMul = new OldNode(0,N,x);
rep(i,0,n){
//updateX(i,X[i]);
//updateY(i,Y[i]);
}
return getAns();
}
int updateX(int pos, int val) {
st->update(pos,n,-log(double(x[pos]))+log(double(val)));
stMul->update(pos,val);
x[pos] = val;
return getAns();
}
int updateY(int pos, int val) {
st->update(pos,pos+1,-log(y[pos])+log(val));
y[pos] = val;
return getAns();
}
Compilation message
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:137:15: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
return getAns();
~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:144:15: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
return getAns();
~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:150:15: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
return getAns();
~~~~~~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
436 KB |
Output is correct |
4 |
Correct |
3 ms |
488 KB |
Output is correct |
5 |
Correct |
3 ms |
488 KB |
Output is correct |
6 |
Correct |
4 ms |
528 KB |
Output is correct |
7 |
Correct |
2 ms |
528 KB |
Output is correct |
8 |
Correct |
3 ms |
528 KB |
Output is correct |
9 |
Correct |
2 ms |
528 KB |
Output is correct |
10 |
Correct |
3 ms |
528 KB |
Output is correct |
11 |
Correct |
3 ms |
528 KB |
Output is correct |
12 |
Correct |
3 ms |
548 KB |
Output is correct |
13 |
Correct |
3 ms |
548 KB |
Output is correct |
14 |
Correct |
3 ms |
548 KB |
Output is correct |
15 |
Correct |
2 ms |
548 KB |
Output is correct |
16 |
Correct |
2 ms |
548 KB |
Output is correct |
17 |
Correct |
2 ms |
548 KB |
Output is correct |
18 |
Correct |
3 ms |
548 KB |
Output is correct |
19 |
Correct |
3 ms |
596 KB |
Output is correct |
20 |
Correct |
3 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
596 KB |
Output is correct |
2 |
Correct |
3 ms |
596 KB |
Output is correct |
3 |
Correct |
2 ms |
596 KB |
Output is correct |
4 |
Correct |
3 ms |
596 KB |
Output is correct |
5 |
Correct |
2 ms |
596 KB |
Output is correct |
6 |
Correct |
3 ms |
596 KB |
Output is correct |
7 |
Correct |
3 ms |
596 KB |
Output is correct |
8 |
Correct |
3 ms |
596 KB |
Output is correct |
9 |
Correct |
3 ms |
596 KB |
Output is correct |
10 |
Correct |
3 ms |
596 KB |
Output is correct |
11 |
Correct |
3 ms |
628 KB |
Output is correct |
12 |
Correct |
2 ms |
628 KB |
Output is correct |
13 |
Correct |
2 ms |
628 KB |
Output is correct |
14 |
Correct |
3 ms |
628 KB |
Output is correct |
15 |
Correct |
2 ms |
628 KB |
Output is correct |
16 |
Correct |
3 ms |
628 KB |
Output is correct |
17 |
Correct |
3 ms |
628 KB |
Output is correct |
18 |
Correct |
2 ms |
628 KB |
Output is correct |
19 |
Correct |
3 ms |
628 KB |
Output is correct |
20 |
Correct |
3 ms |
628 KB |
Output is correct |
21 |
Correct |
3 ms |
628 KB |
Output is correct |
22 |
Correct |
3 ms |
628 KB |
Output is correct |
23 |
Incorrect |
4 ms |
764 KB |
Output isn't correct |
24 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
334 ms |
125888 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
125888 KB |
Output is correct |
2 |
Correct |
2 ms |
125888 KB |
Output is correct |
3 |
Correct |
2 ms |
125888 KB |
Output is correct |
4 |
Correct |
2 ms |
125888 KB |
Output is correct |
5 |
Correct |
2 ms |
125888 KB |
Output is correct |
6 |
Correct |
3 ms |
125888 KB |
Output is correct |
7 |
Correct |
4 ms |
125888 KB |
Output is correct |
8 |
Correct |
3 ms |
125888 KB |
Output is correct |
9 |
Correct |
3 ms |
125888 KB |
Output is correct |
10 |
Correct |
3 ms |
125888 KB |
Output is correct |
11 |
Correct |
3 ms |
125888 KB |
Output is correct |
12 |
Correct |
2 ms |
125888 KB |
Output is correct |
13 |
Correct |
2 ms |
125888 KB |
Output is correct |
14 |
Correct |
3 ms |
125888 KB |
Output is correct |
15 |
Correct |
3 ms |
125888 KB |
Output is correct |
16 |
Correct |
3 ms |
125888 KB |
Output is correct |
17 |
Correct |
3 ms |
125888 KB |
Output is correct |
18 |
Correct |
2 ms |
125888 KB |
Output is correct |
19 |
Correct |
2 ms |
125888 KB |
Output is correct |
20 |
Correct |
2 ms |
125888 KB |
Output is correct |
21 |
Correct |
3 ms |
125888 KB |
Output is correct |
22 |
Correct |
2 ms |
125888 KB |
Output is correct |
23 |
Incorrect |
5 ms |
125888 KB |
Output isn't correct |
24 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
125888 KB |
Output is correct |
2 |
Correct |
2 ms |
125888 KB |
Output is correct |
3 |
Correct |
3 ms |
125888 KB |
Output is correct |
4 |
Correct |
3 ms |
125888 KB |
Output is correct |
5 |
Correct |
3 ms |
125888 KB |
Output is correct |
6 |
Correct |
3 ms |
125888 KB |
Output is correct |
7 |
Correct |
2 ms |
125888 KB |
Output is correct |
8 |
Correct |
3 ms |
125888 KB |
Output is correct |
9 |
Correct |
3 ms |
125888 KB |
Output is correct |
10 |
Correct |
2 ms |
125888 KB |
Output is correct |
11 |
Correct |
2 ms |
125888 KB |
Output is correct |
12 |
Correct |
2 ms |
125888 KB |
Output is correct |
13 |
Correct |
2 ms |
125888 KB |
Output is correct |
14 |
Correct |
1 ms |
125888 KB |
Output is correct |
15 |
Correct |
3 ms |
125888 KB |
Output is correct |
16 |
Correct |
2 ms |
125888 KB |
Output is correct |
17 |
Correct |
2 ms |
125888 KB |
Output is correct |
18 |
Correct |
3 ms |
125888 KB |
Output is correct |
19 |
Correct |
2 ms |
125888 KB |
Output is correct |
20 |
Correct |
2 ms |
125888 KB |
Output is correct |
21 |
Correct |
3 ms |
125888 KB |
Output is correct |
22 |
Correct |
2 ms |
125888 KB |
Output is correct |
23 |
Incorrect |
4 ms |
125888 KB |
Output isn't correct |
24 |
Halted |
0 ms |
0 KB |
- |