oj.uz

Submission #72719

# Submission time Handle Problem Language Result Execution time Memory
72719 2018-08-26T20:43:44 Z RezwanArefin01 Horses (IOI15_horses) C++17
17 / 100
 229 ms 64368 KB 
#include <bits/stdc++.h>
#include "horses.h"
using namespace std; 

typedef long long ll;

const int N = 5e5 + 10; 
const int mod = 1e9 + 7; 

long double mx[N << 2], a[N], add[N << 2]; 
int prod[N << 2], mul[N << 2], opt[N << 2]; 
int x[N], y[N], n, p[N];

int Pow(int n, int p) {
    int ret = 1; 
    while(p) {
        if(p & 1) ret = (ll) ret * n % mod; 
        n = (ll) n * n % mod; 
        p >>= 1; 
    } return ret;
}
    
void merge(int node) {
    long double a = mx[node << 1], b = mx[node << 1 | 1];
    if(b - a >= 1e-9) mx[node] = b, opt[node] = opt[node << 1 | 1]; 
    else mx[node] = a, opt[node] = opt[node << 1]; 
    prod[node] = (ll) prod[node << 1] * prod[node << 1 | 1] % mod; 
}
    
void build(int node, int l, int r) {
    add[node] = 0, mul[node] = 1; 
    if(l == r) {
        mx[node] = a[l]; 
        prod[node] = p[l]; 
        opt[node] = l; 
        return; 
    } int m = l + r >> 1; 
    build(node << 1, l, m);
    build(node << 1 | 1, m + 1, r); 
    merge(node);
}

void upd(int node, long double A, int B) {
    mx[node] += A; 
    prod[node] = (ll) prod[node] * B % mod; 
}
void shift(int node) {
    if(!add[node] && mul[node] == 1) return; 
    upd(node << 1, add[node], mul[node]); 
    upd(node << 1 | 1, add[node], mul[node]); 
    add[node] = 0, mul[node] = 1; 
}

void update(int node, int l, int r, int i, int j, long double A, int B) {
    if(r < i || l > j) return; 
    if(i <= l && r <= j) {
        upd(node, A, B); 
        return; 
    } shift(node); 
    int m = l + r >> 1;
    update(node << 1, l, m, i, j, A, B); 
    update(node << 1 | 1, m + 1, r, i, j, A, B); 
    merge(node); 
}
int query(int node, int l, int r, int i) {
    if(l == r) return prod[node];
    shift(node); 
    int m = l + r >> 1; 
    if(i <= m) return query(node << 1, l, m, i); 
    else return query(node << 1 | 1, m + 1, r, i); 
}
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]; 
    p[0] = x[0]; a[0] = log(x[0]) + log(y[0]); 
    for(int i = 1; i < N; i++) {
        p[i] = (ll) p[i - 1] * x[i] % mod; 
        a[i] = a[i - 1] - log(y[i - 1]) + log(y[i]) + log(x[i]); 
    }
    build(1, 0, N - 1); 
    int ans = (ll) query(1, 0, n - 1, opt[1]) * y[opt[1]] % mod; 
    return ans; 
}

int updateX(int pos, int val) {	
    update(1, 0, n - 1, pos, n - 1, log(val) - log(x[pos]), (ll) val * Pow(x[pos], mod - 2) % mod); 
    x[pos] = val; 
    int ans = (ll) query(1, 0, n - 1, opt[1]) * y[opt[1]] % mod; 
    return ans;
}

int updateY(int pos, int val) {
    update(1, 0, n - 1, pos, pos, log(val) - log(y[pos]), (ll) val * Pow(y[pos], mod - 2) % mod); 
    y[pos] = val; 
    int ans = (ll) query(1, 0, n - 1, opt[1]) * y[opt[1]] % mod; 
    return ans;
}

Compilation message

