Submission #330952

#	Time	Username	Problem	Language	Result	Execution time	Memory
330952		monkey8	Horses (IOI15_horses)	C++17	100 / 100	1056 ms	62316 KiB

horses

#include "horses.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <cstdio>
#include <utility> 
#include <queue>
#include <math.h>
#include <set>
#include <bitset>
#include <cmath>
#include <bitset>
#include <iterator>
#include <limits>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, int> pdi;
typedef unsigned long long ull;
typedef __uint128_t L;
const ll MOD = 1e9 + 7;
const int MAXN = 500010;
pdi st[MAXN << 2];
double lazy[MAXN << 2];
ll st1[MAXN << 2];
ll lazy1[MAXN << 2];
int xval[MAXN];
int yval[MAXN];
struct FastMod {
    ull b, m;
    FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
    ull reduce(ull a) {
        ull q = (ull)((L(m) * a) >> 64);
        ull r = a - q * b;
        return r >= b ? r - b : r;
    }
};
FastMod F(2);
int left(int p) {
    return (p << 1);
}
int right(int p) {
    return (p << 1) + 1;
}
void build(int p, int L, int R) {
    if(L == R) st[p] = pdi(log2(yval[L]), L);
    else {
        build(left(p), L, (L + R)/2);
        build(right(p), (L + R)/2 + 1, R);
        st[p] = max(st[left(p)], st[right(p)]);
    }
}
void push(int p, int L, int R) {
    st[p].first += lazy[p];
    if(L != R) {
        lazy[left(p)] += lazy[p];
        lazy[right(p)] += lazy[p];
    }
    lazy[p] = 0;
}
void update(int p, int L, int R, int i, int j, double val) {
    push(p, L, R);
    if(i > R || j < L) return;
    if(L >= i && R <= j) {
        lazy[p] += val;
        push(p, L, R);
        return;
    }
    update(left(p), L, (L + R)/2, i, j, val);
    update(right(p), (L + R)/2 + 1, R, i, j, val);
    st[p] = max(st[left(p)], st[right(p)]);
}
pdi query(int p, int L, int R, int i, int j) {
    push(p, L, R);
    if(i > R || j < L) return pdi(-1, -1);
    if(L >= i && R <= j) return st[p];
    return max(query(left(p), L, (L + R)/2, i, j), query(right(p), (L + R)/2 + 1, R, i, j));
}
void build1(int p, int L, int R) {
    lazy1[p] = 1;
    if(L == R) st1[p] = yval[L];
    else {
        build1(left(p), L, (L + R)/2);
        build1(right(p), (L + R)/2 + 1, R);
        st1[p] = max(st1[left(p)], st1[right(p)]);
    }
}
void push1(int p, int L, int R) {
    st1[p] = F.reduce(st1[p] * lazy1[p]);
    if(L != R) {
        lazy1[left(p)] = F.reduce(lazy1[left(p)] * lazy1[p]);
        lazy1[right(p)] = F.reduce(lazy1[right(p)] * lazy1[p]);
    }
    lazy1[p] = 1;
}
void update1(int p, int L, int R, int i, int j, ll val) {
    push1(p, L, R);
    if(i > R || j < L) return;
    if(L >= i && R <= j) {
        lazy1[p] = F.reduce(lazy1[p] * val);
        push1(p, L, R);
        return;
    }
    update1(left(p), L, (L + R)/2, i, j, val);
    update1(right(p), (L + R)/2 + 1, R, i, j, val);
    st1[p] = max(st1[left(p)], st1[right(p)]);
}
ll query1(int p, int L, int R, int i) {
    push1(p, L, R);
    if(L == R && i == L) return st1[p];
    if(i < L || i > R) return 0;
    return max(query1(left(p), L, (L + R)/2, i), query1(right(p), (L + R)/2 + 1, R, i));
}
ll poww(ll x, ll y) {
    if(y == 0) return 1;
    if(y == 1) return x;
    ll z = poww(x, y/2);
    if(y % 2 == 0) return F.reduce(z * z);
    return F.reduce(F.reduce(z * z) * x);
}
int N;
int init(int n, int x[], int y[]) {
    F = FastMod(MOD);
    N = n;
    for(int i = 0; i < n; i++)
        yval[i] = y[i];
    build(1, 0, n - 1);
    build1(1, 0, n - 1);
    for(int i = 0; i < n; i++) {
        xval[i] = x[i];
        update(1, 0, n - 1, i, n - 1, log2(x[i]));
        update1(1, 0, n - 1, i, n - 1, x[i]);
    }
    pdi q = query(1, 0, n - 1, 0, n - 1);
    return query1(1, 0, n - 1, q.second);
}
int updateX(int pos, int val) {
    update(1, 0, N - 1, pos, N - 1, log2(val) - log2(xval[pos]));
    update1(1, 0, N - 1, pos, N - 1, F.reduce((ll)val * poww(xval[pos], MOD - 2)));
    xval[pos] = val;
    pdi q = query(1, 0, N - 1, 0, N - 1);
    return query1(1, 0, N - 1, q.second);
}
int updateY(int pos, int val) {
    update(1, 0, N - 1, pos, pos, log2(val) - log2(yval[pos]));
    update1(1, 0, N - 1, pos, pos, F.reduce((ll)val * poww(yval[pos], MOD - 2)));
    yval[pos] = val;
    pdi q = query(1, 0, N - 1, 0, N - 1);
    return query1(1, 0, N - 1, q.second);
}

