제출 #380100

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
380100		idk321	Horses (IOI15_horses)	C++11	34 / 100	49 ms	23532 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 = 650;

    int n;
    int* x;
    int* y;


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





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

    ll getBest()
    {

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


    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;

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

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

    int updateX(int pos, int val) {

        x[pos] = val;

       makeBlock(pos / R);


    	return getBest() % mod;
    }

    int updateY(int pos, int val) {

        y[pos] = val;

        makeBlock(pos / R);

    	return getBest() % mod;
    }

컴파일 시 표준 에러 (stderr) 메시지

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

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