Submission #139911

#	Time	Username	Problem	Language	Result	Execution time	Memory
139911		bogdan10bos	Horses (IOI15_horses)	C++14	100 / 100	915 ms	49944 KiB

horses

/// ... :(
#include <bits/stdc++.h>
#include "horses.h"

using namespace std;

const int NMAX = 5e5 + 5;

const int mod = 1e9 + 7;

int N, X[NMAX], Y[NMAX];
namespace SegmentTree
{
    int N;
    vector<double> lg, lgadd;
    vector<int> aint, aintadd;

    int sti, dri;
    double lgval;
    int val;

    void B(int nod, int st, int dr)
    {
        lg[nod] = lgadd[nod] = 0;
        aint[nod] = aintadd[nod] = 1;

        if(st == dr)    return;

        int mij = st + (dr - st) / 2;
        B(nod * 2, st, mij);
        B(nod * 2 + 1, mij + 1, dr);
    }

    void init(int _N)
    {
        N = _N;
        lg.resize(4 * N);
        lgadd.reserve(4 * N);
        aint.resize(4 * N);
        aintadd.resize(4 * N);
        B(1, 1, N);
    }

    void lazy(int nod)
    {
        double lgval = lgadd[nod];
        int  val = aintadd[nod];
        lgadd[nod] = 0, aintadd[nod] = 1;

        for(int i = 0; i <= 1; i++)
        {
            lg[nod * 2 + i] += lgval;
            lgadd[nod * 2 + i] += lgval;
            aint[nod * 2 + i] = (1LL * aint[nod * 2 + i] * val) % mod;
            aintadd[nod * 2 + i] = (1LL * aintadd[nod * 2 + i] * val) % mod;
        }
    }

    void U(int nod, int st, int dr)
    {
        if(sti <= st && dr <= dri)
        {
            lg[nod] += lgval;
            lgadd[nod] += lgval;
            aint[nod] = (1LL * aint[nod] * val) % mod;
            aintadd[nod] = (1LL * aintadd[nod] * val) % mod;
            return;
        }

        int mij = st + (dr - st) / 2;
        lazy(nod);

        if(sti <= mij)  U(nod * 2, st, mij);
        if(mij < dri)   U(nod * 2 + 1, mij + 1, dr);

        if(lg[nod * 2] > lg[nod * 2 + 1])
        {
            lg[nod] = lg[nod * 2];
            aint[nod] = aint[nod * 2];
        }
        else
        {
            lg[nod] = lg[nod * 2 + 1];
            aint[nod] = aint[nod * 2 + 1];
        }
    }

    void update(int st, int dr, double mylg, int myval)
    {
        sti = st, dri = dr;
        lgval = mylg;
        val = myval;
        U(1, 1, N);
    }
}

int power(int x, int y)
{
    if(x == 0)  return 0;
    if(y <= 0)  return 1;
    int ans = power( (1LL * x * x) % mod, y >> 1 );
    if(y & 1)   ans = (1LL * ans * x) % mod;
    return ans;
}

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];
    SegmentTree::init(N);
    for(int i = 0; i < N; i++)
    {
        SegmentTree::update(i + 1, N, log2(X[i]), X[i]);
        SegmentTree::update(i + 1, i + 1, log2(Y[i]), Y[i]);
    }
	return SegmentTree::aint[1];
}

int updateX(int pos, int val)
{
    SegmentTree::update(pos + 1, N, -log2(X[pos]), power(X[pos], mod - 2));
    X[pos] = val;
    SegmentTree::update(pos + 1, N, log2(X[pos]), X[pos]);
	return SegmentTree::aint[1];
}

int updateY(int pos, int val) {
    SegmentTree::update(pos + 1, pos + 1, -log2(Y[pos]), power(Y[pos], mod - 2));
    Y[pos] = val;
    SegmentTree::update(pos + 1, pos + 1, log2(Y[pos]), Y[pos]);
	return SegmentTree::aint[1];
}

Compilation message (stderr)

horses.cpp: In function 'void SegmentTree::lazy(int)':
horses.cpp:46:16: warning: declaration of 'lgval' shadows a global declaration [-Wshadow]
         double lgval = lgadd[nod];
                ^~~~~
horses.cpp:19:12: note: shadowed declaration is here
     double lgval;
            ^~~~~
horses.cpp:47:14: warning: declaration of 'val' shadows a global declaration [-Wshadow]
         int  val = aintadd[nod];
              ^~~
horses.cpp:20:9: note: shadowed declaration is here
     int val;
         ^~~
horses.cpp:54:65: warning: conversion to '__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type {aka int}' from 'long long int' may alter its value [-Wconversion]
             aint[nod * 2 + i] = (1LL * aint[nod * 2 + i] * val) % mod;
                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:55:71: warning: conversion to '__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type {aka int}' from 'long long int' may alter its value [-Wconversion]
             aintadd[nod * 2 + i] = (1LL * aintadd[nod * 2 + i] * val) % mod;
                                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void SegmentTree::U(int, int, int)':
horses.cpp:65:49: warning: conversion to '__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type {aka int}' from 'long long int' may alter its value [-Wconversion]
             aint[nod] = (1LL * aint[nod] * val) % mod;
                         ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:66:55: warning: conversion to '__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type {aka int}' from 'long long int' may alter its value [-Wconversion]
             aintadd[nod] = (1LL * aintadd[nod] * val) % mod;
                            ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int power(int, int)':
horses.cpp:101:36: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     int ans = power( (1LL * x * x) % mod, y >> 1 );
                      ~~~~~~~~~~~~~~^~~~~
horses.cpp:102:39: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     if(y & 1)   ans = (1LL * ans * x) % mod;
                       ~~~~~~~~~~~~~~~~^~~~~

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