제출 #341210

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

horses

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

long long mod = 1e9 + 7;

long long ll(int a)
{
    return (long long)(a);
}

struct LLL
{
    vector<int> d = vector<int>(5, 0);

    LLL()
    {
        ;
    }

    LLL(long long X)
    {
        d[0] = X;
    }
};

LLL operator * (LLL A, LLL B)
{
    LLL res;
    for(int i = 0; i < 4; i++)
    {
        for(int j = 0; i+j < 4; j++)
        {
            res.d[i+j] += A.d[i] * B.d[j];
            res.d[i+j+1] += res.d[i+j] / 1000000000;
            res.d[i+j] = res.d[i+j] % 1000000000;
        }
    }
    return res;
}

bool operator < (LLL A, LLL B)
{
    for(int i = 4; i >= 0; i++)
    {
        if(A.d[i] < B.d[i]) return 1;
        if(A.d[i] > B.d[i]) return 0;
    }
    return 0;
}

struct segtree
{
    int l;
    int r;

    long long p_mod = 1;
    LLL p_actual = LLL(1);
    long long mx = 1;

    segtree* left = NULL;
    segtree* right = NULL;

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

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

    LLL rangeprod_actual(int L, int R)
    {
        if(L > R) return LLL(1);
        if(r < L || R < l) return LLL(1);
        if(L <= l && r <= R)
        {
            // cout << L << ' ' << R << ' ' << l << ' ' << r << ' ' << "rpa" << ' ' << p_actual.d[1] << p_actual.d[0] << '\n';
            return p_actual;
        }
        else
        {
            return left->rangeprod_actual(L, R) * right->rangeprod_actual(L, R);
        }
    }

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

    void update(int I, long long V)
    {
        if(I < l || r < I) return;
        if(l == r)
        {
            p_mod = mx = V;
            p_actual = LLL(V);
            // cout << "build " << l << ' ' << r << ' ' << p_actual.d[1] << ' ' << p_actual.d[0] << '\n';
        }
        else
        {
            left->update(I, V);
            right->update(I, V);
            p_mod = (left->p_mod * right->p_mod) % mod;
            p_actual = left->p_actual * right->p_actual;
            mx = max(left->mx, right->mx);
            // cout << "build " << l << ' ' << r << ' ' << p_actual.d[1] << ' ' << p_actual.d[0] << '\n';
        }
    }
};

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

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

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

int compute()
{
    LLL maxprod = LLL(1);
    int maxprod_pos = -1;
    for(growth g: Xset)
    {
        maxprod = maxprod * LLL(g.x);
        maxprod_pos = g.i;
        if(LLL(1e9) < maxprod) break;
    } //maxprod_pos is the first position with a suffix product > 1e9

    LLL res = 0;
    int res_pos = 0;

    // for(int i = 0; i < N; i++) cout << X.rangeprod_mod(i, i) << ' ';
    // cout << '\n';
    // for(int i = 0; i < N; i++) cout << X.rangeprod_actual(i, i) << ' ';
    // cout << '\n';
    // for(int i = 0; i < N; i++) cout << Y.rangemax(i, i) << ' ';
    // cout << '\n';

    // cout << maxprod_pos << '\n';

    for(growth g: Xset)
    {
        // cout << g.i << ' ' << g.x << '\n';
        if(g.i < maxprod_pos) break;
        if(LLL(res) < X.rangeprod_actual(maxprod_pos, g.i) * LLL(Y.rangemax(g.i, N-1)))
        {
            // cout << "prod " << ' ' << maxprod_pos << ' ' << g.i << " " << X.rangeprod_actual(maxprod_pos, g.i).d[0] << ' ' << Y.rangemax(g.i, N-1) << '\n';
            res = X.rangeprod_actual(maxprod_pos, g.i) * LLL(Y.rangemax(g.i, N-1));
            res_pos = g.i;
        }
        // if(g.i > 0 && X.rangeprod_actual(maxprod_pos, g.i-1) * Y.rangemax(g.i-1, N-1) > res)
        // {
        //     res = X.rangeprod_actual(maxprod_pos, g.i-1) * Y.rangemax(g.i-1, N-1);
        //     res_pos = g.i-1;
        // }
    }
    // cout << res_pos << '\n';
    return int( (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);
    Y = segtree(0, N-1);
    for(int i = 0; i < N; i++)
    {
        X.update(i, x[i]);
        if(x[i] != 1) Xset.insert(growth{i, ll(x[i])});

        Y.update(i, ll(y[i]));
    }

    return compute();
}

int updateX(int pos, int val)
{
    X.update(pos, val);
    Xset.erase(growth{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 constructor 'LLL::LLL(long long int)':
horses.cpp:26:16: warning: conversion from 'long long int' to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
   26 |         d[0] = X;
      |                ^

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