Submission #380193

#	Time	Username	Problem	Language	Result	Execution time	Memory
380193		idk321	Horses (IOI15_horses)	C++11	0 / 100	1040 ms	13548 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];
ll right1[R];
ll tree[4 * N];

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

void ins(int num, int i, int a, int b, int node)
{
    if (a == b)
    {
        tree[node] = num;
        return;
    }

    int mid = (a + b) / 2;
    if (i <= mid) ins(num, i, a, mid, node * 2);
    if (i > mid) ins(num, i, mid + 1, b, node * 2 + 1);

    tree[node] = tree[node * 2] * tree[node *2 * 1];
    spMod(tree[node]);
}

ll getFac(int from, int to, int a, int b, int node)
{
    if (from <= a && b <= to)
    {
        return tree[node];
    }

    int mid = (a + b) / 2;
    ll res = 1;
    if (from <= mid) res *= getFac(from, to, a, mid, node * 2);
    if (to > mid) res *= getFac(from, to, mid +1, b, node * 2 + 1);

    spMod(res);
    return res;
}


ll getBest()
{


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



        fac *= left1[a / R];
        spMod(fac);


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

        fac *= right1[a / R];
        spMod(fac);
    }


    ll res = getFac(0, ci, 0, n - 1, 1);
    res %= mod;
    res *= y[ci];
    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 <= ci % R; i++)
    {
        fac *= x[i + block * R];
        spMod(fac);
    }
    left1[block] = fac;

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

    best[block] = ci;
}

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

    for (int a = 0; a < R && a * R < n; a++)
    {
        makeBlock(a);
    }

    for (int i = 0; i < n; i++)
    {
        ins(x[i], i, 0, n - 1, 1);
    }
    //cout << best[0] << endl;
    return getBest() % mod;
}

int updateX(int pos, int val) {

    x[pos] = val;

    ins(x[pos], pos, 0, n - 1, 1);
   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:141:33: warning: declaration of 'N' shadows a global declaration [-Wshadow]
  141 | int init(int N, int X[], int Y[]) {
      |                                 ^
horses.cpp:9:11: note: shadowed declaration is here
    9 | const int N = 500000;
      |           ^
horses.cpp:156:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  156 |     return getBest() % mod;
      |            ~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:167:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  167 |     return getBest() % mod;
      |            ~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:176:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  176 |     return getBest() % mod;
      |            ~~~~~~~~~~^~~~~

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