Submission #283295

#	Time	Username	Problem	Language	Result	Execution time	Memory
283295		stoyan_malinin	Horses (IOI15_horses)	C++14	100 / 100	671 ms	138748 KiB

horses

#include "horses.h"
//#include "grader.cpp"

#include <cmath>
#include <vector>
#include <iostream>

#define double long double

using namespace std;

const int MAXN = 5e5 + 5;
const long long mod = 1e9 + 7;

int n;
double lnPref[MAXN];
int x[MAXN], y[MAXN];

struct NodeInfo
{
    int bestInd;
    double val, lazy;
    long long product;

    NodeInfo(){}
    NodeInfo(int x, double val, int ind)
    {
        this->product = x%mod;
        this->bestInd = ind;
        this->val = val;
        this->lazy = 0;
    }
};

NodeInfo Merge(NodeInfo A, NodeInfo B)
{
    NodeInfo C;
    C.lazy = 0;

    if(A.val<B.val) swap(A, B);
    C.val = A.val;C.bestInd = A.bestInd;

    C.product = (A.product*B.product)%mod;

    return C;
}

struct SegmentTree
{
    NodeInfo info;

    int l, r;
    SegmentTree *L, *R;

    SegmentTree(){}
    SegmentTree(int l, int r)
    {
        this->l = l;
        this->r = r;

        this->L = nullptr;
        this->R = nullptr;
    }

    void build()
    {
        if(l==r)
        {
            this->info = NodeInfo(x[l], lnPref[l]+log(y[l]), l);
            return;
        }

        L = new SegmentTree(l, (l+r)/2);
        R = new SegmentTree((l+r)/2+1, r);

        L->build();
        R->build();
        info = Merge(L->info, R->info);
    }

    void updateLazy()
    {
        info.val += info.lazy;
        if(l!=r)
        {
            L->info.lazy += info.lazy;
            R->info.lazy += info.lazy;
        }

        info.lazy = 0;
    }

    void updateVal(int ql, int qr, double change)
    {
        updateLazy();

        if(l>=ql && r<=qr)
        {
            info.val += change;
            if(l!=r)
            {
                L->info.lazy += change;
                R->info.lazy += change;
            }

            return;
        }
        if(r<ql || l>qr) return;

        L->updateVal(ql, qr, change);
        R->updateVal(ql, qr, change);
        info = Merge(L->info, R->info);
    }

    void updateProduct(int q, int newVal)
    {
        updateLazy();

        if(l==r && l==q)
        {
            info.product = newVal;
            return;
        }
        if(r<q || l>q) return;

        L->updateProduct(q, newVal);
        R->updateProduct(q, newVal);
        info = Merge(L->info, R->info);
    }

    long long queryProduct(int ql, int qr)
    {
        updateLazy();

        if(l>=ql && r<=qr) return info.product;
        if(r<ql || l>qr) return 1;

        return (L->queryProduct(ql, qr)*R->queryProduct(ql, qr))%mod;
    }

    void print()
    {
        cout << l << " " << r << " -> " << info.val << " " << info.bestInd << '\n';
        if(l!=r)
        {
            L->print();
            R->print();
        }
    }
};

SegmentTree *T;

long long evalInd(int ind)
{
    long long ans = T->queryProduct(0, ind);
    return (ans*y[ind])%mod;
}

int init(int N, int X[], int Y[])
{
    n = N;
    for(int i = 0;i<n;i++)
    {
        x[i] = X[i];
        y[i] = Y[i];
    }

    lnPref[0] = log(x[0]);
    for(int i = 1;i<n;i++) lnPref[i] = lnPref[i-1] + log(x[i]);

    T = new SegmentTree(0, n-1);
    T->build();

    //T->print();

    return evalInd(T->info.bestInd);
}

int updateX(int pos, int val)
{
	double change = log(val) - log(x[pos]);
	x[pos] = val;

    T->updateVal(pos, n-1, change);
    T->updateProduct(pos, x[pos]);

    return evalInd(T->info.bestInd);
}

