| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 785203 |
2023-07-17T07:08:18 Z |
NothingXD |
Horses (IOI15_horses) |
C++17 |
|
192 ms |
61204 KB |
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;
void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cout << H << " ";
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
const int maxn = 5e5 + 10;
const int mod = 1e9 + 7;
int n;
ll x[maxn], y[maxn];
ll seg[maxn << 2], dp[maxn << 2][2];
bool of[maxn << 2];
void build(int v, int l, int r){
if (l + 1 == r){
seg[v] = x[l];
return;
}
int mid = (l + r) >> 1;
build(v << 1, l, mid);
build(v << 1 | 1, mid, r);
ll tmp = 1ll * seg[v << 1] * seg[v << 1 | 1];
if (tmp >= mod || of[v << 1] || of[v << 1 | 1]) of[v] = true;
seg[v] = tmp % mod;
}
void change(int v, int l, int r, int idx){
if (idx < l || r <= idx) return;
if (l + 1 == r){
seg[v] = x[l];
return;
}
int mid = (l + r) >> 1;
change(v << 1, l, mid, idx);
change(v << 1 | 1, mid, r, idx);
ll tmp = 1ll * seg[v << 1] * seg[v << 1 | 1];
if (tmp >= mod || of[v << 1] || of[v << 1 | 1]) of[v] = true;
seg[v] = tmp % mod;
}
int find(int v, int l, int r, int tmp){
if (!of[v] && 1ll * tmp * seg[v] < mod) return -1;
if (l + 1 == r) return l;
int mid = (l + r) >> 1;
int res = find(v << 1 | 1, mid, r, tmp);
if (res == -1){
tmp *= seg[v << 1 | 1];
res = find(v << 1, l, mid, tmp);
}
return res;
}
int get(int v, int l, int r, int ql, int qr){
if (qr <= l || r <= ql) return 1;
if (ql <= l && r <= qr) return seg[v];
int mid = (l + r) >> 1;
return 1ll * get(v << 1, l, mid, ql, qr) * get(v << 1 | 1, mid, r, ql, qr) % mod;
}
void build2(int v, int l, int r){
if (l + 1 == r){
dp[v][0] = x[l] * y[l];
dp[v][1] = x[l];
return;
}
int mid = (l + r) >> 1;
build2(v << 1, l, mid);
build2(v << 1 | 1, mid, r);
dp[v][0] = max(dp[v << 1][0], dp[v << 1][1] * dp[v << 1 | 1][0]);
dp[v][1] = dp[v << 1][1] * dp[v << 1 | 1][1];
}
void change2(int v, int l, int r, int idx){
if (idx < l || r <= idx) return;
if (l + 1 == r){
dp[v][0] = x[l] * y[l];
dp[v][1] = x[l];
return;
}
int mid = (l + r) >> 1;
change2(v << 1, l, mid, idx);
change2(v << 1 | 1, mid, r, idx);
dp[v][0] = max(dp[v << 1][0], dp[v << 1][1] * dp[v << 1 | 1][0]);
dp[v][1] = dp[v << 1][1] * dp[v << 1 | 1][1];
}
pll get2(int v, int l, int r, int ql, int qr){
if (qr <= l || r <= ql) return {1, 1};
if (ql <= l && r <= qr) return MP(dp[v][0], dp[v][1]);
int mid = (l + r) >> 1;
pll a = get2(v << 1, l, mid, ql, qr);
pll b = get2(v << 1 | 1, mid, r, ql, qr);
return MP(max(a.S, a.F * b.S), a.F * b.F);
}
set<int> st;
int Calc(){
int idx = find(1, 0, n, 1);
if (idx == -1) idx = 0;
int tmp = get(1, 0, n, 0, idx+1);
ll tmp2 = max(y[idx], get2(1, 0, n+1, idx+1, n+1).F) % mod;
return 1ll * tmp * tmp2 % mod;
}
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];
if (x[i] > 1) st.insert(i);
}
build(1, 0, n);
build2(1, 0, n+1);
return Calc();
}
int updateX(int pos, int val) {
st.erase(pos);
x[pos] = val;
if (val > 1) st.insert(pos);
change(1, 0, n, pos);
change2(1, 0, n+1, pos);
return Calc();
}
int updateY(int pos, int val) {
y[pos] = val;
change2(1, 0, n+1, pos);
return Calc();
}
Compilation message
horses.cpp: In function 'int find(int, int, int, int)':
horses.cpp:68:7: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
68 | tmp *= seg[v << 1 | 1];
| ~~~~^~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int get(int, int, int, int, int)':
horses.cpp:76:38: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
76 | if (ql <= l && r <= qr) return seg[v];
| ~~~~~^
horses.cpp:78:77: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
78 | return 1ll * get(v << 1, l, mid, ql, qr) * get(v << 1 | 1, mid, r, ql, qr) % mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int Calc()':
horses.cpp:124:26: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
124 | return 1ll * tmp * tmp2 % mod;
| ~~~~~~~~~~~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
192 ms |
61204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
