Submission #996424

#	Time	Username	Problem	Language	Result	Execution time	Memory
996424		phoenix	Horses (IOI15_horses)	C++17	100 / 100	227 ms	41556 KiB

horses

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

using namespace std;
using ll = long long;

const int MOD = 1e9 + 7;

const int N = (1 << 19);
int n;
ll y[N];

int mx[2 * N];

struct Z {
    bool over = 0;
    ll x = 1;
};
Z t[2 * N];
void updX(int pos, int val) {
    for(t[pos += N].x = val; pos > 1; pos >>= 1) {
        t[pos >> 1].over = (t[pos].over | t[(pos ^ 1)].over | (t[pos].x * t[(pos ^ 1)].x >= MOD));
        t[pos >> 1].x = (t[pos].x * t[(pos ^ 1)].x) % MOD;
    }
}
Z get(int ql, int qr) {
    Z res;
    for(ql += N, qr += N + 1; ql < qr; ql >>= 1, qr >>= 1) {
        if(ql & 1) {
            res.over = (res.over | t[ql].over | (res.x * t[ql].x >= MOD));
            res.x = (res.x * t[ql].x) % MOD;
            ql++;
        }   
        if(qr & 1) {
            qr--;
            res.over = (res.over | t[qr].over | (res.x * t[qr].x >= MOD));
            res.x = (res.x * t[qr].x) % MOD;
        }
    }
    return res;
}
void build(int l = 0, int r = N - 1, int v = 1) {
    if(l == r) {
        mx[v] = l;
        return; 
    }
    int m = (l + r) / 2;
    build(l, m, 2 * v);
    build(m + 1, r, 2 * v + 1);
    Z x = get(mx[2 * v] + 1, mx[2 * v + 1]);
    mx[v] = mx[2 * v + (x.over || x.x * y[mx[2 * v + 1]] >= y[mx[2 * v]])];
}
void update(int pos) {
    for(pos += N, pos >>= 1; pos; pos >>= 1) {
        Z x = get(mx[2 * pos] + 1, mx[2 * pos + 1]);
        mx[pos] = mx[2 * pos + (x.over || x.x * y[mx[2 * pos + 1]] >= y[mx[2 * pos]])];
    }
}

int init(int N, int X[], int Y[]) {
    n = N;
    for(int i = 0; i < n; i++) {
        y[i] = Y[i];
        updX(i, X[i]);
    }
    build();
    return (y[mx[1]] * get(0, mx[1]).x) % MOD;
}

int updateX(int pos, int val) {
    updX(pos, val);
    update(pos);
    return (y[mx[1]] * get(0, mx[1]).x) % MOD;
}

int updateY(int pos, int val) {
    y[pos] = val;
    update(pos);
    return (y[mx[1]] * get(0, mx[1]).x) % MOD;
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:60:14: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   60 | int init(int N, int X[], int Y[]) {
      |          ~~~~^
horses.cpp:9:11: note: shadowed declaration is here
    9 | const int N = (1 << 19);
      |           ^
horses.cpp:67:41: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   67 |     return (y[mx[1]] * get(0, mx[1]).x) % MOD;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:73:41: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   73 |     return (y[mx[1]] * get(0, mx[1]).x) % MOD;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:79:41: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   79 |     return (y[mx[1]] * get(0, mx[1]).x) % MOD;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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