Submission #154140

#	Time	Username	Problem	Language	Result	Execution time	Memory
154140		popovicirobert	Horses (IOI15_horses)	C++14	0 / 100	629 ms	59988 KiB

horses

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

using namespace std;

const int MOD = (int) 1e9 + 7;
const int MAXN = (int) 5e5;

inline int lgput(int a, int b) {
    int ans = 1;
    while(b > 0) {
        if(b & 1) ans = (1LL * ans * a) % MOD;
        b >>= 1;
        a = (1LL * a * a) % MOD;
    }
    return ans;
}

static int X[MAXN + 1], Y[MAXN + 1];
static int n;

struct Node {
    int rem, lazy_rem;
    double mx, lazy;
}aint[4 * MAXN];

inline void refresh(int nod) {
    if(aint[2 * nod + 1].rem * aint[2 * nod + 1].lazy_rem > aint[2 * nod + 2].rem * aint[2 * nod + 2].lazy_rem) {
        aint[nod].mx = aint[2 * nod + 1].mx + aint[2 * nod + 1].lazy;
        aint[nod].rem = (1LL * aint[2 * nod + 1].rem * aint[2 * nod + 1].lazy_rem) % MOD;
    }
    else {
        aint[nod].mx = aint[2 * nod + 2].mx + aint[2 * nod + 2].lazy;
        aint[nod].rem = (1LL * aint[2 * nod + 2].rem * aint[2 * nod + 2].lazy_rem) % MOD;
    }
}

inline void push(int nod) {
    aint[2 * nod + 1].lazy += aint[nod].lazy;
    aint[2 * nod + 2].lazy += aint[nod].lazy;
    aint[nod].lazy = 0;

    aint[2 * nod + 1].lazy_rem = (1LL * aint[2 * nod + 1].lazy_rem * aint[nod].lazy_rem) % MOD;
    aint[2 * nod + 2].lazy_rem = (1LL * aint[2 * nod + 2].lazy_rem * aint[nod].lazy_rem) % MOD;
    aint[nod].lazy_rem = 1;
}

void update(int nod, int left, int right, int l, int r, double val, int rem) {
    if(l <= left && right <= r) {
        aint[nod].lazy += val;
        aint[nod].lazy_rem = (1LL * aint[nod].lazy_rem * rem) % MOD;
        return ;
    }
    push(nod);
    int mid = (left + right) / 2;

    if(l <= mid) update(2 * nod + 1, left, mid, l, r, val, rem);
    if(mid < r) update(2 * nod + 2, mid + 1, right, l, r, val, rem);

    refresh(nod);
}

int init(int N, int x[], int y[]) {
    n = N;
    for(int i = 0; i < 4 * n; i++) {
        aint[i] = {1, 1, 0, 0};
    }
    for(int i = 0; i < n; i++) {
        X[i] = x[i], Y[i] = y[i];
        update(0, 0, n - 1, i, i, log(Y[i]), Y[i]);
        update(0, 0, n - 1, i, n - 1, log(X[i]), X[i]);
    }
	return aint[0].rem;
}

int updateX(int pos, int val) {
    update(0, 0, n - 1, pos, n - 1, -log(X[pos]), lgput(X[pos], MOD - 2));
    X[pos] = val;
    update(0, 0, n - 1, pos, n - 1, log(X[pos]), X[pos]);
	return aint[0].rem;
}

int updateY(int pos, int val) {
    update(0, 0, n - 1, pos, pos, -log(Y[pos]), lgput(Y[pos], MOD - 2));
    Y[pos] = val;
    update(0, 0, n - 1, pos, pos, log(Y[pos]), Y[pos]);
	return aint[0].rem;
}

Compilation message (stderr)

horses.cpp: In function 'int lgput(int, int)':
horses.cpp:12:41: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         if(b & 1) ans = (1LL * ans * a) % MOD;
                         ~~~~~~~~~~~~~~~~^~~~~
horses.cpp:14:27: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         a = (1LL * a * a) % MOD;
             ~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void refresh(int)':
horses.cpp:30:84: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         aint[nod].rem = (1LL * aint[2 * nod + 1].rem * aint[2 * nod + 1].lazy_rem) % MOD;
                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:34:84: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         aint[nod].rem = (1LL * aint[2 * nod + 2].rem * aint[2 * nod + 2].lazy_rem) % MOD;
                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void push(int)':
horses.cpp:43:90: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     aint[2 * nod + 1].lazy_rem = (1LL * aint[2 * nod + 1].lazy_rem * aint[nod].lazy_rem) % MOD;
                                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:44:90: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     aint[2 * nod + 2].lazy_rem = (1LL * aint[2 * nod + 2].lazy_rem * aint[nod].lazy_rem) % MOD;
                                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void update(int, int, int, int, int, double, int)':
horses.cpp:51:63: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         aint[nod].lazy_rem = (1LL * aint[nod].lazy_rem * rem) % MOD;
                              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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