답안 #778116

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
778116	2023-07-10T06:26:10 Z	boris_mihov	말 (IOI15_horses)	C++17	100 / 100	537 ms	60848 KB

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

Compilation message

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.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	15956 KB	Output is correct
2	Correct	8 ms	15956 KB	Output is correct
3	Correct	8 ms	15956 KB	Output is correct
4	Correct	8 ms	15956 KB	Output is correct
5	Correct	7 ms	15956 KB	Output is correct
6	Correct	7 ms	15928 KB	Output is correct
7	Correct	10 ms	15956 KB	Output is correct
8	Correct	8 ms	15956 KB	Output is correct
9	Correct	7 ms	15908 KB	Output is correct
10	Correct	8 ms	15892 KB	Output is correct
11	Correct	7 ms	15956 KB	Output is correct
12	Correct	8 ms	15960 KB	Output is correct
13	Correct	7 ms	15932 KB	Output is correct
14	Correct	9 ms	15900 KB	Output is correct
15	Correct	7 ms	15956 KB	Output is correct
16	Correct	7 ms	15956 KB	Output is correct
17	Correct	7 ms	15956 KB	Output is correct
18	Correct	7 ms	15900 KB	Output is correct
19	Correct	8 ms	15960 KB	Output is correct
20	Correct	8 ms	15896 KB	Output is correct

Subtask #2

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	15956 KB	Output is correct
2	Correct	8 ms	15956 KB	Output is correct
3	Correct	7 ms	15956 KB	Output is correct
4	Correct	7 ms	15964 KB	Output is correct
5	Correct	7 ms	15956 KB	Output is correct
6	Correct	7 ms	15956 KB	Output is correct
7	Correct	7 ms	15964 KB	Output is correct
8	Correct	10 ms	15924 KB	Output is correct
9	Correct	9 ms	15884 KB	Output is correct
10	Correct	7 ms	15924 KB	Output is correct
11	Correct	7 ms	15956 KB	Output is correct
12	Correct	9 ms	15956 KB	Output is correct
13	Correct	7 ms	15964 KB	Output is correct
14	Correct	7 ms	15956 KB	Output is correct
15	Correct	7 ms	15956 KB	Output is correct
16	Correct	7 ms	15956 KB	Output is correct
17	Correct	7 ms	15968 KB	Output is correct
18	Correct	7 ms	15968 KB	Output is correct
19	Correct	8 ms	15948 KB	Output is correct
20	Correct	8 ms	15964 KB	Output is correct
21	Correct	8 ms	16084 KB	Output is correct
22	Correct	7 ms	15924 KB	Output is correct
23	Correct	8 ms	15972 KB	Output is correct
24	Correct	8 ms	15964 KB	Output is correct
25	Correct	8 ms	16060 KB	Output is correct
26	Correct	8 ms	16000 KB	Output is correct
27	Correct	10 ms	15956 KB	Output is correct
28	Correct	9 ms	15944 KB	Output is correct
29	Correct	9 ms	15932 KB	Output is correct
30	Correct	8 ms	15952 KB	Output is correct
31	Correct	9 ms	15976 KB	Output is correct
32	Correct	10 ms	15936 KB	Output is correct

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	493 ms	48188 KB	Output is correct
2	Correct	312 ms	60848 KB	Output is correct
3	Correct	306 ms	51984 KB	Output is correct
4	Correct	350 ms	55812 KB	Output is correct

Subtask #4

