| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 747420 |
2023-05-24T07:26:55 Z |
Desh03 |
Horses (IOI15_horses) |
C++17 |
|
131 ms |
38664 KB |
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
vector<int> x, y;
int n;
struct segtree1 {
vector<double> st, lz;
vector<int> id;
int sz;
void init(vector<double> a) {
sz = a.size();
while (sz & sz - 1) ++sz;
st.resize(sz << 1), lz.resize(sz << 1), id.resize(sz << 1);
for (int i = 0; i < a.size(); i++) st[i + sz] = a[i] + log(y[i]), id[i + sz] = i;
for (int i = sz - 1; i; i--) pull(i);
}
void pull(int v) {
if (st[v << 1] >= st[v << 1 | 1]) {
st[v] = st[v << 1], id[v] = id[v << 1];
} else {
st[v] = st[v << 1 | 1], id[v] = id[v << 1 | 1];
}
}
void push(int v) {
st[v << 1] += lz[v];
st[v << 1 | 1] += lz[v];
lz[v << 1] += lz[v];
lz[v << 1 | 1] += lz[v];
lz[v] = 0;
}
void updx(int v, int l, int r, int ql, int qr, double x) {
if (l > qr || r < ql) return;
if (l >= ql && r <= qr) {
st[v] += x, lz[v] += x;
return;
}
if (lz[v]) push(v);
int m = l + r >> 1;
updx(v << 1, l, m, ql, qr, x);
updx(v << 1 | 1, m + 1, r, ql, qr, x);
pull(v);
}
void updy(int v, int l, int r, int u, double y) {
if (l == r) {
st[v] += y;
return;
}
if (lz[v]) push(v);
int m = l + r >> 1;
if (u <= m) updy(v << 1, l, m, u, y);
else updy(v << 1 | 1, m + 1, r, u, y);
pull(v);
}
void updx(int l, int r, double x) {
updx(1, 0, sz - 1, l, r, x);
}
void updy(int u, double y) {
updy(1, 0, sz - 1, u, y);
}
} st1;
struct segtree2 {
vector<int> st;
int sz;
void init(int n) {
sz = n;
st.resize(sz << 1);
}
void upd(int id, int x) {
for (st[id += sz] = x; id >>= 1;) st[id] = 1LL * st[id << 1] * st[id << 1 | 1] % mod;
}
int qry(int l, int r) {
int s = 1;
for (l += sz, r += sz + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) s = 1LL * s * st[l++] % mod;
if (r & 1) s = 1LL * s * st[--r] % mod;
}
return s;
}
} st2;
int init(int N, int X[], int Y[]) {
n = N, x.resize(n), y.resize(n);
for (int i = 0; i < n; i++) x[i] = X[i], y[i] = Y[i];
vector<double> p(n);
p[0] = log(x[0]);
for (int i = 1; i < n; i++) p[i] = p[i - 1] + log(x[i]);
st1.init(p);
st2.init(n);
for (int i = 0; i < n; i++) st2.upd(i, x[i]);
return st2.qry(0, st1.id[1]);
}
int updateX(int pos, int val) {
st1.updx(pos, n - 1, log(val) - log(x[pos]));
st2.upd(pos, val);
x[pos] = val;
return st2.qry(0, st1.id[1]);
}
int updateY(int pos, int val) {
st1.updy(pos, log(val) - log(y[pos]));
y[pos] = val;
return st2.qry(0, st1.id[1]);
}
Compilation message
horses.cpp: In member function 'void segtree1::init(std::vector<double>)':
horses.cpp:14:20: warning: conversion from 'std::vector<double>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
14 | sz = a.size();
| ~~~~~~^~
horses.cpp:15:24: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
15 | while (sz & sz - 1) ++sz;
| ~~~^~~
horses.cpp:17:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for (int i = 0; i < a.size(); i++) st[i + sz] = a[i] + log(y[i]), id[i + sz] = i;
| ~~^~~~~~~~~~
horses.cpp: In member function 'void segtree1::updx(int, int, int, int, int, double)':
horses.cpp:34:59: warning: declaration of 'x' shadows a global declaration [-Wshadow]
34 | void updx(int v, int l, int r, int ql, int qr, double x) {
| ~~~~~~~^
horses.cpp:6:13: note: shadowed declaration is here
6 | vector<int> x, y;
| ^
horses.cpp:41:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
41 | int m = l + r >> 1;
| ~~^~~
horses.cpp: In member function 'void segtree1::updy(int, int, int, int, double)':
horses.cpp:46:50: warning: declaration of 'y' shadows a global declaration [-Wshadow]
46 | void updy(int v, int l, int r, int u, double y) {
| ~~~~~~~^
horses.cpp:6:16: note: shadowed declaration is here
6 | vector<int> x, y;
| ^
horses.cpp:52:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
52 | int m = l + r >> 1;
| ~~^~~
horses.cpp: In member function 'void segtree1::updx(int, int, double)':
horses.cpp:57:36: warning: declaration of 'x' shadows a global declaration [-Wshadow]
57 | void updx(int l, int r, double x) {
| ~~~~~~~^
horses.cpp:6:13: note: shadowed declaration is here
6 | vector<int> x, y;
| ^
horses.cpp: In member function 'void segtree1::updy(int, double)':
horses.cpp:60:29: warning: declaration of 'y' shadows a global declaration [-Wshadow]
60 | void updy(int u, double y) {
| ~~~~~~~^
horses.cpp:6:16: note: shadowed declaration is here
6 | vector<int> x, y;
| ^
horses.cpp: In member function 'void segtree2::init(int)':
horses.cpp:68:19: warning: declaration of 'n' shadows a global declaration [-Wshadow]
68 | void init(int n) {
| ~~~~^
horses.cpp:7:5: note: shadowed declaration is here
7 | int n;
| ^
horses.cpp: In member function 'void segtree2::upd(int, int)':
horses.cpp:72:26: warning: declaration of 'x' shadows a global declaration [-Wshadow]
72 | void upd(int id, int x) {
| ~~~~^
horses.cpp:6:13: note: shadowed declaration is here
6 | vector<int> x, y;
| ^
horses.cpp:73:88: warning: conversion from 'long long int' to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
73 | for (st[id += sz] = x; id >>= 1;) st[id] = 1LL * st[id << 1] * st[id << 1 | 1] % mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In member function 'int segtree2::qry(int, int)':
horses.cpp:78:46: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
78 | if (l & 1) s = 1LL * s * st[l++] % mod;
| ~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:79:46: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
79 | if (r & 1) s = 1LL * s * st[--r] % mod;
| ~~~~~~~~~~~~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
131 ms |
38664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
