Submission #274417

#	Time	Username	Problem	Language	Result	Execution time	Memory
274417		A02	Horses (IOI15_horses)	C++14	0 / 100	447 ms	72760 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 updateMaxSegTree(vector<pair<long long, int> > &tree, int p, long long t){

    int N = tree.size() / 2;

    tree[p + N].first = t;

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

        tree[p].second = tree[2 * p + 1].second;

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

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

    }

}

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

    int N = tree.size() / 2;

    long long total = -1;
    int answer = -1;

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

        if (l % 2 == 1){

            if (tree[l].second > answer){
                answer = tree[l].second;
            }

            total = (max(total, tree[l++].first));
        }
        if (r % 2 == 1){

            if (tree[r - 1].second > answer){
                answer = tree[r - 1].second;
            }

            total = (max(total, tree[--r].first));
        }

    }

    return make_pair(total, answer);
}

vector<long long> mod_seg_tree;
vector<pair<long long, int> > max_seg_tree;
vector<long long> Xi;
vector<long long> Yi;
set<int> reduced_sequence;

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

    mod_seg_tree = vector<long long> (2 * N, 1);
    max_seg_tree = vector<pair<long long, int> > (2 * N, make_pair(0, 0));

    for (int i = 0; i < N; i++){
        max_seg_tree[i + N].second = i;
    }

    for (int i = 0; i < N; i++){
        Xi.push_back(X[i]);
        Yi.push_back(Y[i]);
        updateModSegTree(mod_seg_tree, i, X[i]);
        updateMaxSegTree(max_seg_tree, i, Y[i]);
    }

    bool is_current_one = false;
    int s_index = 0;

    for (int i = 0; i < N; i++){

        if (is_current_one){
            if (Xi[i] == 1){
            } else {
                reduced_sequence.insert(s_index);
                reduced_sequence.insert(i);
            }
        } else {

            if (Xi[i] == 1){
                s_index = i;
                is_current_one = true;
            } else {
                reduced_sequence.insert(i);
            }

        }

    }

    if (is_current_one){
        reduced_sequence.insert(s_index);
    }

    long long best = Yi[N - 1];
    int b_index = N - 1;
    int c_index = N - 1;
    long long h_threshold = 1;
    set<int>::reverse_iterator it = reduced_sequence.rbegin();

    while(h_threshold * best < prime && *(it) != 0){

        it++;

        int n_index = (*it);
        //cout << n_index << ' ' << Xi[n_index + 1] << ' ' << Xi[n_index] << endl;
        if (Xi[n_index] != 1){

            h_threshold *= Xi[n_index + 1];
            if (Yi[n_index] > best * h_threshold){
                best = Yi[n_index];
                b_index = n_index;
                h_threshold = 1;
            }

        } else {

            pair<long long, int> m = queryMaxSegTree(max_seg_tree, n_index, c_index);
            //cout << m.first << ' ' << m.second << ' ' <<  best << ' ' << h_threshold << endl;
            if (m.first > h_threshold * best){
                best = m.first;
                b_index = m.second;
                h_threshold = 1;
            }

        }

        c_index = n_index;

    }

    return (queryModSegTree(mod_seg_tree, 0, b_index + 1) * Yi[b_index]) % prime;
}

