Submission #380201

#	Time	Username	Problem	Language	Result	Execution time	Memory
380201		idk321	Horses (IOI15_horses)	C++11	0 / 100	718 ms	22252 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;


ll tree[4 * N];
int tree2[4 * N];
int tree3[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;
        tree2[node] = num;
        if (num == 1)
        {
            tree3[node] = 0;
        } else
        {
            tree3[node] = 1;
        }
        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];
    tree2[node] = max(tree2[node * 2], tree2[node * 2 + 1]);
    spMod(tree[node]);
    tree3[node] = tree3[node *2] + tree3[node *2  +1];
}

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;
}

int getMax(int from, int to, int a, int b, int node)
{
    if (from <= a && b <= to)
    {
        return tree2[node];
    }

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

    return res;
}

int getKth(int k, int a, int b, int node)
{
    if (tree[node] <= k) return -1;

    if (a == b)
    {
        return a;
    }

    int mid = (a + b) / 2;
    if (tree[node * 2 + 1] > k) return getKth(k, mid + 1, b, node * 2 + 1);
    return getKth(k - tree[node * 2 + 1], a, mid, node * 2);
}


ll getBest()
{

    int ci = -1;
    int cy = -1;

    for (int i = 30; i >= 0; i--)
    {
        int cur = getKth(i, 0, n - 1, 1);
        int prev = getKth(i + 1, 0, n - 1, 1);
        if (cur == -1) continue;

        ll ones = 0;
        ll yVal = y[cur];
        if (cur - prev > 1)
        {
            ones = getMax(prev + 1, cur - 1, 0, n - 1, 1);
        }

        if (ones > (ll) x[cur] * y[cur])
        {
            cur--;
            yVal = ones;
        }

        if (ci == -1)
        {
            ci = cur;
        } else
        {
            ll fac = getFac(prev + 1, cur, 0, n - 1, 1);
            fac *= yVal;
            if (fac > cy)
            {
                cy = yVal;
                ci = cur;
            }
        }
    }

    int prev = getKth(0, 0, n - 1, 1);
    if (prev < n - 1)
    {
        ll yVal = getMax(prev + 1, n - 1, 0, n - 1, 1);
        int cur = n - 1;
        ll fac = getFac(prev + 1, cur, 0, n - 1, 1);
        fac *= yVal;
        if (fac > cy)
        {
            cy = yVal;
            ci = cur;
        }
    }

    ll res = getFac(0, ci, 0, n - 1, 1);
    res %= mod;
    res *= cy;
    res %= mod;

    return res;
}


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


    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);


    return getBest() % mod;
}

int updateY(int pos, int val) {

    y[pos] = val;


    return getBest() % mod;
}

Compilation message (stderr)

horses.cpp: In function 'int getKth(int, int, int, int)':
horses.cpp:98:21: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   98 |     return getKth(k - tree[node * 2 + 1], a, mid, node * 2);
      |                   ~~^~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'll getBest()':
horses.cpp:136:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  136 |                 cy = yVal;
      |                      ^~~~
horses.cpp:151:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  151 |             cy = yVal;
      |                  ^~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:165:33: warning: declaration of 'N' shadows a global declaration [-Wshadow]
  165 | int init(int N, int X[], int Y[]) {
      |                                 ^
horses.cpp:9:11: note: shadowed declaration is here
    9 | const int N = 500000;
      |           ^
horses.cpp:176:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  176 |     return getBest() % mod;
      |            ~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:185:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  185 |     return getBest() % mod;
      |            ~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:193:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  193 |     return getBest() % mod;
      |            ~~~~~~~~~~^~~~~

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