Submission #438035

#	Time	Username	Problem	Language	Result	Execution time	Memory
438035		illyakr	Horses (IOI15_horses)	C++14	54 / 100	1590 ms	21224 KiB

horses

#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
#define ll long long
const ll mod = 1000000007;
const ll mx = 1000000018;

ll n;
ll x[501010], y[501010];
ll t[2010101];
void build(int v, int vl, int vr) {
    if (vl == vr) {
        t[v] = x[vl] % mod;
        return;
    }
    int vm = (vl + vr) / 2;
    build(2 * v, vl, vm);
    build(2 * v + 1, vm + 1, vr);
    t[v] = (t[2 * v] * t[2 * v + 1]) % mod;
}
void upd(int v, int vl, int vr, int pos, ll val) {
    if (vl == vr) {
        t[v] = val % mod;
        return;
    }
    int vm = (vl + vr) / 2;
    if (pos <= vm)upd(2 * v, vl, vm, pos, val);
    else upd(2 * v + 1, vm + 1, vr, pos, val);
    t[v] = (t[2 * v] * t[2 * v + 1]) % mod;
}
ll gt(int v, int vl, int vr, int l, int r) {
    if (l <= vl && vr <= r)return t[v] % mod;
    if (r < vl || vr < l)return 1ll;
    int vm = (vl + vr) / 2;
    return (gt(2 * v, vl, vm, l, r) * gt(2 * v + 1, vm + 1, vr, l, r)) % mod;
}

int gt() {
    ll cnt = y[n - 1];
    ll last = n - 1;
    for (int i = n - 1; i > 0; i--) {
        if (x[i] > mx / cnt)cnt = mx;
        else cnt *= x[i];

        if (cnt < y[i - 1]){last = i - 1;cnt = y[i - 1];}

        if (cnt == mx)break;
    }
    ll d = gt(1, 0, n - 1, 0, last);
    return ((d % mod) * (y[last] % mod)) % mod;
}
int init(int N, int X[], int Y[]) {
	n = N;
	for (ll i = 0; i < n; i++) {
        x[i] = X[i];
        y[i] = Y[i];
	}
	build(1, 0, n - 1);
    return gt();
}

int updateX(int pos, int val) {
    x[pos] = val;
    upd(1, 0, n - 1, pos, val);
    if (val == 0)exit(1);
	return gt();
}

int updateY(int pos, int val) {
    y[pos] = val;
	return gt();
}

Compilation message (stderr)

horses.cpp: In function 'int gt()':
horses.cpp:41:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   41 |     for (int i = n - 1; i > 0; i--) {
      |                  ~~^~~
horses.cpp:49:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   49 |     ll d = gt(1, 0, n - 1, 0, last);
      |                     ~~^~~
horses.cpp:49:31: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   49 |     ll d = gt(1, 0, n - 1, 0, last);
      |                               ^~~~
horses.cpp:50:42: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   50 |     return ((d % mod) * (y[last] % mod)) % mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:58:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   58 |  build(1, 0, n - 1);
      |              ~~^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:64:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   64 |     upd(1, 0, n - 1, pos, val);
      |               ~~^~~

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