Submission #274198

#	Time	Username	Problem	Language	Result	Execution time	Memory
274198		A02	Horses (IOI15_horses)	C++14	17 / 100	1188 ms	48604 KiB

horses

#include "horses.h"
#include <vector>
#include <algorithm>
#include <set>
#include <utility>
#include <iostream>
#include <math.h>

using namespace std;

long long prime = 1000000007;

long long mod_exp(long long a, long long k){

    if (k == 0){
        return 1;
    }

    if (k == 1){
        return a;
    }

    long long a1 = mod_exp(a, k / 2);

    if (k % 2 == 1){
        return (((a1 * a1) % prime) * a) % prime;
    }

    return (a1 * a1) % prime;
}

void updateModSegTree(vector<long long> &tree, int p, long long t){

    int N = tree.size() / 2;

    tree[p + N] = (tree[p + N] * t) % prime;

    for (p = (p + N) / 2; p > 0; p = p / 2){

        tree[p] = (tree[2 * p] * tree[2 * p + 1]) % prime;

    }

}

long long queryModSegTree(vector<long long> &tree, int l, int r){

    int N = tree.size() / 2;

    long long total = 1;

    for (l += N, r += N; l < r; l /= 2, r /= 2){

        if (l % 2 == 1){
            total = (total * tree[l++]) % prime;
        }
        if (r % 2 == 1){
            total = (total * tree[--r]) % prime;
        }

    }

    return total;
}

void apply(vector<long double> &tree, vector<long double> &delayed, int p, long double t){

    tree[p] += t;

    if (p < delayed.size()){
        delayed[p] += t;
    }

}

void build(vector<long double> &tree, vector<long double> &delayed, int p, vector<int> &answer_node){

    while (p > 1){

        p /= 2;

        answer_node[p] = answer_node[2 * p + 1];
        if (tree[2 * p] > tree[2 * p + 1]){
            answer_node[p] = answer_node[2 * p];
        }

        tree[p] = max(tree[2 * p], tree[2 * p + 1]) + delayed[p];

    }

}

void push(vector<long double> &tree, vector<long double> &delayed, int p){

    int N = tree.size() / 2;

    int h = sizeof(int) * 8 - __builtin_clz(N);

    for (int s = h; s > 0; s--){

        int i = p >> s;

        if (delayed[i] != 0){
            apply(tree, delayed, 2 * i, delayed[i]);
            apply(tree, delayed, 2 * i + 1, delayed[i]);
            delayed[i] = 0;
        }

    }

}

void updateMaxSegTree(vector<long double> &tree, vector<long double> &delayed, int l, int r, long double t, vector<int> &answer_node){

    int n = tree.size() / 2;
    l += n;
    r += n;

    int L = l;
    int R = r;

    for (; l < r; l/=2, r/=2){

        if (l % 2 == 1){
            apply(tree, delayed, l++, t);
        }

        if (r % 2 == 1){
            apply(tree, delayed, --r, t);
        }

    }

    build(tree, delayed, L, answer_node);
    build(tree, delayed, R - 1, answer_node);

}

int queryMaxSegTree(vector<long double> &tree, vector<long double> &delayed, int l, int r, vector<int> &answer_node){

    int N = tree.size() / 2;

    l += N;
    r += N;

    push(tree, delayed, l);
    push(tree, delayed, r - 1);

    long double answer = -1;
    int answer_n = -1;
    for (; l < r; l /= 2, r /= 2){
        if (l % 2 == 1){
            if (tree[l] > answer){
                answer_n = answer_node[l];
            }
            answer = max(answer, tree[l++]);
        }
        if (r % 2 == 1){
            if (tree[r - 1] > answer){
                answer_n = answer_node[r - 1];
            }
            answer = max(answer, tree[--r]);
        }
    }

    //cout << answer << endl;
    return answer_n;
}

vector<long long> mod_seg_tree;
vector<long double> max_seg_tree;
vector<long double> max_seg_tree_delayed;
vector<int> answer_node;
vector<long long> Xi;
vector<long long> Yi;

