oj.uz

Submission #60118

# Submission time Handle Problem Language Result Execution time Memory
60118 2018-07-23T16:56:21 Z istlemin Horses (IOI15_horses) C++14
17 / 100
 352 ms 125872 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;
        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.second = dn;
            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();
         ~~~~~~^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 568 KB Output is correct
4 Correct 3 ms 568 KB Output is correct
5 Correct 2 ms 568 KB Output is correct
6 Correct 3 ms 568 KB Output is correct
7 Correct 2 ms 568 KB Output is correct
8 Correct 2 ms 568 KB Output is correct
9 Correct 3 ms 568 KB Output is correct
10 Correct 3 ms 568 KB Output is correct
11 Correct 3 ms 568 KB Output is correct
12 Correct 2 ms 568 KB Output is correct
13 Correct 2 ms 568 KB Output is correct
14 Correct 2 ms 568 KB Output is correct
15 Correct 3 ms 568 KB Output is correct
16 Correct 3 ms 568 KB Output is correct
17 Correct 3 ms 568 KB Output is correct
18 Correct 2 ms 568 KB Output is correct
19 Correct 3 ms 568 KB Output is correct
20 Correct 3 ms 568 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 2 ms 620 KB Output is correct
14 Correct 3 ms 620 KB Output is correct
15 Correct 3 ms 620 KB Output is correct
16 Correct 2 ms 620 KB Output is correct
17 Correct 3 ms 620 KB Output is correct
18 Correct 2 ms 620 KB Output is correct
19 Correct 3 ms 620 KB Output is correct
20 Correct 2 ms 620 KB Output is correct
21 Correct 2 ms 620 KB Output is correct
22 Correct 3 ms 620 KB Output is correct
23 Incorrect 4 ms 764 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 352 ms 125872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 125872 KB Output is correct
2 Correct 2 ms 125872 KB Output is correct
3 Correct 3 ms 125872 KB Output is correct
4 Correct 2 ms 125872 KB Output is correct
5 Correct 3 ms 125872 KB Output is correct
6 Correct 5 ms 125872 KB Output is correct
7 Correct 2 ms 125872 KB Output is correct
8 Correct 2 ms 125872 KB Output is correct
9 Correct 3 ms 125872 KB Output is correct
10 Correct 3 ms 125872 KB Output is correct
11 Correct 3 ms 125872 KB Output is correct
12 Correct 3 ms 125872 KB Output is correct
13 Correct 2 ms 125872 KB Output is correct
14 Correct 2 ms 125872 KB Output is correct
15 Correct 3 ms 125872 KB Output is correct
16 Correct 3 ms 125872 KB Output is correct
17 Correct 3 ms 125872 KB Output is correct
18 Correct 3 ms 125872 KB Output is correct
19 Correct 3 ms 125872 KB Output is correct
20 Correct 3 ms 125872 KB Output is correct
21 Correct 3 ms 125872 KB Output is correct
22 Correct 2 ms 125872 KB Output is correct
23 Incorrect 5 ms 125872 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 125872 KB Output is correct
2 Correct 2 ms 125872 KB Output is correct
3 Correct 2 ms 125872 KB Output is correct
4 Correct 2 ms 125872 KB Output is correct
5 Correct 2 ms 125872 KB Output is correct
6 Correct 2 ms 125872 KB Output is correct
7 Correct 2 ms 125872 KB Output is correct
8 Correct 3 ms 125872 KB Output is correct
9 Correct 3 ms 125872 KB Output is correct
10 Correct 2 ms 125872 KB Output is correct
11 Correct 2 ms 125872 KB Output is correct
12 Correct 2 ms 125872 KB Output is correct
13 Correct 3 ms 125872 KB Output is correct
14 Correct 4 ms 125872 KB Output is correct
15 Correct 3 ms 125872 KB Output is correct
16 Correct 2 ms 125872 KB Output is correct
17 Correct 2 ms 125872 KB Output is correct
18 Correct 2 ms 125872 KB Output is correct
19 Correct 2 ms 125872 KB Output is correct
20 Correct 2 ms 125872 KB Output is correct
21 Correct 2 ms 125872 KB Output is correct
22 Correct 3 ms 125872 KB Output is correct
23 Incorrect 4 ms 125872 KB Output isn't correct
24 Halted 0 ms 0 KB -