Submission #597738

#	Time	Username	Problem	Language	Result	Execution time	Memory
597738		PiejanVDC	Horses (IOI15_horses)	C++17	100 / 100	762 ms	119756 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;

vector<long long>x,y;

long long mod = (long long)1000000007;

int last;
int ans;

int l,r;

vector<long long>mul(8*500000), correct_mul(8*500000), best(8*500000);

void build(int i, int j, int p) {
    if(i == j) {
        mul[p] = correct_mul[p] = x[i];
        return;
    }
    int mid = (i+j)/2;
    build(i, mid, 2*p);
    build(mid+1, j, 2*p+1);
    mul[p] = mul[2*p] * mul[2*p+1];
    mul[p] = min(mul[p], (long long)1e9+5);
    correct_mul[p] = correct_mul[2*p] * correct_mul[2*p+1];
    correct_mul[p] %= mod;
}

long long get_mul(int i, int j, int p) {
    if(i > r || j < l)
        return 1;
    if(i >= l && j <= r)
        return mul[p];
    int mid = (i+j)/2;
    return min(get_mul(i, mid, 2*p) * get_mul(mid+1, j, 2*p+1), (long long)1e9+5);
}

long long get_correct_mul(int i, int j, int p) {
    if(i > r || j < l)
        return 1;
    if(i >= l && j <= r)
        return correct_mul[p];
    int mid = (i+j)/2;
    return (get_correct_mul(i, mid, 2*p) * get_correct_mul(mid+1, j, 2*p+1))%mod;
}

void update(int i, int j, int p) {
    if(i > l || j < l)
        return;
    if(i == j) {
        mul[p] = correct_mul[p] = x[i];
        return;
    }
    int mid = (i+j)/2;
    update(i, mid, 2*p);
    update(mid+1, j, 2*p+1);
    mul[p] = mul[2*p] * mul[2*p+1];
    mul[p] = min(mul[p], (long long)1e9+5);
    correct_mul[p] = correct_mul[2*p] * correct_mul[2*p+1];
    correct_mul[p] %= mod;
}

void buld(int i, int j, int p) {
    int n = x.size();
    if(i == j) {
        best[p] = i;
        return;
    }
    int mid = (i+j)/2;
    buld(i, mid, 2*p);
    buld(mid+1, j, 2*p+1);
    l = best[2*p]+1, r = best[2*p+1];
    if(y[best[2*p]] >= get_mul(0, n-1, 1) * y[best[2*p+1]])
        best[p] = best[2*p];
    else
        best[p] = best[2*p+1];
}

void updQ(int i, int j, int p) {
    int n = x.size();
    if(i > r || j < l)
        return;
    if(i == j)
        return;
    int mid = (i+j)/2;
    updQ(i, mid, 2*p);
    updQ(mid+1, j, 2*p+1);
    l = best[2*p]+1, r = best[2*p+1];
    if(y[best[2*p]] >= get_mul(0, n-1, 1) * y[best[2*p+1]])
        best[p] = best[2*p];
    else
        best[p] = best[2*p+1];
}

int calc(int i) {
    int n = x.size();
    l = 0, r = i;
    long long c = get_correct_mul(0, n-1, 1);
    c *= y[i];
    c %= mod;
    return c;
}

int init(int n, int X[], int Y[]) {
    for(int i = 0 ; i < n ; i++)
        x.push_back(X[i]), y.push_back(Y[i]);
    build(0, n-1, 1);
    buld(0, n-1, 1);
    return calc(best[1]);
}

int updateX(int p, int val) {
    int n = (int)x.size();
    x[p] = val;
    l = p, r = p;
    update(0, n-1, 1);
    updQ(0, n-1, 1);
    return calc(best[1]);
}

int updateY(int p, int val) {
    int n = (int)x.size();
    y[p] = val;
    l = p, r = p;
    update(0, n-1, 1);
    updQ(0, n-1, 1);
    return calc(best[1]);
}

Compilation message (stderr)

horses.cpp: In function 'void buld(int, int, int)':
horses.cpp:65:19: warning: conversion from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   65 |     int n = x.size();
      |             ~~~~~~^~
horses.cpp:73:18: 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]
   73 |     l = best[2*p]+1, r = best[2*p+1];
horses.cpp:73:36: 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]
   73 |     l = best[2*p]+1, r = best[2*p+1];
      |                                    ^
horses.cpp: In function 'void updQ(int, int, int)':
horses.cpp:81:19: warning: conversion from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   81 |     int n = x.size();
      |             ~~~~~~^~
horses.cpp:89:18: 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]
   89 |     l = best[2*p]+1, r = best[2*p+1];
horses.cpp:89:36: 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]
   89 |     l = best[2*p]+1, r = best[2*p+1];
      |                                    ^
horses.cpp: In function 'int calc(int)':
horses.cpp:97:19: warning: conversion from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   97 |     int n = x.size();
      |             ~~~~~~^~
horses.cpp:102:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  102 |     return c;
      |            ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:110:24: 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]
  110 |     return calc(best[1]);
      |                        ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:119:24: 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 |     return calc(best[1]);
      |                        ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:128:24: 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]
  128 |     return calc(best[1]);
      |                        ^

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