23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	15956 KB	Output is correct
2	Correct	7 ms	15956 KB	Output is correct
3	Correct	7 ms	15956 KB	Output is correct
4	Correct	7 ms	15960 KB	Output is correct
5	Correct	8 ms	15964 KB	Output is correct
6	Correct	7 ms	15912 KB	Output is correct
7	Correct	8 ms	15860 KB	Output is correct
8	Correct	7 ms	15956 KB	Output is correct
9	Correct	8 ms	15888 KB	Output is correct
10	Correct	7 ms	15956 KB	Output is correct
11	Correct	7 ms	15960 KB	Output is correct
12	Correct	7 ms	15956 KB	Output is correct
13	Correct	7 ms	15964 KB	Output is correct
14	Correct	7 ms	15920 KB	Output is correct
15	Correct	7 ms	15964 KB	Output is correct
16	Correct	7 ms	15956 KB	Output is correct
17	Correct	7 ms	15884 KB	Output is correct
18	Correct	7 ms	15956 KB	Output is correct
19	Correct	7 ms	15904 KB	Output is correct
20	Correct	7 ms	15956 KB	Output is correct
21	Correct	8 ms	15956 KB	Output is correct
22	Correct	8 ms	15856 KB	Output is correct
23	Correct	8 ms	15956 KB	Output is correct
24	Correct	9 ms	15956 KB	Output is correct
25	Correct	9 ms	16000 KB	Output is correct
26	Correct	8 ms	15976 KB	Output is correct
27	Correct	10 ms	15944 KB	Output is correct
28	Correct	8 ms	15956 KB	Output is correct
29	Correct	8 ms	15956 KB	Output is correct
30	Correct	8 ms	15956 KB	Output is correct
31	Correct	9 ms	15956 KB	Output is correct
32	Correct	9 ms	15976 KB	Output is correct
33	Correct	39 ms	27864 KB	Output is correct
34	Correct	43 ms	27916 KB	Output is correct
35	Correct	158 ms	58276 KB	Output is correct
36	Correct	148 ms	58116 KB	Output is correct
37	Correct	77 ms	26072 KB	Output is correct
38	Correct	84 ms	38832 KB	Output is correct
39	Correct	31 ms	25776 KB	Output is correct
40	Correct	136 ms	53280 KB	Output is correct
41	Correct	48 ms	25892 KB	Output is correct
42	Correct	65 ms	25916 KB	Output is correct
43	Correct	125 ms	53540 KB	Output is correct
44	Correct	127 ms	53656 KB	Output is correct

Subtask #5

23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	15956 KB	Output is correct
2	Correct	6 ms	15956 KB	Output is correct
3	Correct	6 ms	15964 KB	Output is correct
4	Correct	9 ms	15896 KB	Output is correct
5	Correct	7 ms	15876 KB	Output is correct
6	Correct	7 ms	15960 KB	Output is correct
7	Correct	7 ms	15956 KB	Output is correct
8	Correct	7 ms	15964 KB	Output is correct
9	Correct	7 ms	15892 KB	Output is correct
10	Correct	7 ms	15904 KB	Output is correct
11	Correct	7 ms	15956 KB	Output is correct
12	Correct	7 ms	15960 KB	Output is correct
13	Correct	7 ms	15884 KB	Output is correct
14	Correct	7 ms	15956 KB	Output is correct
15	Correct	7 ms	15852 KB	Output is correct
16	Correct	6 ms	15956 KB	Output is correct
17	Correct	7 ms	15964 KB	Output is correct
18	Correct	7 ms	15956 KB	Output is correct
19	Correct	8 ms	15956 KB	Output is correct
20	Correct	7 ms	15956 KB	Output is correct
21	Correct	7 ms	15956 KB	Output is correct
22	Correct	7 ms	15956 KB	Output is correct
23	Correct	7 ms	16008 KB	Output is correct
24	Correct	8 ms	16000 KB	Output is correct
25	Correct	8 ms	15956 KB	Output is correct
26	Correct	7 ms	15956 KB	Output is correct
27	Correct	9 ms	15956 KB	Output is correct
28	Correct	8 ms	15956 KB	Output is correct
29	Correct	7 ms	15956 KB	Output is correct
30	Correct	8 ms	15956 KB	Output is correct
31	Correct	8 ms	15956 KB	Output is correct
32	Correct	9 ms	15976 KB	Output is correct
33	Correct	507 ms	52016 KB	Output is correct
34	Correct	297 ms	60804 KB	Output is correct
35	Correct	332 ms	52112 KB	Output is correct
36	Correct	359 ms	55884 KB	Output is correct
37	Correct	42 ms	27828 KB	Output is correct
38	Correct	42 ms	27932 KB	Output is correct
39	Correct	159 ms	58208 KB	Output is correct
40	Correct	157 ms	58188 KB	Output is correct
41	Correct	90 ms	26020 KB	Output is correct
42	Correct	103 ms	38816 KB	Output is correct
43	Correct	29 ms	25788 KB	Output is correct
44	Correct	159 ms	53208 KB	Output is correct
45	Correct	46 ms	25812 KB	Output is correct
46	Correct	62 ms	26148 KB	Output is correct
47	Correct	133 ms	53644 KB	Output is correct
48	Correct	139 ms	53656 KB	Output is correct
49	Correct	138 ms	30848 KB	Output is correct
50	Correct	141 ms	30884 KB	Output is correct
51	Correct	273 ms	60028 KB	Output is correct
52	Correct	228 ms	59612 KB	Output is correct
53	Correct	537 ms	29168 KB	Output is correct
54	Correct	248 ms	42684 KB	Output is correct
55	Correct	120 ms	26908 KB	Output is correct
56	Correct	213 ms	55076 KB	Output is correct
57	Correct	300 ms	27496 KB	Output is correct
58	Correct	450 ms	28044 KB	Output is correct
59	Correct	134 ms	53604 KB	Output is correct