제출 #380217

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
380217		idk321	말 (IOI15_horses)	C++11	20 / 100	766 ms	17644 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 i, int a, int b, int node)
{
    if (a == b)
    {
        tree[node] = x[a];
        if (x[a] == 1)
        {
            tree3[node] = 0;
        } else
        {
            tree3[node] = 1;
        }
        return;
    }

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

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

void insMax(int i, int a, int b, int node)
{
    if (a == b)
    {
        tree2[node] = y[a];
        return;
    }


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

    tree2[node] = max(tree2[node * 2], tree2[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;
}

void getKth(int k, int a, int b, int node, vector<int>& v)
{
    if (tree3[node] == 0) return;

    if (a == b)
    {
        v.push_back(a);
        return;
    }

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


ll getBest()
{

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

    vector<int> v;
    getKth(30, 0, n - 1, 1, v);
    while (v.size() < 31) v.push_back(-1);

    for (int i = 29; i >= 0; i--)
    {
        int cur = v[i];
        int prev = v[i + 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 > x[cur] * yVal)
        {
            cur--;
            yVal = ones;
        }

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

        prev = cur;
    }

    int prev = v[0];
    if (prev < n - 1)
    {
        ll yVal = getMax(prev + 1, n - 1, 0, n - 1, 1);
        int cur = n - 1;

        if (ci == -1)
        {
            cy = yVal;
            ci = cur;
        } else
        {
            ll fac = getFac(ci + 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(i, 0, n - 1, 1);
        insMax(i, 0, n - 1, 1);
    }
    //cout << best[0] << endl;
    return getBest() % mod;
}

int updateX(int pos, int val) {

    x[pos] = val;
    ins(pos, 0, n - 1, 1);


    return getBest() % mod;
}

int updateY(int pos, int val) {

    y[pos] = val;
    insMax(pos, 0, n - 1, 1);

    return getBest() % mod;
}

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

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

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