제출 #778116

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
778116		boris_mihov	말 (IOI15_horses)	C++17	100 / 100	537 ms	60848 KiB

horses

#include "horses.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <set>

typedef long long llong;
const int MAXN = 500000 + 10;
const int MOD = 1e9 + 7;

int n;
struct SegmentTree
{
    struct Node
    {
        int prodX;
        int maxY;

        Node()
        {
            prodX = 1;
            maxY = 0;
        }
    };

    Node tree[4*MAXN];
    Node combine(Node left, Node right)
    {
        Node res;
        res.maxY = std::max(left.maxY, right.maxY);
        res.prodX = (1LL * left.prodX * right.prodX) % MOD;
        return res;
    }

    void build(int l, int r, int node, int x[], int y[])
    {
        if (l == r)
        {
            tree[node].prodX = x[l];
            tree[node].maxY = y[l];
            return;
        }

        int mid = (l + r) / 2;
        build(l, mid, 2*node, x, y);
        build(mid + 1, r, 2*node + 1, x, y);
        tree[node] = combine(tree[2*node], tree[2*node + 1]);
    }

    void update(int l, int r, int node, int queryPos, int x, int y)
    {
        if (l == r)
        {
            tree[node].prodX = x;
            tree[node].maxY = y;
            return;
        }

        int mid = (l + r) / 2;
        if (queryPos <= mid) update(l, mid, 2*node, queryPos, x, y);
        else update(mid + 1, r, 2*node + 1, queryPos, x, y);
        tree[node] = combine(tree[2*node], tree[2*node + 1]);
    }

    Node query(int l, int r, int node, int queryL, int queryR)
    {
        if (queryL <= l && r <= queryR)
        {
            return tree[node];
        }

        Node res;
        int mid = (l + r) / 2;
        if (queryL <= mid) res = combine(res, query(l, mid, 2*node, queryL, queryR));
        if (mid + 1 <= queryR) res = combine(res, query(mid + 1, r, 2*node + 1, queryL, queryR));
        return res;
    }

    void build(int x[], int y[])
    {
        build(1, n, 1, x, y);
    }

    void update(int pos, int x, int y)
    {
        update(1, n, 1, pos, x, y);
    }

    int findProd(int to)
    {
        if (to == 0) return 1;
        return query(1, n, 1, 1, to).prodX;
    }

    int findMAX(int l, int r)
    {
        return query(1, n, 1, l, r).maxY;
    }
};

int x[MAXN];
int y[MAXN];
SegmentTree tree;
std::set <int> pos;
std::vector <int> toCheck;

int answerQuery()
{
    if (pos.empty())
    {
        return tree.findMAX(1, n);
    }

    __int128 prod = 1;
    auto it = pos.rbegin();
    toCheck.clear();
    toCheck.push_back(n + 1);

    for (int i = 0 ; prod < MOD && it != pos.rend() ; ++it)
    {
        prod *= x[*it];
        toCheck.push_back(*it);
    }

    if (prod < MOD && toCheck.back() != 1)
    {
        toCheck.push_back(1);
    }

    std::reverse(toCheck.begin(), toCheck.end());
    prod = 1;

    __int128 ans = 1;
    for (int i = 0 ; i + 1 < toCheck.size() ; ++i)
    {
        prod *= x[toCheck[i]];
        ans = std::max(ans, prod * tree.findMAX(toCheck[i], toCheck[i + 1] - 1));
    }

    ans %= MOD;
    ans *= tree.findProd(toCheck[0] - 1);
    return ans % MOD;
}

int init(int N, int X[], int Y[]) 
{
    n = N;
    x[0] = 1;
    for (int i = 1 ; i <= n ; ++i)
    {
        x[i] = X[i - 1];
        y[i] = Y[i - 1];

        if (x[i] > 1)
        {
            pos.insert(i);
        }
    }

    tree.build(x, y);
	return answerQuery();
}

int updateX(int qPos, int val) 
{	
    qPos++;
    if (x[qPos] > 1)
    {
        pos.erase(pos.find(qPos));
    }

    x[qPos] = val;
    if (x[qPos] > 1)
    {
        pos.insert(qPos);
    }

    tree.update(qPos, x[qPos], y[qPos]);
	return answerQuery();
}

int updateY(int qPos, int val) 
{
    qPos++;
    y[qPos] = val;
    tree.update(qPos, x[qPos], y[qPos]);
	return answerQuery();
}

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

horses.cpp: In member function 'SegmentTree::Node SegmentTree::combine(SegmentTree::Node, SegmentTree::Node)':
horses.cpp:33:54: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   33 |         res.prodX = (1LL * left.prodX * right.prodX) % MOD;
      |                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int answerQuery()':
horses.cpp:121:14: warning: unused variable 'i' [-Wunused-variable]
  121 |     for (int i = 0 ; prod < MOD && it != pos.rend() ; ++it)
      |              ^
horses.cpp:136:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |     for (int i = 0 ; i + 1 < toCheck.size() ; ++i)
      |                      ~~~~~~^~~~~~~~~~~~~~~~
horses.cpp:144:16: warning: conversion from '__int128' to 'int' may change value [-Wconversion]
  144 |     return ans % MOD;
      |            ~~~~^~~~~

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