제출 #299264

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
299264		Hideo	말 (IOI15_horses)	C++17	37 / 100	827 ms	53240 KiB

horses

#include "horses.h"
//#include "grader.cpp"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define all(s) s.begin(), s.end()
#define pb push_back
#define fr first
#define sc second
#define vl vector < ll >
#define pl pair < ll, ll >

const int MN = 5e5 + 7;
const ll mod = 1e9 + 7;

ll t[4 * MN], m[4 * MN];
ll x[MN], y[MN], pr[MN];
set < int > p;
int n;

void build (int v, int l, int r){
    if (l == r){
        t[v] = x[l];
        m[v] = y[l];
    }
    else {
        int mid = (l + r) >> 1;
        build(v + v, l, mid);
        build(v + v + 1, mid + 1, r);
        t[v] = (t[v + v] * t[v + v + 1]) % mod;
        m[v] = max(m[v + v], m[v + v + 1]);
    }
}

void upd (int v, int l, int r, int pos, ll val){
    if (l == r)
        t[v] = val;
    else {
        int mid = (l + r) >> 1;
        if (pos <= mid)
            upd(v + v, l, mid, pos, val);
        else
            upd(v + v + 1, mid + 1, r, pos, val);
        t[v] = (t[v + v] * t[v + v + 1]) % mod;
    }
}

void upd_m (int v, int l, int r, int pos, ll val){
    if (l == r)
        m[v] = val;
    else {
        int mid = (l + r) >> 1;
        if (pos <= mid)
            upd_m(v + v, l, mid, pos, val);
        else
            upd_m(v + v + 1, mid + 1, r, pos, val);
        m[v] = max(m[v + v], m[v + v + 1]);
    }
}

ll get (int v, int l, int r, int ql, int qr){
    if (ql <= l && r <= qr)
        return t[v];
    if (r < ql || qr < l)
        return 1LL;
    int mid = (l + r) >> 1;
    return (get(v + v, l, mid, ql, qr) * get(v + v + 1, mid + 1, r, ql, qr)) % mod;
}

ll get_m (int v, int l, int r, int ql, int qr){
    if (ql <= l && r <= qr)
        return m[v];
    if (r < ql || qr < l)
        return 1LL;
    int mid = (l + r) >> 1;
    return max(get_m(v + v, l, mid, ql, qr), get_m(v + v + 1, mid + 1, r, ql, qr));
}

int answer(){
    vl v;
    v.clear();
    ll s = 1;
    bool met = false;
    for (int it : p){
        if (s >= mod)
            break;
        int i = -it;
        s *= x[i];
        v.pb(i);
        if (i == 0)
            met = true;
    }
    sort(all(v));
    reverse(all(v));
    ll temp = s;
    int sz = v.size();
    ll mx = 0, yy = 0;
    s = 1;
    for (int i = sz - 2; i >= 0; i--){
        s *= x[v[i]];
        if (i)
            yy = get_m(1, 1, n, v[i], v[i - 1] - 1);
        else
            yy = get_m(1, 1, n, v[i], n);
        mx = max(mx, s * yy);
    }
    if (v[sz - 1] == 0){
        yy = get_m(1, 1, n, 1, n);
        return max(mx, yy) % mod;
    }
    else {
        if (temp < mod && met == true)
            assert(false);
        if (sz > 1)
            yy = get_m(1, 1, n, v[sz - 1], v[sz - 2] - 1);
        else
            yy = get_m(1, 1, n, v[sz - 1], n);
        return (max(mx, yy) % mod * get(1, 1, n, 1, v[sz - 1])) % mod;
    }
}

int init(int N, int X[], int Y[]){
    n = N;
    p.insert(0);
    x[0] = 1LL;
    y[0] = 1LL;
    for (int i = 1; i <= n; i++){
        x[i] = X[i - 1];
        y[i] = Y[i - 1];
        if (x[i] != 1)
            p.insert(-i);
    }
    build(1, 1, n);
    return answer();
}

int updateX(int pos, int val) {
    pos++;
//    if (!pos)
//        assert(false);
    if (x[pos] != 1 && val == 1)
        p.erase(pos);
    else if (x[pos] == 1 && val != 1)
        p.insert(pos);
    upd(1, 1, n, pos, 1LL * val);
    x[pos] = 1LL * val;
    return answer();
}

int updateY(int pos, int val) {
    pos++;
    y[pos] = 1LL * val;
    upd_m(1, 1, n, pos, 1LL * val);
	return answer();
}

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

horses.cpp: In function 'int answer()':
horses.cpp:98:20: warning: conversion from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   98 |     int sz = v.size();
      |              ~~~~~~^~
horses.cpp:104:51: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  104 |             yy = get_m(1, 1, n, v[i], v[i - 1] - 1);
      |                                                   ^
horses.cpp:104:48: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  104 |             yy = get_m(1, 1, n, v[i], v[i - 1] - 1);
horses.cpp:106:40: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  106 |             yy = get_m(1, 1, n, v[i], n);
      |                                        ^
horses.cpp:111:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  111 |         return max(mx, yy) % mod;
      |                ~~~~~~~~~~~~^~~~~
horses.cpp:117:57: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  117 |             yy = get_m(1, 1, n, v[sz - 1], v[sz - 2] - 1);
      |                                                         ^
horses.cpp:117:54: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  117 |             yy = get_m(1, 1, n, v[sz - 1], v[sz - 2] - 1);
horses.cpp:119:45: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  119 |             yy = get_m(1, 1, n, v[sz - 1], n);
      |                                             ^
horses.cpp:120:62: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  120 |         return (max(mx, yy) % mod * get(1, 1, n, 1, v[sz - 1])) % mod;
      |                                                              ^
horses.cpp:120:65: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  120 |         return (max(mx, yy) % mod * get(1, 1, n, 1, v[sz - 1])) % mod;
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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