int updateY(int pos, int val)
{
    double change = log(val) - log(y[pos]);
	y[pos] = val;

    T->updateVal(pos, pos, change);
    //cout << T->info.bestInd << " " << change << '\n';

    //T->print();

    return evalInd(T->info.bestInd);
}

Compilation message (stderr)

horses.cpp: In constructor 'NodeInfo::NodeInfo(int, long double, int)':
horses.cpp:27:5: warning: declaration of 'val' shadows a member of 'NodeInfo' [-Wshadow]
   27 |     {
      |     ^
horses.cpp:22:12: note: shadowed declaration is here
   22 |     double val, lazy;
      |            ^~~
horses.cpp:27:5: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   27 |     {
      |     ^
horses.cpp:17:5: note: shadowed declaration is here
   17 | int x[MAXN], y[MAXN];
      |     ^
horses.cpp: In constructor 'NodeInfo::NodeInfo(int, long double, int)':
horses.cpp:32:5: warning: declaration of 'val' shadows a member of 'NodeInfo' [-Wshadow]
   32 |     }
      |     ^
horses.cpp:22:12: note: shadowed declaration is here
   22 |     double val, lazy;
      |            ^~~
horses.cpp:32:5: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   32 |     }
      |     ^
horses.cpp:17:5: note: shadowed declaration is here
   17 | int x[MAXN], y[MAXN];
      |     ^
horses.cpp: In constructor 'NodeInfo::NodeInfo(int, long double, int)':
horses.cpp:32:5: warning: declaration of 'val' shadows a member of 'NodeInfo' [-Wshadow]
   32 |     }
      |     ^
horses.cpp:22:12: note: shadowed declaration is here
   22 |     double val, lazy;
      |            ^~~
horses.cpp:32:5: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   32 |     }
      |     ^
horses.cpp:17:5: note: shadowed declaration is here
   17 | int x[MAXN], y[MAXN];
      |     ^
horses.cpp: In constructor 'SegmentTree::SegmentTree(int, int)':
horses.cpp:57:5: warning: declaration of 'r' shadows a member of 'SegmentTree' [-Wshadow]
   57 |     {
      |     ^
horses.cpp:52:12: note: shadowed declaration is here
   52 |     int l, r;
      |            ^
horses.cpp:57:5: warning: declaration of 'l' shadows a member of 'SegmentTree' [-Wshadow]
   57 |     {
      |     ^
horses.cpp:52:9: note: shadowed declaration is here
   52 |     int l, r;
      |         ^
horses.cpp: In constructor 'SegmentTree::SegmentTree(int, int)':
horses.cpp:63:5: warning: declaration of 'r' shadows a member of 'SegmentTree' [-Wshadow]
   63 |     }
      |     ^
horses.cpp:52:12: note: shadowed declaration is here
   52 |     int l, r;
      |            ^
horses.cpp:63:5: warning: declaration of 'l' shadows a member of 'SegmentTree' [-Wshadow]
   63 |     }
      |     ^
horses.cpp:52:9: note: shadowed declaration is here
   52 |     int l, r;
      |         ^
horses.cpp: In constructor 'SegmentTree::SegmentTree(int, int)':
horses.cpp:63:5: warning: declaration of 'r' shadows a member of 'SegmentTree' [-Wshadow]
   63 |     }
      |     ^
horses.cpp:52:12: note: shadowed declaration is here
   52 |     int l, r;
      |            ^
horses.cpp:63:5: warning: declaration of 'l' shadows a member of 'SegmentTree' [-Wshadow]
   63 |     }
      |     ^
horses.cpp:52:9: note: shadowed declaration is here
   52 |     int l, r;
      |         ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:177:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  177 |     return evalInd(T->info.bestInd);
      |            ~~~~~~~^~~~~~~~~~~~~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:188:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  188 |     return evalInd(T->info.bestInd);
      |            ~~~~~~~^~~~~~~~~~~~~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:201:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  201 |     return evalInd(T->info.bestInd);
      |            ~~~~~~~^~~~~~~~~~~~~~~~~

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