int init(int N, int X[], int Y[]) {

    mod_seg_tree = vector<long long> (2 * N, 1);

    max_seg_tree = vector<long double> (2 * N, 0.0);
    max_seg_tree_delayed = vector<long double> (N, 0.0);
    answer_node = vector<int> (2 * N, 0);

    for (int i = 0; i < N; i++){
        answer_node[i + N] = i;
        Xi.push_back(X[i]);
        Yi.push_back(Y[i]);
    }

    for (int i = 0; i < N; i++){
        //cout << i << ' ' << X[i] << endl;
        updateModSegTree(mod_seg_tree, i, X[i]);
        //cout << queryModSegTree(mod_seg_tree, 0, 1) << endl;

        updateMaxSegTree(max_seg_tree, max_seg_tree_delayed, i, N, log((long double) X[i]), answer_node);
        updateMaxSegTree(max_seg_tree, max_seg_tree_delayed, i, i + 1, log((long double) Y[i]), answer_node);
    }

    int best = queryMaxSegTree(max_seg_tree, max_seg_tree_delayed, 0, N, answer_node);
    //cout << best << endl;
    long long answer = queryModSegTree(mod_seg_tree, 0, best + 1);
    //cout << 'a' << endl;
    //cout << queryModSegTree(mod_seg_tree, 0, 1) << endl;
    return (answer * Yi[best]) % prime;
}

int updateX(int pos, int val) {

	int N = max_seg_tree.size() / 2;
	updateModSegTree(mod_seg_tree, pos, val * mod_exp(Xi[pos], prime - 1));
	updateMaxSegTree(max_seg_tree, max_seg_tree_delayed, pos, N, log((long double) val) - log((long double) Xi[pos]), answer_node);

	Xi[pos] = val;

    int best = queryMaxSegTree(max_seg_tree, max_seg_tree_delayed, 0, N, answer_node);
    //cout << best << endl;
    long long answer = queryModSegTree(mod_seg_tree, 0, best + 1);
    //cout << 'a' << endl;
    //cout << queryModSegTree(mod_seg_tree, 0, 1) << endl;
    return ((answer * Yi[best]) % prime);
}

int updateY(int pos, int val) {


    int N = max_seg_tree.size() / 2;
    updateMaxSegTree(max_seg_tree, max_seg_tree_delayed, pos, pos + 1, log(val) - log(Yi[pos]), answer_node);

    Yi[pos] = val;

    int best = queryMaxSegTree(max_seg_tree, max_seg_tree_delayed, 0, N, answer_node);
    //cout << best << endl;
    long long answer = queryModSegTree(mod_seg_tree, 0, best + 1);
    //cout << 'a' << endl;
    //cout << queryModSegTree(mod_seg_tree, 0, 1) << endl;
    return ((answer * Yi[best]) % prime);
}

Compilation message (stderr)

horses.cpp: In function 'void updateModSegTree(std::vector<long long int>&, int, long long int)':
horses.cpp:34:25: warning: conversion from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   34 |     int N = tree.size() / 2;
      |             ~~~~~~~~~~~~^~~
horses.cpp: In function 'long long int queryModSegTree(std::vector<long long int>&, int, int)':
horses.cpp:48:25: warning: conversion from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   48 |     int N = tree.size() / 2;
      |             ~~~~~~~~~~~~^~~
horses.cpp: In function 'void apply(std::vector<long double>&, std::vector<long double>&, int, long double)':
horses.cpp:70:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     if (p < delayed.size()){
      |         ~~^~~~~~~~~~~~~~~~
horses.cpp: In function 'void push(std::vector<long double>&, std::vector<long double>&, int)':
horses.cpp:95:25: warning: conversion from 'std::vector<long double>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   95 |     int N = tree.size() / 2;
      |             ~~~~~~~~~~~~^~~
horses.cpp:97:29: warning: conversion from 'long unsigned int' to 'int' may change value [-Wconversion]
   97 |     int h = sizeof(int) * 8 - __builtin_clz(N);
      |             ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
horses.cpp: In function 'void updateMaxSegTree(std::vector<long double>&, std::vector<long double>&, int, int, long double, std::vector<int>&)':
horses.cpp:115:25: warning: conversion from 'std::vector<long double>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  115 |     int n = tree.size() / 2;
      |             ~~~~~~~~~~~~^~~
horses.cpp: In function 'int queryMaxSegTree(std::vector<long double>&, std::vector<long double>&, int, int, std::vector<int>&)':
horses.cpp:141:25: warning: conversion from 'std::vector<long double>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  141 |     int N = tree.size() / 2;
      |             ~~~~~~~~~~~~^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:205:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  205 |     return (answer * Yi[best]) % prime;
      |            ~~~~~~~~~~~~~~~~~~~~^~~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:210:30: warning: conversion from 'std::vector<long double>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  210 |  int N = max_seg_tree.size() / 2;
      |          ~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp:221:33: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  221 |     return ((answer * Yi[best]) % prime);
      |            ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:227:33: warning: conversion from 'std::vector<long double>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  227 |     int N = max_seg_tree.size() / 2;
      |             ~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp:237:33: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  237 |     return ((answer * Yi[best]) % prime);
      |            ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~

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