Submission #852054

#	Time	Username	Problem	Language	Result	Execution time	Memory
852054		ntkphong	Horses (IOI15_horses)	C++14	100 / 100	185 ms	67440 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
 
const long long lim = 1e9 + 1;
const long long mod = 1e9 + 7;
const int mxN = 5e5 + 10;
 
int n;
long long aX[mxN], aY[mxN];
 
long long mul(long long x, long long y) {
    return min(x * y, lim);
}
 
struct Node {
    int id;
    long long p, s;
    long long np, ns;
    
    friend Node operator + (Node a, Node b) {
        Node c;
        
        long long suffix = mul(a.s, b.p);
        if(aY[a.id] > mul(suffix, aY[b.id])) {
            c.id = a.id;
            c.p = a.p;
            c.s = mul(a.s, mul(b.p, b.s));
            c.np = a.np;
            c.ns = a.ns * b.np % mod * b.ns % mod;
        } else {
            c.id = b.id;
            c.p = mul(mul(a.p, a.s), b.p);
            c.s = b.s;
            c.np = a.np * a.ns % mod * b.np % mod;
            c.ns = b.ns;
        }
        
        return c;
    }
} ST[mxN << 2];
 
void build(int id, int l, int r) {
    if(l == r) {
        ST[id] = {l, aX[l], 1, aX[l], 1};
        return ;
    }
    
    int mid = (l + r) / 2;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    
    ST[id] = ST[id * 2] + ST[id * 2 + 1];   
}
 
void update(int id, int l, int r, int x) {
    if(r < x || x < l) return ;
    if(l == r) {
        ST[id] = {l, aX[l], 1, aX[l], 1};
        return ;
    }
    
    int mid = (l + r) / 2;
    update(id * 2, l, mid, x);
    update(id * 2 + 1, mid + 1, r, x);
    
    ST[id] = ST[id * 2] + ST[id * 2 + 1];
}
 
int init(int N, int X[], int Y[]) {
    n = N;
    for(int i = 0; i < N; i ++) aX[i] = X[i];
    for(int i = 0; i < N; i ++) aY[i] = Y[i];
    
    build(1, 0, N - 1);
    return ST[1].np * aY[ST[1].id] % mod;
}
 
int updateX(int pos, int val) {
    aX[pos] = val;
    update(1, 0, n - 1, pos);
    return ST[1].np * aY[ST[1].id] % mod;
}
 
int updateY(int pos, int val) {
    aY[pos] = val;
    update(1, 0, n - 1, pos);
    return ST[1].np * aY[ST[1].id] % mod;
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:76:36: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   76 |     return ST[1].np * aY[ST[1].id] % mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:82:36: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   82 |     return ST[1].np * aY[ST[1].id] % mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:88:36: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   88 |     return ST[1].np * aY[ST[1].id] % mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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