제출 #342415

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
342415		blue	말 (IOI15_horses)	C++11	0 / 100	692 ms	325712 KiB

horses

#include "horses.h"
#include <vector>
#include <set>
using namespace std;

long long mod = 1e9 + 7;

struct segtree
{
    int l;
    int r;

    long long mx = 0;
    long long p_mod = 0;
    long long p_actual = 0;

    segtree* left;
    segtree* right;

    segtree()
    {
        ;
    }

    segtree(int L, int R)
    {
        l = L;
        r = R;
        if(l == r) return;
        int m = (l+r)/2;
        left = new segtree(l, m);
        right = new segtree(m+1, r);
    }

    void update(int I, int V)
    {
        if(I < l || r < I) return;

        if(l == r) mx = p_mod = p_actual = V;
        else
        {
            left->update(I, V);
            right->update(I, V);

            mx = max(left->mx, right->mx);
            p_mod = (left->p_mod * right->p_mod) % mod;
            p_actual = left->p_actual * right->p_actual;
        }
    }

    long long rangemax(int L, int R)
    {
        if(R < l || r < L) return 0;
        if(R <= l && r <= L) return mx;
        return max(left->rangemax(L, R), right->rangemax(L, R));
    }

    long long rangeprod_actual(int L, int R)
    {
        if(R < l || r < L) return 1;
        if(R <= l && r <= L) return p_actual;
        return left->rangeprod_actual(L, R) * right->rangeprod_actual(L, R);
    }

    long long rangeprod_mod(int L, int R)
    {
        if(R < l || r < L) return 1;
        if(R <= l && r <= L) return p_mod;
        return (left->rangeprod_mod(L, R) * right->rangeprod_mod(L, R)) % mod;
    }
};

struct growth
{
    int i;
    long long x;
};

bool operator < (growth A, growth B)
{
    return A.i > B.i;
}

segtree X;
segtree Y;
set<growth> Xset;
int N;

int compute()
{
    if(Xset.size() == 0) return Y.rangemax(0, N-1);

    int maxprod_pos;
    long long maxprod = 1;

    for(growth g: Xset)
    {
        maxprod *= g.x;
        maxprod_pos = g.i;
        if(maxprod > 1e9) break;
    }

    int res_pos;
    long long temp_res = 1;

    for(growth g: Xset)
    {
        if(g.i < maxprod_pos) break;
        if(X.rangeprod_actual(maxprod_pos, g.i) * Y.rangemax(g.i, N-1) >= temp_res)
        {
            temp_res = X.rangeprod_actual(maxprod_pos, g.i) * Y.rangemax(g.i, N-1);
            res_pos = g.i;
        }
    }

    return (X.rangeprod_mod(0, res_pos) * Y.rangemax(res_pos, N-1)) % mod;
}

int init(int n, int x[], int y[])
{
    N = n;
    X = segtree(0, n-1);
    for(int i = 0; i < n; i++)
    {
        X.update(i, x[i]);
        if(x[i] != 1) Xset.insert(growth{i, x[i]});
    }

    Y = segtree(0, n-1);
    for(int i = 0; i < n; i++) Y.update(i, y[i]);

    return compute();
}

int updateX(int pos, int val)
{
    int curr_val = X.rangemax(pos, pos);
    if(curr_val != 1) Xset.erase(growth{pos, curr_val});

    X.update(pos, val);
    if(val != 1) Xset.insert(growth{pos, val});

    return compute();
}

int updateY(int pos, int val)
{
    Y.update(pos, val);
    return compute();
}

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

horses.cpp: In function 'int compute()':
horses.cpp:91:43: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   91 |     if(Xset.size() == 0) return Y.rangemax(0, N-1);
      |                                 ~~~~~~~~~~^~~~~~~~
horses.cpp:100:12: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
  100 |         if(maxprod > 1e9) break;
      |            ^~~~~~~
horses.cpp:116:69: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  116 |     return (X.rangeprod_mod(0, res_pos) * Y.rangemax(res_pos, N-1)) % mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:137:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  137 |     int curr_val = X.rangemax(pos, pos);
      |                    ~~~~~~~~~~^~~~~~~~~~
horses.cpp: In function 'int compute()':
horses.cpp:55:57: warning: 'res_pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |         return max(left->rangemax(L, R), right->rangemax(L, R));
      |                                          ~~~~~~~~~~~~~~~^~~~~~
horses.cpp:103:9: note: 'res_pos' was declared here
  103 |     int res_pos;
      |         ^~~~~~~

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