Submission #802104

#	Time	Username	Problem	Language	Result	Execution time	Memory
802104		caganyanmaz	Horses (IOI15_horses)	C++17	100 / 100	510 ms	80388 KiB

horses

#include "horses.h"
#define mp make_pair
#define f first
#define s second
#include <bits/stdc++.h>
using namespace std;


struct SegTree
{
        int n;
        vector<pair<int, double>> data;
        vector<double> lazy;
        SegTree(int n) : n(n), data(n<<2), lazy(n<<2) {}
        pair<int, double> merge(pair<int, double> a, pair<int, double> b)
        {
                if (b.s > a.s)
                        return b;
                else
                        return a;
        }
        void push(int l, int r, int index)
        {
                data[index].s += lazy[index];
                if (r - l > 1)
                {
                        lazy[index<<1] += lazy[index];
                        lazy[(index<<1)|1] += lazy[index];
                }
                lazy[index] = 0;
        }
        void update_range(int l, int r, int index, int ss, int ee, double val)
        {
                push(l, r, index);
                if (ss >= r || l >= ee)
                        return;
                if (ee >= r && l >= ss)
                {
                        lazy[index] += val;
                        push(l, r, index);
                        return;
                }
                int m = l+r>>1;
                update_range(l, m, index<<1, ss, ee, val);
                update_range(m, r, (index<<1)|1, ss, ee, val);
                data[index] = merge(data[index<<1], data[(index<<1)|1]);
        }
        void set(int l, int r, int index, int i, double val)
        {
                push(l, r, index);
                if (i >= r || l > i)
                        return;
                if (r - l == 1)
                {
                        data[index].f = i;
                        data[index].s += val;
                        return;
                }
                int m = l+r>>1;
                set(l, m, index<<1, i, val);
                set(m, r, (index<<1)|1, i, val);
                data[index] = merge(data[index<<1], data[(index<<1)|1]);
        }
        pair<int, double> get(int l, int r, int index, int ss, int ee)
        {
                push(l, r, index);
                if (ss >= r || l >= ee)
                        return mp(-1, -1);
                if (ee >= r && l >= ss)
                        return data[index];
                int m = l+r>>1;
                pair<int, double> lres = get(l, m, index<<1, ss, ee);
                pair<int, double> rres = get(m, r, (index<<1)|1, ss, ee);
                return merge(lres, rres);
        }
        void set(int i, double val) { set(0, n, 1, i, val); }
        pair<int, double> get(int ss, int ee) { return get(0, n, 1, ss, ee); }
        void update_range(int ss, int ee, double val) { update_range(0, n, 1, ss, ee, val); }
};

constexpr static int MXSIZE = 5e5;
constexpr static int MOD = 1e9 + 7;


double xl[MXSIZE];
double yl[MXSIZE];
int x[MXSIZE], y[MXSIZE];
int mul(int64_t a, int64_t b)
{
        return (a * b) % MOD;
}
int st[MXSIZE<<1];
SegTree stm(0);
int n;
void update(int i, int val) { for (st[i+=n]=val;i>1;i>>=1) st[i>>1] = mul(st[i], st[i^1]); }
int get(int l, int r)
{
        int res = 1;
        for (l+=n,r+=n;l<r;l>>=1,r>>=1)
        {
                if (l&1) res = mul(res, st[l++]);
                if (r&1) res = mul(res, st[--r]);
        }
        return res;
}

int get_best()
{
        int i = stm.get(0, n).f;
        return mul(get(0, i+1), y[i]);
}

int init(int N, int X[], int Y[])
{
        n = N;
        stm = SegTree(n);
        for (int i = 0; i < n; i++)
        {
                x[i] = X[i];
                y[i] = Y[i];
                xl[i] = log2(x[i]);
                yl[i] = log2(y[i]);
                update(i, x[i]);
        }
        for (int i = 0; i < n; i++)
                stm.set(i, yl[i]);
        for (int i = 0; i < n; i++)
                stm.update_range(i, n, xl[i]);
        return get_best();

}

int updateY(int pos, int val)
{
        y[pos] = val;

        double _new = log2(val);
        double change = _new - yl[pos];
        yl[pos] = _new;
        stm.set(pos, change);
        return get_best();
}

int updateX(int pos, int val)
{
        x[pos] = val;
        update(pos, val);

        double _new = log2(val);
        double change = _new - xl[pos];
        xl[pos] = _new;
        stm.update_range(pos, n, change);
        return get_best();
}

Compilation message (stderr)

horses.cpp: In constructor 'SegTree::SegTree(int)':
horses.cpp:14:21: warning: declaration of 'n' shadows a member of 'SegTree' [-Wshadow]
   14 |         SegTree(int n) : n(n), data(n<<2), lazy(n<<2) {}
      |                 ~~~~^
horses.cpp:11:13: note: shadowed declaration is here
   11 |         int n;
      |             ^
horses.cpp: In constructor 'SegTree::SegTree(int)':
horses.cpp:14:21: warning: declaration of 'n' shadows a member of 'SegTree' [-Wshadow]
   14 |         SegTree(int n) : n(n), data(n<<2), lazy(n<<2) {}
      |                 ~~~~^
horses.cpp:11:13: note: shadowed declaration is here
   11 |         int n;
      |             ^
horses.cpp: In constructor 'SegTree::SegTree(int)':
horses.cpp:14:21: warning: declaration of 'n' shadows a member of 'SegTree' [-Wshadow]
   14 |         SegTree(int n) : n(n), data(n<<2), lazy(n<<2) {}
      |                 ~~~~^
horses.cpp:11:13: note: shadowed declaration is here
   11 |         int n;
      |             ^
horses.cpp: In member function 'void SegTree::update_range(int, int, int, int, int, double)':
horses.cpp:43:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |                 int m = l+r>>1;
      |                         ~^~
horses.cpp: In member function 'void SegTree::set(int, int, int, int, double)':
horses.cpp:59:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |                 int m = l+r>>1;
      |                         ~^~
horses.cpp: In member function 'std::pair<int, double> SegTree::get(int, int, int, int, int)':
horses.cpp:71:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |                 int m = l+r>>1;
      |                         ~^~
horses.cpp: In function 'int mul(int64_t, int64_t)':
horses.cpp:90:24: warning: conversion from 'int64_t' {aka 'long int'} to 'int' may change value [-Wconversion]
   90 |         return (a * b) % MOD;
      |                ~~~~~~~~^~~~~

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