horses.cpp: In function 'int Pow(int, int)':
horses.cpp:14:21: warning: declaration of 'p' shadows a global declaration [-Wshadow]
 int Pow(int n, int p) {
                     ^
horses.cpp:12:20: note: shadowed declaration is here
 int x[N], y[N], n, p[N];
                    ^
horses.cpp:14:21: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 int Pow(int n, int p) {
                     ^
horses.cpp:12:17: note: shadowed declaration is here
 int x[N], y[N], n, p[N];
                 ^
horses.cpp:17:38: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
         if(p & 1) ret = (ll) ret * n % mod; 
                         ~~~~~~~~~~~~~^~~~~
horses.cpp:18:24: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
         n = (ll) n * n % mod; 
             ~~~~~~~~~~~^~~~~
horses.cpp: In function 'void merge(int)':
horses.cpp:24:17: warning: declaration of 'a' shadows a global declaration [-Wshadow]
     long double a = mx[node << 1], b = mx[node << 1 | 1];
                 ^
horses.cpp:10:25: note: shadowed declaration is here
 long double mx[N << 2], a[N], add[N << 2]; 
                         ^
horses.cpp:27:61: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     prod[node] = (ll) prod[node << 1] * prod[node << 1 | 1] % mod; 
                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void build(int, int, int)':
horses.cpp:37:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     } int m = l + r >> 1; 
               ~~^~~
horses.cpp: In function 'void upd(int, long double, int)':
horses.cpp:45:38: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     prod[node] = (ll) prod[node] * B % mod; 
                  ~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void update(int, int, int, int, int, long double, int)':
horses.cpp:60:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1;
             ~~^~~
horses.cpp: In function 'int query(int, int, int, int)':
horses.cpp:68:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1; 
             ~~^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:72:33: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int init(int N, int X[], int Y[]) {
                                 ^
horses.cpp:7:11: note: shadowed declaration is here
 const int N = 5e5 + 10; 
           ^
horses.cpp:78:37: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
         p[i] = (ll) p[i - 1] * x[i] % mod; 
                ~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:82:59: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     int ans = (ll) query(1, 0, n - 1, opt[1]) * y[opt[1]] % mod; 
               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:87:93: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     update(1, 0, n - 1, pos, n - 1, log(val) - log(x[pos]), (ll) val * Pow(x[pos], mod - 2) % mod); 
                                                             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:89:59: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     int ans = (ll) query(1, 0, n - 1, opt[1]) * y[opt[1]] % mod; 
               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:94:91: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     update(1, 0, n - 1, pos, pos, log(val) - log(y[pos]), (ll) val * Pow(y[pos], mod - 2) % mod); 
                                                           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:96:59: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     int ans = (ll) query(1, 0, n - 1, opt[1]) * y[opt[1]] % mod; 
               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 3 ms 484 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 548 KB Output is correct
8 Correct 2 ms 548 KB Output is correct
9 Correct 2 ms 568 KB Output is correct
10 Correct 2 ms 568 KB Output is correct
11 Correct 2 ms 632 KB Output is correct
12 Correct 2 ms 632 KB Output is correct
13 Correct 2 ms 632 KB Output is correct
14 Correct 2 ms 640 KB Output is correct
15 Correct 2 ms 640 KB Output is correct
16 Correct 2 ms 640 KB Output is correct
17 Correct 3 ms 640 KB Output is correct
18 Correct 3 ms 640 KB Output is correct
19 Correct 2 ms 656 KB Output is correct
20 Correct 3 ms 656 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 656 KB Output is correct
2 Correct 2 ms 656 KB Output is correct
3 Correct 3 ms 656 KB Output is correct
4 Correct 3 ms 656 KB Output is correct
5 Correct 2 ms 656 KB Output is correct
6 Correct 3 ms 656 KB Output is correct
7 Correct 3 ms 656 KB Output is correct
8 Correct 2 ms 656 KB Output is correct
9 Correct 3 ms 656 KB Output is correct
10 Correct 3 ms 656 KB Output is correct
11 Correct 3 ms 656 KB Output is correct
12 Correct 2 ms 656 KB Output is correct
13 Correct 2 ms 656 KB Output is correct
14 Correct 3 ms 656 KB Output is correct
15 Correct 2 ms 708 KB Output is correct
16 Correct 2 ms 708 KB Output is correct
17 Correct 3 ms 708 KB Output is correct
18 Correct 2 ms 708 KB Output is correct
19 Correct 2 ms 708 KB Output is correct
20 Correct 2 ms 708 KB Output is correct
21 Incorrect 3 ms 708 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 64368 KB Output is correct
2 Correct 2 ms 64368 KB Output is correct
3 Correct 2 ms 64368 KB Output is correct
4 Correct 3 ms 64368 KB Output is correct
5 Correct 2 ms 64368 KB Output is correct
6 Correct 2 ms 64368 KB Output is correct
7 Correct 3 ms 64368 KB Output is correct
8 Correct 3 ms 64368 KB Output is correct
9 Correct 2 ms 64368 KB Output is correct
10 Correct 2 ms 64368 KB Output is correct
11 Correct 3 ms 64368 KB Output is correct
12 Correct 2 ms 64368 KB Output is correct
13 Correct 2 ms 64368 KB Output is correct
14 Correct 3 ms 64368 KB Output is correct
15 Correct 3 ms 64368 KB Output is correct
16 Correct 3 ms 64368 KB Output is correct
17 Correct 2 ms 64368 KB Output is correct
18 Correct 2 ms 64368 KB Output is correct
19 Correct 3 ms 64368 KB Output is correct
20 Correct 3 ms 64368 KB Output is correct
21 Incorrect 2 ms 64368 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 64368 KB Output is correct
2 Correct 2 ms 64368 KB Output is correct
3 Correct 3 ms 64368 KB Output is correct
4 Correct 3 ms 64368 KB Output is correct
5 Correct 2 ms 64368 KB Output is correct
6 Correct 2 ms 64368 KB Output is correct
7 Correct 3 ms 64368 KB Output is correct
8 Correct 2 ms 64368 KB Output is correct
9 Correct 3 ms 64368 KB Output is correct
10 Correct 2 ms 64368 KB Output is correct
11 Correct 3 ms 64368 KB Output is correct
12 Correct 2 ms 64368 KB Output is correct
13 Correct 2 ms 64368 KB Output is correct
14 Correct 2 ms 64368 KB Output is correct
15 Correct 3 ms 64368 KB Output is correct
16 Correct 2 ms 64368 KB Output is correct
17 Correct 2 ms 64368 KB Output is correct
18 Correct 2 ms 64368 KB Output is correct
19 Correct 3 ms 64368 KB Output is correct
20 Correct 2 ms 64368 KB Output is correct
21 Incorrect 3 ms 64368 KB Output isn't correct
22 Halted 0 ms 0 KB -