Submission #833901

#	Time	Username	Problem	Language	Result	Execution time	Memory
833901		Victor	Horses (IOI15_horses)	C++17	100 / 100	451 ms	182208 KiB

horses

#include "horses.h"

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define per(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back

typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;

const ll INF = 1'000'000'007;

struct Node {
    ll lo,hi,id;
    long double log_sum=0,val,madd=0;
    Node *l,*r;
    Node(const vll&x, const vll&y, long double add, ll L,ll R) : lo(L), hi(R) {
        if(hi-lo==1) {
            log_sum=logf64(x[lo])+add;
            val=log_sum+logf64(y[lo]);
            id=lo;

        } else {
            ll mid=(lo+hi)/2;
            l=new Node(x,y,add,lo,mid);
            r=new Node(x,y,l->log_sum,mid,hi);
            log_sum=r->log_sum;
            tie(val,id)=max(pair<long double,ll>(l->val,l->id),pair<long double,ll>(r->val,r->id));
        }
        //cout<<"lo = "<<lo<<" hi = "<<hi<<" log_sum = "<<log_sum<<" add = "<<add<<" val = "<<val<<endl;
    }


    void updateX(ll pos, long double v) { // v is new logx[pos] - prev logx[pos]
        if(hi<=pos) return;
        if(pos<=lo) {
            madd+=v;
            log_sum+=v;
            val+=v;
            return;
        }

        push();
        l->updateX(pos,v);
        r->updateX(pos,v);
        tie(val,id)=max(pair<long double,ll>(l->val,l->id),pair<long double,ll>(r->val,r->id));
    }

    void updateY(ll pos, ll v) { // v is new y[pos]
        if(pos<lo||hi<=pos) return;
        if(hi-lo==1) {
            val=log_sum+logf64(v);
            return;
        }

        push();
        l->updateY(pos,v);
        r->updateY(pos,v);
        tie(val,id)=max(pair<long double,ll>(l->val,l->id),pair<long double,ll>(r->val,r->id));
    }

    void push() {
        if(madd!=0) {
            l->updateX(0,madd);
            r->updateX(0,madd);
            madd=0;
        }
    }
};

struct Prod {
    ll lo,hi,prod;
    Prod *l,*r;
    Prod(const vll&x,ll L,ll R) : lo(L), hi(R) {
        if(hi-lo==1) {
            prod=x[lo];

        } else {
            ll mid=(lo+hi)/2;
            l=new Prod(x,lo,mid);
            r=new Prod(x,mid,hi);
            prod=l->prod*r->prod%INF;
        }
    }

    ll query(ll R) {
        if(R<=lo) return 1;
        if(hi<=R) return prod;
        return l->query(R)*r->query(R)%INF;
    }

    void updateX(ll pos,ll v) { // v is new x[pos]
        if(pos<lo||hi<=pos) return; 
        if(hi-lo==1) {
            prod=v;
            return;
        }

        l->updateX(pos,v);
        r->updateX(pos,v);
        prod=l->prod*r->prod%INF;
    }
};

vll x,y;
Node *segtree;
Prod *prodseg;

int init(int N, int X[], int Y[]) {
    rep(i,0,N) {
        assert(X[i]&&Y[i]);
        x.pb(X[i]);
        y.pb(Y[i]);
    }

    segtree=new Node(x,y,0,0,N);
    prodseg=new Prod(x,0,N);

    ll id=segtree->id;
    return prodseg->query(id+1)*y[id]%INF;
}

int updateX(int pos, int val) {
    assert(val);
    double diff=logf64(val)-logf64(x[pos]);
    x[pos]=val;
    segtree->updateX(pos,diff);
    prodseg->updateX(pos,val);
    ll id=segtree->id;
    return prodseg->query(id+1)*y[id]%INF;
}

int updateY(int pos, int val) {
    assert(val);
    y[pos]=val;
    segtree->updateY(pos,val);
    ll id=segtree->id;
    return prodseg->query(id+1)*y[id]%INF;
}

Compilation message (stderr)

horses.cpp: In constructor 'Node::Node(const vll&, const vll&, long double, ll, ll)':
horses.cpp:27:33: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to '_Float64' {aka 'double'} may change value [-Wconversion]
   27 |             log_sum=logf64(x[lo])+add;
      |                                 ^
horses.cpp:28:37: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to '_Float64' {aka 'double'} may change value [-Wconversion]
   28 |             val=log_sum+logf64(y[lo]);
      |                                     ^
horses.cpp: In member function 'void Node::updateY(ll, ll)':
horses.cpp:60:32: warning: conversion from 'll' {aka 'long long int'} to '_Float64' {aka 'double'} may change value [-Wconversion]
   60 |             val=log_sum+logf64(v);
      |                                ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:128:38: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  128 |     return prodseg->query(id+1)*y[id]%INF;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:133:42: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to '_Float64' {aka 'double'} may change value [-Wconversion]
  133 |     double diff=logf64(val)-logf64(x[pos]);
      |                                          ^
horses.cpp:138:38: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  138 |     return prodseg->query(id+1)*y[id]%INF;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:146:38: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  146 |     return prodseg->query(id+1)*y[id]%INF;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 23 / 23
• Subtask 5: 23 / 23