Compilation message (stderr)

horses.cpp: In constructor 'FastMod::FastMod(ull)':
horses.cpp:33:20: warning: declaration of 'b' shadows a member of 'FastMod' [-Wshadow]
   33 |     FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
      |                    ^
horses.cpp:32:9: note: shadowed declaration is here
   32 |     ull b, m;
      |         ^
horses.cpp: In constructor 'FastMod::FastMod(ull)':
horses.cpp:33:54: warning: declaration of 'b' shadows a member of 'FastMod' [-Wshadow]
   33 |     FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
      |                                                      ^
horses.cpp:32:9: note: shadowed declaration is here
   32 |     ull b, m;
      |         ^
horses.cpp: In constructor 'FastMod::FastMod(ull)':
horses.cpp:33:54: warning: declaration of 'b' shadows a member of 'FastMod' [-Wshadow]
   33 |     FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
      |                                                      ^
horses.cpp:32:9: note: shadowed declaration is here
   32 |     ull b, m;
      |         ^
horses.cpp: In function 'void build(int, int, int)':
horses.cpp:47:31: warning: declaration of 'L' shadows a global declaration [-Wshadow]
   47 | void build(int p, int L, int R) {
      |                               ^
horses.cpp:22:21: note: shadowed declaration is here
   22 | typedef __uint128_t L;
      |                     ^
horses.cpp: In function 'void push(int, int, int)':
horses.cpp:55:30: warning: declaration of 'L' shadows a global declaration [-Wshadow]
   55 | void push(int p, int L, int R) {
      |                              ^
horses.cpp:22:21: note: shadowed declaration is here
   22 | typedef __uint128_t L;
      |                     ^
horses.cpp: In function 'void update(int, int, int, int, int, double)':
horses.cpp:63:58: warning: declaration of 'L' shadows a global declaration [-Wshadow]
   63 | void update(int p, int L, int R, int i, int j, double val) {
      |                                                          ^
horses.cpp:22:21: note: shadowed declaration is here
   22 | typedef __uint128_t L;
      |                     ^
horses.cpp: In function 'pdi query(int, int, int, int, int)':
horses.cpp:75:44: warning: declaration of 'L' shadows a global declaration [-Wshadow]
   75 | pdi query(int p, int L, int R, int i, int j) {
      |                                            ^
horses.cpp:22:21: note: shadowed declaration is here
   22 | typedef __uint128_t L;
      |                     ^
horses.cpp: In function 'void build1(int, int, int)':
horses.cpp:81:32: warning: declaration of 'L' shadows a global declaration [-Wshadow]
   81 | void build1(int p, int L, int R) {
      |                                ^
horses.cpp:22:21: note: shadowed declaration is here
   22 | typedef __uint128_t L;
      |                     ^
horses.cpp: In function 'void push1(int, int, int)':
horses.cpp:90:31: warning: declaration of 'L' shadows a global declaration [-Wshadow]
   90 | void push1(int p, int L, int R) {
      |                               ^
horses.cpp:22:21: note: shadowed declaration is here
   22 | typedef __uint128_t L;
      |                     ^
horses.cpp: In function 'void update1(int, int, int, int, int, ll)':
horses.cpp:98:55: warning: declaration of 'L' shadows a global declaration [-Wshadow]
   98 | void update1(int p, int L, int R, int i, int j, ll val) {
      |                                                       ^
horses.cpp:22:21: note: shadowed declaration is here
   22 | typedef __uint128_t L;
      |                     ^
horses.cpp: In function 'll query1(int, int, int, int)':
horses.cpp:110:37: warning: declaration of 'L' shadows a global declaration [-Wshadow]
  110 | ll query1(int p, int L, int R, int i) {
      |                                     ^
horses.cpp:22:21: note: shadowed declaration is here
   22 | typedef __uint128_t L;
      |                     ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:137:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  137 |     return query1(1, 0, n - 1, q.second);
      |            ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:144:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  144 |     return query1(1, 0, N - 1, q.second);
      |            ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:151:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  151 |     return query1(1, 0, N - 1, q.second);
      |            ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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