Submission #408946

#	Time	Username	Problem	Language	Result	Execution time	Memory
408946		dxz05	Horses (IOI15_horses)	C++14	17 / 100	210 ms	146160 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>

typedef long double ld;
typedef long long ll;

using namespace std;

const int MAXN = 2e6 + 3e2;
const int MOD = 1000000007;

int X[MAXN], Y[MAXN];
int N;

ll powmod(ll n, ll k){
    if (k == 0) return 1;
    ll x = powmod(n, k / 2);
    x = x * x % MOD;
    if (k % 2) x = x * n % MOD;
    return x;
}

struct node{
    ll mult = 1;
    ld mx_sum = 0;
    bool isUpdated = false;
    ll mult_val = 1;
    ld add_val = 0;

    node(ll a1, ld a2, bool a3, ll a4, ld a5){
        mult = a1;
        mx_sum = a2;
        isUpdated = a3;
        mult_val = a4;
        add_val = a5;
    }

    node(){};
};

ll pref_mult[MAXN];
ld pref_sum[MAXN];

node t[MAXN];

void combine(node &par, node lf, node rg){
    if (lf.mx_sum < rg.mx_sum) swap(lf, rg);
    par.mx_sum = lf.mx_sum;
    par.mult = lf.mult;
}

void build(int v = 1, int tl = 0, int tr = N - 1){
    if (tl == tr){
        t[v].mult = pref_mult[tl] * Y[tl] % MOD;
        t[v].mx_sum = pref_sum[tl] + log2(Y[tl]);
        return;
    }
    int tm = (tl + tr) >> 1;
    build(v + v, tl, tm);
    build(v + v + 1, tm + 1, tr);
    combine(t[v], t[v + v], t[v + v + 1]);
}

void propagate(int v, int tl, int tr){
    if (!t[v].isUpdated || tl == tr) return;
    int tm = (tl + tr) >> 1;

    t[v + v].mult = t[v + v].mult * t[v].mult_val % MOD;
    t[v + v].mult_val = t[v + v].mult_val * t[v].mult_val % MOD;

    t[v + v + 1].mult = t[v + v + 1].mult * t[v].mult_val % MOD;
    t[v + v + 1].mult_val = t[v + v + 1].mult_val * t[v].mult_val % MOD;

    t[v + v].mx_sum += t[v].add_val;
    t[v + v + 1].mx_sum += t[v].add_val;

    t[v + v].add_val += t[v].add_val;
    t[v + v + 1].add_val += t[v].add_val;

    combine(t[v], t[v + v], t[v + v + 1]);

    t[v].mult_val = 1;
    t[v].add_val = 0;

    t[v].isUpdated = false;
    t[v + v].isUpdated = t[v + v + 1].isUpdated = true;
}

void update(int l, int r, ll mult, ld add, int v = 1, int tl = 0, int tr = N - 1){
    if (l <= tl && tr <= r){
        t[v].mx_sum += add;
        t[v].add_val += add;
        t[v].mult = t[v].mult * mult % MOD;
        t[v].mult_val = t[v].mult_val * mult % MOD;
        t[v].isUpdated = true;
        return;
    }
    if (tl > r || tr < l) return;

    propagate(v, tl, tr);

    int tm = (tl + tr) >> 1;
    update(l, r, mult, add, v + v, tl, tm);
    update(l, r, mult, add, v + v + 1, tm + 1, tr);

    combine(t[v], t[v + v], t[v + v + 1]);
}

node get(int l, int r, int v = 1, int tl = 0, int tr = N - 1){
    if (l <= tl && tr <= r) return t[v];
    if (tl > r || tr < l) return node(0, 0, 0, 0, 0);

    propagate(v, tl, tr);

    int tm = (tl + tr) >> 1;

    node res, lf = get(l, r, v + v, tl, tm), rg = get(l, r, v + v + 1, tm + 1, tr);
    combine(res, lf, rg);

    return res;
}

int init(int _N, int _X[], int _Y[]) {
    N = _N;
    for (int i = 0; i < N; i++){
        X[i] = _X[i], Y[i] = _Y[i];
        pref_mult[i] = (i > 0 ? pref_mult[i - 1] : 1) * X[i] % MOD;
        pref_sum[i] = (i > 0 ? pref_sum[i - 1] : 0) + log2(X[i]);
    }

    build();

	return get(0, N - 1).mult;
}

int updateX(int pos, int val) {
    ll k = val * powmod(X[pos], MOD - 2) % MOD;
    update(pos, N - 1, k, log2(val) - log2(X[pos]));
    X[pos] = val;
	return get(0, N - 1).mult;
}

int updateY(int pos, int val) {
    ll k = val * powmod(Y[pos], MOD - 2);
    update(pos, pos, k, ld(log2(val)) - ld(log2(Y[pos])));
    Y[pos] = val;
	return get(0, N - 1).mult;
}

Compilation message (stderr)

horses.cpp: In function 'void propagate(int, int, int)':
horses.cpp:66:9: warning: unused variable 'tm' [-Wunused-variable]
   66 |     int tm = (tl + tr) >> 1;
      |         ^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:133:23: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  133 |  return get(0, N - 1).mult;
      |         ~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:140:23: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  140 |  return get(0, N - 1).mult;
      |         ~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:147:23: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  147 |  return get(0, N - 1).mult;
      |         ~~~~~~~~~~~~~~^~~~

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