oj.uz

Submission #735542

# Submission time Handle Problem Language Result Execution time Memory
735542 2023-05-04T10:10:03 Z sandry24 Horses (IOI15_horses) C++17
0 / 100
 104 ms 49680 KB 
#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define pb push_back
#define mp make_pair
#define f first
#define s second

const int mod = 1e9+7;
const int maxn = 500005;

struct node {
    double logsum;
    double bestlogsum;
    ll mult;
    ll bestmult;
};

int n;
node st[4*maxn];
ll x[maxn], y[maxn];

void combine(int v, int l, int r){
    st[v].logsum = st[l].logsum + st[r].logsum;
    st[v].mult = (st[l].mult * st[r].mult) % mod;
    if(st[l].bestlogsum > st[l].logsum + st[r].bestlogsum){
        st[v].bestlogsum = st[l].bestlogsum;
        st[v].bestmult = st[l].bestmult;
    } else {
        st[v].bestlogsum = st[l].logsum + st[r].bestlogsum;
        st[v].bestmult = (st[l].mult * st[l].bestmult) % mod;
    }
}

void build(int v, int tl, int tr){
    if(tl == tr){
        st[v].logsum = log10(x[tl]);
        st[v].mult = x[tl];
        st[v].bestlogsum = st[v].logsum + log10(y[tl]);
        st[v].bestmult = (st[v].mult * y[tl]) % mod;
    } else {
        int tm = (tl+tr)/2;
        build(v*2, tl, tm);
        build(v*2+1, tm+1, tr);
        combine(v, v*2, v*2+1);
    }
}

void update(int v, int tl, int tr, int pos, int val){
    if(tl == tr){
        st[v].logsum = log10(x[tl]);
        st[v].mult = x[tl];
        st[v].bestlogsum = st[v].logsum + log10(y[tl]);
        st[v].bestmult = (st[v].mult * y[tl]) % mod;
    } else {
        int tm = (tl+tr)/2;
        if(pos <= tm)
            update(v*2, tl, tm, pos, val);
        else
            update(v*2+1, tm+1, tr, pos, val);
        combine(v, v*2, v*2+1);
    }
}

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];
    build(1, 0, n-1);
    return st[1].bestmult;
}

int updateX(int pos, int val){
    x[pos] = val;
    update(1, 0, n-1, pos, val);
    return st[1].bestmult;
}

int updateY(int pos, int val){
    y[pos] = val;
    update(1, 0, n-1, pos, val);
    return st[1].bestmult;
}

Compilation message

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:76:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   76 |     return st[1].bestmult;
      |            ~~~~~~^~~~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:82:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   82 |     return st[1].bestmult;
      |            ~~~~~~^~~~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:88:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   88 |     return st[1].bestmult;
      |            ~~~~~~^~~~~~~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 104 ms 49680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -