Submission #597134

#	Time	Username	Problem	Language	Result	Execution time	Memory
597134		PiejanVDC	Horses (IOI15_horses)	C++17	17 / 100	1591 ms	74888 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);

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;
}

int updX(int p) {
    int n = x.size();
    if(p <= last)
        return ans;
    l = last+1, r = p;
    if(get_mul(0, n-1, 1) * y[p] > ans) {
        last = p;
        l = 0, r = p;
        return ans = int((get_correct_mul(0, n-1, 1) * y[last])%mod);
    }
}

int calc();

int updY(int p) {
    int n = x.size();
    if(p == last)
        return calc();
    if(p < last) {
        l = p+1, r = last;
        if(get_mul(0, n-1, 1) * y[last] > y[p])
            return ans;
        else {
            last = p;
            l = 0, r = p;
            return ans = int((get_correct_mul(0, n-1, 1) * y[last])%mod);
        }
    } else {
        l = last+1, r = p;
        if(get_mul(0, n-1, 1) * y[p] > y[last]) {
            last = p;
            l = 0, r = p;
            return ans = int((get_correct_mul(0, n-1, 1) * y[last])%mod);
        } else {
            return ans;
        }
    }
}

int calc() {
    int n = (int)x.size();

    build(0, n-1, 1);

    last = -1;

    bool ok = 1;
    while(ok) {
        ok = 0;
        long long c = 1;
        for(int i = last+1 ; i < n ; i++) {
            c *= x[i];
            c = min(c, (long long)1e9+5);
            if(c * y[i] > (last == -1 ? 0 : y[last])) {
                last = i;
                ok = 1;
                break;
            }
        }
    }

    long long C = 1;
    for(int i = 0 ; i <= last ; i++)
        C *= x[i], C %= mod;
    return ans = int((C * y[last])%mod);
}

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]);
    return calc();
}

int updateX(int p, int val) {
    int n = (int)x.size();
    x[p] = val;
    update(0, n-1, 1);
    return updX(p);
}

int updateY(int p, int val) {
    int n = (int)x.size();
    y[p] = val;
    return updY(p);
}

Compilation message (stderr)

horses.cpp: In function 'int updX(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: In function 'int updY(int)':
horses.cpp:79:19: warning: conversion from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   79 |     int n = x.size();
      |             ~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:145:9: warning: unused variable 'n' [-Wunused-variable]
  145 |     int n = (int)x.size();
      |         ^
horses.cpp: In function 'int updX(int)':
horses.cpp:74:1: warning: control reaches end of non-void function [-Wreturn-type]
   74 | }
      | ^

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