Submission #60124

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
60124	2018-07-23T17:11:40 Z	istlemin	Horses (IOI15_horses)	C++14	Compilation error	0 ms	0 KB

horses

#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)%mod;
        } else {
            val = init[dn]%mod;
        }
    }

    ll update(ll a,ll v){
        if(dn>a||up<=a) return val;
        if(dn+1==up) {
			return val = v%mod;
        }
        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<long double,ll> op1(pair<long double,ll> a,long double b){
    return {a.first+b,a.second};
}

class Node{
public:
    pair<long double,ll> val = {0,0};
    long double toPush = 0;
    ll dn,up;
    Node *left;
    Node *right;

    Node(ll _dn,ll _up,vector<long 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<long double,ll> update(ll a,ll b,long 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<long double,ll> query(ll a,ll b){
        if(dn>=b||up<=a) return {-1e30,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<long 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]);

	}

	/*cout<<"#######"<<endl;
	rep(i,0,n) cout<<x[i]<<" ";
	cout<<endl;
	rep(i,0,n) cout<<y[i]<<" ";
	cout<<endl;
	rep(i,0,n) cout<<stMul->query(i,i+1)<<" ";
	cout<<endl;
	rep(i,0,n) cout<<st->query(i,i+1).first<<" ";
	cout<<endl;
	cout<<"#######"<<endl;*/

	return getAns();
}

int updateX(int pos, int val) {
    st->update(pos,n,-log(long double(x[pos]))+log(long 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:149: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:153:27: error: expected primary-expression before 'long'
     st->update(pos,n,-log(long double(x[pos]))+log(long double(val)));
                           ^~~~
horses.cpp:153:52: error: expected primary-expression before 'long'
     st->update(pos,n,-log(long double(x[pos]))+log(long double(val)));
                                                    ^~~~
horses.cpp:156: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:162:15: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return getAns();
         ~~~~~~^~