This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//Power Of Ninja Go
#include <bits/stdc++.h>
#ifdef atom
#include "grader.cpp"
#else
#include "horses.h"
#endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii;
#define X first
#define Y second
#define vi vector<int>
#define vii vector< ii >
#define pb push_back
const int maxn = 500005;
const int md = 1e9 + 7;
int prod[4*maxn];
int most[4*maxn];
int x[4*maxn];
int y[4*maxn];
int n;
int mul(int a, int b)
{
return (1LL*a*b)%md;
}
void update(int *st, int x, int dx, int md, int p = 1, int L = 1, int R = n)
{
if(L> x || R< x) return;
if(L == R && L == x)
{
st[p] = dx;
return;
}
int M = (L+R)/2;
//printf("%d %d %d\n", L, R, M);
//system("pause");
update(st, x, dx, md, 2*p, L, M); update(st, x, dx, md, 2*p+1, M+1, R);
if(md == 1) st[p] = mul(st[2*p], st[2*p+1]);
else st[p] = max(st[2*p], st[2*p+1]);
}
int ask(int *st, int i, int j, int md, int p = 1, int L = 1, int R = n)
{
if(i> R || j< L) return 1;
if(i<= L && R<= j) return st[p];
int M = (L+R)/2;
int x = ask(st, i, j, md, 2*p, L, M);
int y = ask(st, i, j, md, 2*p+1, M+1, R);
if(md == 1) return mul(x, y);
else return max(x, y);
}
set<int> bst;
int query()
{
int cnt = 30;
vi tmp;
for(auto it = bst.rbegin(); it != bst.rend() && cnt; it++)
{
tmp.pb(*it);
cnt--;
}
reverse(tmp.begin(), tmp.end());
if(tmp.empty()) return ask(most, 1, n, 2);
ll best = ask(most, 1, tmp[0]-1, 2);
ll run = 1;
int q = tmp.size();
for(int i = 0; i< q; i++)
{
//printf("%d", tmp[i]);
run *= x[tmp[i]];
int rend = i+1<q?tmp[i+1]:n+1;
best = max(best, 1LL*run*ask(most, tmp[i], rend-1, 2));
//printf("(%d)", run*ask(most, tmp[i], rend-1, 2));
}
//printf("\n");
return mul(best, ask(prod, 1, tmp[0]-1, 1));
}
int init(int N, int X[], int Y[])
{
n = N;
for(int i = 1; i<= n; i++) x[i] = X[i-1], y[i] = Y[i-1];
for(int i = 1; i<= N; i++) update(prod, i, x[i], 1);
for(int i = 1; i<= N; i++) update(most, i, y[i], 2);
for(int i = 1; i<= N; i++) if(x[i]> 1) bst.insert(i);
return query();
}
int updateX(int pos, int val)
{
pos++;
x[pos] = val;
if(val> 1) bst.insert(pos);
else bst.erase(pos);
update(prod, pos, val, 1);
return query();
}
int updateY(int pos, int val)
{
pos++;
y[pos] = val;
update(most, pos, val, 2);
return query();
}
Compilation message (stderr)
horses.cpp: In function 'int mul(int, int)':
horses.cpp:24:19: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return (1LL*a*b)%md;
^
horses.cpp: In function 'void update(int*, int, int, int, int, int, int)':
horses.cpp:26:76: warning: declaration of 'md' shadows a global declaration [-Wshadow]
void update(int *st, int x, int dx, int md, int p = 1, int L = 1, int R = n)
^
horses.cpp:16:11: note: shadowed declaration is here
const int md = 1e9 + 7;
^
horses.cpp:26:76: warning: declaration of 'x' shadows a global declaration [-Wshadow]
void update(int *st, int x, int dx, int md, int p = 1, int L = 1, int R = n)
^
horses.cpp:19:5: note: shadowed declaration is here
int x[4*maxn];
^
horses.cpp: In function 'int ask(int*, int, int, int, int, int, int)':
horses.cpp:41:71: warning: declaration of 'md' shadows a global declaration [-Wshadow]
int ask(int *st, int i, int j, int md, int p = 1, int L = 1, int R = n)
^
horses.cpp:16:11: note: shadowed declaration is here
const int md = 1e9 + 7;
^
horses.cpp:46:6: warning: declaration of 'x' shadows a global declaration [-Wshadow]
int x = ask(st, i, j, md, 2*p, L, M);
^
horses.cpp:19:5: note: shadowed declaration is here
int x[4*maxn];
^
horses.cpp:47:6: warning: declaration of 'y' shadows a global declaration [-Wshadow]
int y = ask(st, i, j, md, 2*p+1, M+1, R);
^
horses.cpp:20:5: note: shadowed declaration is here
int y[4*maxn];
^
horses.cpp: In function 'int query()':
horses.cpp:65:19: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
int q = tmp.size();
^
horses.cpp:75:44: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
return mul(best, ask(prod, 1, tmp[0]-1, 1));
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |