Submission #380093

#	Time	Username	Problem	Language	Result	Execution time	Memory
380093		idk321	Horses (IOI15_horses)	C++11	77 / 100	1576 ms	23020 KiB

horses

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

using namespace std;
typedef long long ll;

const int mod = 1000000007;

const int N = 500000;
const int R = 710;

int n;
int* x;
int* y;


int best[R];
ll left1[R][R];
ll right1[R][R];
int f1;
ll left2;



void spMod(ll& num)
{
    if (num >= mod)
    {
        num %= mod;
        num += mod;
    }
}

ll getBigBest()
{

    int ci = max(0, n - 40);
    ll cbest = left2 * y[ci];
    cbest %= mod;
    cbest *= x[ci];
    cbest %= mod;

    ll fac = 1;
    ll facAll = x[ci];
    for (int i = max(0, n - 40) + 1; i < n; i++)
    {
        fac *= x[i];
        facAll *= x[i];
        facAll %= mod;
        spMod(fac);
        if (fac > y[ci] || fac * y[i] > y[ci])
        {
            fac = 1;
            ci = i;
            cbest = left2 * facAll;
            cbest %= mod;
            cbest *= y[i];
            cbest %= mod;
        }
    }

    return cbest;
}

ll getBest()
{
    if (!f1) return getBigBest();

    ll cbest = left1[0][best[0]] % mod;
    cbest *= y[best[0]];
    cbest %= mod;
    int ci = best[0];
    ll fac = 1;
    if (ci != min(R - 1, n - 1)) fac *= right1[0][ci + 1];
    spMod(fac);
    ll facAll = left1[0][min(R - 1, n - 1)];
    facAll %= mod;
    for (int a = R; a < n; a += R)
    {
        int i = best[a / R];



        fac *= left1[a / R][i % R];
        spMod(fac);
        facAll *= left1[a / R][i % R];
        facAll %= mod;


        if (fac * y[i] > y[ci])
        {
            cbest = facAll * y[i];
            cbest %= mod;
            ci = i;
            fac = 1;
        }

        if (i != min(n - 1, a + R - 1))
        {
            fac *= right1[a / R][(i + 1) % R];
            spMod(fac);
            facAll *= right1[a / R][(i + 1) % R];
            facAll %= mod;
        }
    }


    return cbest;
}


ll binExp(ll num, ll power)
{
    ll res = 1;
    while (power > 0)
    {
        if (power % 2 == 0)
        {
            power /= 2;
            num *= num;
            num %= mod;
        } else
        {
            power--;
            res *= num;
            res %= mod;
        }
    }

    return res;
}

void makeBlock(int block)
{
    int ci = block * R;
    ll fac = 1;
    for (int i = block * R + 1; i < min(n, (block + 1) * R); i++)
    {
        fac *= x[i];
        spMod(fac);
        if (fac > y[ci] || fac * y[i] > y[ci])
        {
            ci = i;
            fac = 1;
        }
    }

    fac = 1;
    for (int i = 0; i < R; i++)
    {
        if (i + block * R >= n) continue;
        fac *= x[i + block * R];
        spMod(fac);
        left1[block][i] = fac;
    }

    fac = 1;
    for (int i = R - 1; i >= 0; i--)
    {
        if (i + block * R >= n) continue;
        fac *= x[i + block * R];
        spMod(fac);
        right1[block][i] = fac;
    }

    best[block] = ci;
}



int init(int N, int X[], int Y[]) {
    n = N;
    x = X;
    y = Y;

    f1 = 0;
    for (int i = 0; i < n; i++)
    {
        if (x[i] == 1) f1++;
    }
    for (int a = 0; a < R && a * R < n; a++)
    {
        makeBlock(a);
    }

    left2 = 1;
    for (int i = 0; i < n - 40; i++)
    {
        left2 *= x[i];
        left2 %= mod;
    }

    //cout << best[0] << endl;
	return getBest() % mod;
}

int updateX(int pos, int val) {

    if (x[pos] == 1) f1--;

    if (pos < n - 40)
    {
        left2 *= binExp(x[pos], mod - 2);
        left2 %= mod;
    }
    x[pos] = val;
    if (pos < n - 40)
    {
        left2 *= val;
        left2 %= mod;
    }

    if (x[pos] == 1) f1++;

   makeBlock(pos / R);


	return getBest() % mod;
}

int updateY(int pos, int val) {

    y[pos] = val;

    makeBlock(pos / R);

	return getBest() % mod;
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:171:33: warning: declaration of 'N' shadows a global declaration [-Wshadow]
  171 | int init(int N, int X[], int Y[]) {
      |                                 ^
horses.cpp:9:11: note: shadowed declaration is here
    9 | const int N = 500000;
      |           ^
horses.cpp:194:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  194 |  return getBest() % mod;
      |         ~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:218:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  218 |  return getBest() % mod;
      |         ~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:227:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  227 |  return getBest() % mod;
      |         ~~~~~~~~~~^~~~~

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