int updateX(int pos, int val) {

    int N = mod_seg_tree.size() / 2;

    if (Xi[pos] != val){
        updateModSegTree(mod_seg_tree, pos, val * mod_exp(val, prime - 1));

        if (pos == 0){

            if (val == 1){
                if (Xi[pos + 1] == 1){
                    reduced_sequence.erase(pos + 1);
                }
            }

            if (Xi[pos] == 1){
                if (Xi[pos + 1] == 1){
                    reduced_sequence.insert(pos + 1);
                }
            }

        }
        if (pos == N - 1){

            if (val == 1){
                if (Xi[pos - 1] == 1){
                    reduced_sequence.erase(pos);
                }
                if (Xi[pos + 1] == 1){
                    reduced_sequence.erase(pos + 1);
                }
            }

            if (Xi[pos] == 1){
                if (Xi[pos + 1] == 1){
                    reduced_sequence.insert(pos + 1);
                }
                reduced_sequence.insert(pos);
            }

        }


        Xi[pos] = val;
    }

    long long best = Yi[N - 1];
    int b_index = N - 1;
    int c_index = N - 1;
    long long h_threshold = 1;
    set<int>::reverse_iterator it = reduced_sequence.rbegin();

    while(h_threshold * best < prime && *(it) != 0){

        it++;

        int n_index = (*it);
        //cout << n_index << ' ' << Xi[n_index + 1] << ' ' << Xi[n_index] << endl;
        if (Xi[n_index] != 1){

            h_threshold *= Xi[n_index + 1];
            if (Yi[n_index] > best * h_threshold){
                best = Yi[n_index];
                b_index = n_index;
                h_threshold = 1;
            }

        } else {

            pair<long long, int> m = queryMaxSegTree(max_seg_tree, n_index, c_index);
            //cout << m.first << ' ' << m.second << ' ' <<  best << ' ' << h_threshold << endl;
            if (m.first > h_threshold * best){
                best = m.first;
                b_index = m.second;
                h_threshold = 1;
            }

        }

        c_index = n_index;

    }

    return (queryModSegTree(mod_seg_tree, 0, b_index + 1) * Yi[b_index]) % prime;
}

int updateY(int pos, int val) {

    int N = max_seg_tree.size() / 2;

    updateMaxSegTree(max_seg_tree, pos, val);

    Yi[pos] = val;

    long long best = Yi[N - 1];
    int b_index = N - 1;
    int c_index = N - 1;
    long long h_threshold = 1;
    set<int>::reverse_iterator it = reduced_sequence.rbegin();

    while(h_threshold * best < prime && *(it) != 0){

        it++;

        int n_index = (*it);
        //cout << n_index << ' ' << Xi[n_index + 1] << ' ' << Xi[n_index] << endl;
        if (Xi[n_index] != 1){

            h_threshold *= Xi[n_index + 1];
            if (Yi[n_index] > best * h_threshold){
                best = Yi[n_index];
                b_index = n_index;
                h_threshold = 1;
            }

        } else {

            pair<long long, int> m = queryMaxSegTree(max_seg_tree, n_index, c_index);
            //cout << m.first << ' ' << m.second << ' ' <<  best << ' ' << h_threshold << endl;
            if (m.first > h_threshold * best){
                best = m.first;
                b_index = m.second;
                h_threshold = 1;
            }

        }

        c_index = n_index;

    }

    return (queryModSegTree(mod_seg_tree, 0, b_index + 1) * Yi[b_index]) % 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 updateMaxSegTree(std::vector<std::pair<long long int, int> >&, int, long long int)':
horses.cpp:68:25: warning: conversion from 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   68 |     int N = tree.size() / 2;
      |             ~~~~~~~~~~~~^~~
horses.cpp: In function 'std::pair<long long int, int> queryMaxSegTree(std::vector<std::pair<long long int, int> >&, int, int)':
horses.cpp:88:25: warning: conversion from 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   88 |     int N = tree.size() / 2;
      |             ~~~~~~~~~~~~^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:204:74: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  204 |     return (queryModSegTree(mod_seg_tree, 0, b_index + 1) * Yi[b_index]) % prime;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:209:33: warning: conversion from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  209 |     int N = mod_seg_tree.size() / 2;
      |             ~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp:290:74: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  290 |     return (queryModSegTree(mod_seg_tree, 0, b_index + 1) * Yi[b_index]) % prime;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:295:33: warning: conversion from 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  295 |     int N = max_seg_tree.size() / 2;
      |             ~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp:338:74: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  338 |     return (queryModSegTree(mod_seg_tree, 0, b_index + 1) * Yi[b_index]) % prime;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~

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