Submission #349213

#	Time	Username	Problem	Language	Result	Execution time	Memory
349213		mjhmjh1104	Horses (IOI15_horses)	C++14	100 / 100	1152 ms	46060 KiB

horses

#include "horses.h"
#include <algorithm>
using namespace std;

const long long MOD = 1e9 + 7;

long long tree_x[1048576];
long long tree_y[1048576];
long long real_x[1048576];
long long real_y[500006];

long long query_x(int i, int b, int e, int l, int r) {
    if (r < b || e < l) return 1;
    if (l <= b && e <= r) return tree_x[i];
    int m = (b + e) / 2;
    return min(query_x(i * 2 + 1, b, m, l, r) * query_x(i * 2 + 2, m + 1, e, l, r), MOD);
}

long long update_x(int i, int b, int e, int p, int v) {
    if (p < b || e < p) return tree_x[i];
    if (b == e) return tree_x[i] = v;
    int m = (b + e) / 2;
    return tree_x[i] = min(update_x(i * 2 + 1, b, m, p, v) * update_x(i * 2 + 2, m + 1, e, p, v), MOD);
}

long long query_rx(int i, int b, int e, int l, int r) {
    if (r < b || e < l) return 1;
    if (l <= b && e <= r) return real_x[i];
    int m = (b + e) / 2;
    return query_rx(i * 2 + 1, b, m, l, r) * query_rx(i * 2 + 2, m + 1, e, l, r) % MOD;
}

long long update_rx(int i, int b, int e, int p, int v) {
    if (p < b || e < p) return real_x[i];
    if (b == e) return real_x[i] = v;
    int m = (b + e) / 2;
    return real_x[i] = update_rx(i * 2 + 1, b, m, p, v) * update_rx(i * 2 + 2, m + 1, e, p, v) % MOD;
}

bool compare(int x, int y) {
    long long t = query_x(0, 0, 524287, x + 1, y);
    if (t == MOD) return true;
    return real_y[x] < t * real_y[y];
}

long long query_y(int i, int b, int e, int l, int r) {
    if (r < b || e < l) return -1;
    if (l <= b && e <= r) return tree_y[i];
    int m = (b + e) / 2;
    int first = query_y(i * 2 + 1, b, m, l, r);
    int second = query_y(i * 2 + 2, m + 1, e, l, r);
    if (first == -1 || second == -1) return first + second + 1;
    if (compare(first, second)) return second;
    return first;
}

long long update_y(int i, int b, int e, int p) {
    if (p < b || e < p) return tree_y[i];
    if (b == e) return tree_y[i];
    int m = (b + e) / 2;
    int first = update_y(i * 2 + 1, b, m, p);
    int second = update_y(i * 2 + 2, m + 1, e, p);
    if (first == -1 || second == -1) return tree_y[i] = first + second + 1;
    if (compare(first, second)) return tree_y[i] = second;
    return tree_y[i] = first;
}

int init(int N, int X[], int Y[]) {
    for (int i = 0; i < N; i++) tree_x[524287 + i] = X[i];
    for (int i = 524286; i >= 0; i--) tree_x[i] = min(tree_x[i * 2 + 1] * tree_x[i * 2 + 2], MOD);
    for (int i = 0; i < N; i++) real_x[524287 + i] = X[i];
    for (int i = 524286; i >= 0; i--) real_x[i] = real_x[i * 2 + 1] * real_x[i * 2 + 2] % MOD;
    for (int i = 0; i < N; i++) real_y[i] = Y[i];
    for (int i = 0; i < 524288; i++) tree_y[524287 + i] = -1;
    for (int i = 0; i < N; i++) tree_y[524287 + i] = i;
    for (int i = 524286; i >= 0; i--) {
        if (compare(tree_y[i * 2 + 1], tree_y[i * 2 + 2])) tree_y[i] = tree_y[i * 2 + 2];
        else tree_y[i] = tree_y[i * 2 + 1];
    }
	int t = tree_y[0];
	return query_rx(0, 0, 524287, 0, t) * real_y[t] % MOD;
}

int updateX(int pos, int val) {
    update_x(0, 0, 524287, pos, val);
    update_rx(0, 0, 524287, pos, val);
    update_y(0, 0, 524287, pos);
    int t = tree_y[0];
	return query_rx(0, 0, 524287, 0, t) * real_y[t] % MOD;
}

int updateY(int pos, int val) {
    real_y[pos] = val;
    update_y(0, 0, 524287, pos);
	int t = tree_y[0];
	return query_rx(0, 0, 524287, 0, t) * real_y[t] % MOD;
}

Compilation message (stderr)

horses.cpp: In function 'long long int query_y(int, int, int, int, int)':
horses.cpp:50:24: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   50 |     int first = query_y(i * 2 + 1, b, m, l, r);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:51:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   51 |     int second = query_y(i * 2 + 2, m + 1, e, l, r);
      |                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'long long int update_y(int, int, int, int)':
horses.cpp:61:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   61 |     int first = update_y(i * 2 + 1, b, m, p);
      |                 ~~~~~~~~^~~~~~~~~~~~~~~~~~~~
horses.cpp:62:26: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   62 |     int second = update_y(i * 2 + 2, m + 1, e, p);
      |                  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:77:37: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   77 |         if (compare(tree_y[i * 2 + 1], tree_y[i * 2 + 2])) tree_y[i] = tree_y[i * 2 + 2];
      |                     ~~~~~~~~~~~~~~~~^
horses.cpp:77:56: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   77 |         if (compare(tree_y[i * 2 + 1], tree_y[i * 2 + 2])) tree_y[i] = tree_y[i * 2 + 2];
      |                                        ~~~~~~~~~~~~~~~~^
horses.cpp:80:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   80 |  int t = tree_y[0];
      |          ~~~~~~~~^
horses.cpp:81:50: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   81 |  return query_rx(0, 0, 524287, 0, t) * real_y[t] % MOD;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:88:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   88 |     int t = tree_y[0];
      |             ~~~~~~~~^
horses.cpp:89:50: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   89 |  return query_rx(0, 0, 524287, 0, t) * real_y[t] % MOD;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:95:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   95 |  int t = tree_y[0];
      |          ~~~~~~~~^
horses.cpp:96:50: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   96 |  return query_rx(0, 0, 524287, 0, t) * real_y[t] % MOD;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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