Submission #72719

#TimeUsernameProblemLanguageResultExecution timeMemory
72719RezwanArefin01Horses (IOI15_horses)C++17
17 / 100
229 ms64368 KiB
#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 (stderr)

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; 
               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...