| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 839295 |
2023-08-29T15:27:36 Z |
Cookie |
Horses (IOI15_horses) |
C++14 |
|
190 ms |
24752 KB |
#include<bits/stdc++.h>
#include<fstream>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#include "horses.h"
const ll mod = 1e9 + 7;
const int mxn = 5e5 + 5, mxr = 25e3, sq = 500, mxv = 200, mxvv = 130, pr = 31;
const ll inf = 1e9;
int n, m;
pii st[4 * mxn + 1];
ll prod[4 * mxn + 1], x[mxn + 1], y[mxn + 1];
set<int>special;
void updprod(int nd, int l, int r, int id, ll v){
if(id < l || id > r)return;
if(l == r){
prod[nd] = v;
return;
}
int mid = (l + r) >> 1;
updprod(nd << 1, l, mid, id, v); updprod(nd << 1 | 1, mid + 1, r, id, v);
prod[nd] = (prod[nd << 1] * prod[nd << 1 | 1]) % mod;
}
void upd(int nd, int l, int r, int id, int v){
if(id < l || id > r)return;
if(l == r){
st[nd] = make_pair(v, id);
return;
}
int mid = (l + r) >> 1;
upd(nd << 1, l, mid, id, v); upd(nd << 1 | 1, mid + 1, r, id, v);
st[nd] = max(st[nd << 1], st[nd << 1 | 1]);
}
ll getprod(int nd, int l, int r, int ql, int qr){
if(ql > r || qr < l)return(1);
if(ql <= l && qr >= r)return(prod[nd]);
int mid = (l + r) >> 1;
return((getprod(nd << 1, l, mid, ql, qr) * getprod(nd << 1 | 1, mid + 1, r, ql, qr)) % mod);
}
pii get(int nd, int l, int r, int ql, int qr){
if(ql > r || qr < l)return(make_pair(-1, -1));
if(ql <= l && qr >= r)return(st[nd]);
int mid = (l + r) >> 1;
return(max(get(nd << 1, l, mid, ql, qr), get(nd << 1 | 1, mid + 1, r, ql, qr)));
}
void updx(int pos, int val){
if(x[pos] != 1)special.erase(pos);
x[pos] = val;
if(x[pos] != 1)special.insert(pos);
updprod(1, 0, n - 1, pos, val);
}
void updy(int pos, int val){
y[pos] = val;
upd(1, 0, n - 1, pos, val);
}
int solve(){
ll mul = 0, idbest = n - 1;
for(int j = n - 1; j >= 0;){
if(mul > inf)break;
if(x[j] >= 2){
if(y[j] > mul){
mul = y[j]; idbest = j;
}
mul = mul * x[j];
j--;
}else{
auto it = special.lower_bound(j);
int id = -1;
if(it != special.begin()){
--it;
id = *it;
}
auto [mxy, idy] = get(1, 0, n - 1, id + 1, j);
if(mxy > mul){
mul = mxy; idbest = idy;
}
j = id;
}
}
return((getprod(1, 0, n - 1, 0, idbest) * y[idbest]) % mod);
}
int init(int N, int X[], int Y[]) {
n = N;
for(int i = 0; i < n; i++){
if(x[i] > 1){
special.insert(i);
}
updprod(1, 0, n - 1, i, x[i]);
}
for(int i = 0; i < n; i++){
y[i] = Y[i];
upd(1, 0, n - 1, i, y[i]);
}
return(solve());
}
int updateX(int pos, int val) {
updx(pos, val);
return(solve());
}
int updateY(int pos, int val) {
updy(pos, val);
return(solve());
}
Compilation message
horses.cpp: In function 'int solve()':
horses.cpp:87:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
87 | auto [mxy, idy] = get(1, 0, n - 1, id + 1, j);
| ^
horses.cpp:98:37: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
98 | return((getprod(1, 0, n - 1, 0, idbest) * y[idbest]) % mod);
| ^~~~~~
horses.cpp:98:58: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
98 | return((getprod(1, 0, n - 1, 0, idbest) * y[idbest]) % mod);
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:111:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
111 | upd(1, 0, n - 1, i, y[i]);
| ~~~^
horses.cpp:100:21: warning: unused parameter 'X' [-Wunused-parameter]
100 | int init(int N, int X[], int Y[]) {
| ~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
190 ms |
24752 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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
