| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 726486 |
2023-04-19T03:01:14 Z |
becaido |
Horses (IOI15_horses) |
C++17 |
|
84 ms |
31696 KB |
#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;
#ifndef WAIMAI
#include "horses.h"
#endif
#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout (T t, U...u) {cout << t << (sizeof... (u) ? ", " : ""), dout (u...);}
#else
#define debug(...) 7122
#endif
#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second
#define lpos pos*2
#define rpos pos*2+1
const int MOD = 1e9 + 7;
const int SIZE = 5e5 + 5;
struct Node {
int pro = 1;
double sum = 0, mx = 0;
Node operator + (const Node& rhs) const {
Node re;
re.pro = 1ll * pro * rhs.pro % MOD;
re.sum = sum + rhs.sum;
re.mx = max(mx, sum + rhs.mx);
return re;
}
} node[4 * SIZE];
int n, y[SIZE];
void upd(int pos, int l, int r, int p, int ty, int x) {
if (l == r) {
if (ty == 1) {
node[pos].pro = x;
node[pos].sum = log(x);
}
if (ty == 2) {
node[pos].mx = node[pos].sum + log(y[p] = x);
}
return;
}
int mid = (l + r) / 2;
if (p <= mid) upd(lpos, l, mid, p, ty, x);
else upd(rpos, mid + 1, r, p, ty, x);
node[pos] = node[lpos] + node[rpos];
}
int que(int pos, int l, int r, int cur = 1) {
if (l == r) return 1ll * cur * y[l] % MOD;
int mid = (l + r) / 2;
if (node[lpos].mx >= node[lpos].sum + node[rpos].mx) return que(lpos, l, mid, cur);
else return que(rpos, mid + 1, r, 1ll * cur * node[lpos].pro % MOD);
}
int init(int N, int X[], int Y[]) {
auto build = [&](auto build, int pos, int l, int r)->void {
if (l == r) {
node[pos].pro = X[l];
node[pos].sum = log(X[l]);
node[pos].mx = node[pos].sum + log(y[l] = Y[l]);
return;
}
int mid = (l + r) / 2;
build(build, lpos, l, mid);
build(build, rpos, mid + 1, r);
node[pos] = node[lpos] + node[rpos];
};
n = N;
build(build, 1, 0, n - 1);
return que(1, 0, n - 1);
}
int updateX(int pos, int val) {
upd(1, 0, n - 1, pos, 1, val);
return que(1, 0, n - 1);
}
int updateY(int pos, int val) {
upd(1, 0, n - 1, pos, 2, val);
return que(1, 0, n - 1);
}
/*
in1
3
2 1 3
3 4 1
1
2 1 2
out1
...
*/
#ifdef WAIMAI
int main() {
int N; cin >> N;
int *X = (int*)malloc(sizeof(int)*(unsigned int)N);
int *Y = (int*)malloc(sizeof(int)*(unsigned int)N);
for (int i = 0; i < N; i++) cin >> X[i];
for (int i = 0; i < N; i++) cin >> Y[i];
cout << init(N,X,Y) << '\n';
int M; cin >> M;
for (int i = 0; i < M; i++) {
int type; cin >> type;
int pos; cin >> pos;
int val; cin >> val;
if (type == 1) {
cout << updateX(pos,val) << '\n';
} else if (type == 2) {
cout << updateY(pos,val) << '\n';
}
}
return 0;
}
#endif
Compilation message
horses.cpp: In member function 'Node Node::operator+(const Node&) const':
horses.cpp:37:38: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
37 | re.pro = 1ll * pro * rhs.pro % MOD;
| ~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int que(int, int, int, int)':
horses.cpp:64:41: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
64 | if (l == r) return 1ll * cur * y[l] % MOD;
| ~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:67:66: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
67 | else return que(rpos, mid + 1, r, 1ll * cur * node[lpos].pro % MOD);
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In lambda function:
horses.cpp:71:27: warning: declaration of 'build' shadows a previous local [-Wshadow]
71 | auto build = [&](auto build, int pos, int l, int r)->void {
| ~~~~~^~~~~
horses.cpp:71:10: note: shadowed declaration is here
71 | auto build = [&](auto build, int pos, int l, int r)->void {
| ^~~~~
| # |
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 |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
84 ms |
31696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
