| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 710640 |
2023-03-15T13:00:28 Z |
ssense |
Horses (IOI15_horses) |
C++14 |
|
1500 ms |
90360 KB |
#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
#define MOD 1000000007
int ng;
long long power(long long n, long long pow, long long m) {if (pow == 0) return 1;if (pow % 2 == 0) {long long x = power(n, pow / 2, m);return (x * x) % m;}else return (power(n, pow - 1, m) * n) % m;}
template<typename T>
struct LazySegmentTree{
int n;
vector<T> t, lazy, a;
T neutral, lazy_neutral;
function<T(const T&, const T&)> merge;
function<T(const T&, const T&)> upd;
bool range_modif = false;
LazySegmentTree(int _n, T _neutral, T _lazy_neutral, const function<T(const T&, const T&)> &_merge, const function<T(const T&, const T&)> &_upd, bool _range_modif){
range_modif = _range_modif;
init(_n, _neutral, _lazy_neutral, _merge, _upd);
}
LazySegmentTree(vector<T> _a, T _neutral, T _lazy_neutral, const function<T(const T&, const T&)> &_merge, const function<T(const T&, const T&)> &_upd, bool _range_modif){
range_modif = _range_modif, a = _a;
int _n = (int)a.size();
init(_n, _neutral, _lazy_neutral, _merge, _upd);
build(1, 0, n - 1);
}
void init(int _n, T _neutral, T _lazy_neutral, const function<T(const T&, const T&)> &_merge, const function<T(const T&, const T&)> &_upd){
n = _n, neutral = _neutral, lazy_neutral = _lazy_neutral, merge = _merge, upd = _upd;
t.assign(4 * n, neutral);
lazy.assign(4 * n, lazy_neutral);
}
void build(int i, int l, int r){
if(l == r){
t[i] = a[l];
return;
}
int mid = (l + r) >> 1;
build(2 * i, l, mid);
build(2 * i + 1, mid + 1, r);
t[i] = merge(t[2 * i], t[2 * i + 1]);
}
void push(int i, int l, int r){
if(lazy[i] == lazy_neutral)return;
t[i] = upd(t[i], lazy[i] * (range_modif ? (r - l + 1) : 1));
if(l != r){
lazy[2 * i] = upd(lazy[2 * i], lazy[i]);
lazy[2 * i + 1] = upd(lazy[2 * i + 1], lazy[i]);
}
lazy[i] = lazy_neutral;
}
void modif(int i, int l, int r, int tl, int tr, T val){
push(i, l, r);
if(l > tr || r < tl)return;
if(l >= tl && r <= tr){
lazy[i] = upd(lazy[i], val);
push(i, l, r);
return;
}
int mid = (l + r) >> 1;
modif(2 * i, l, mid, tl, tr, val);
modif(2 * i + 1, mid + 1, r, tl, tr, val);
t[i] = merge(t[2 * i], t[2 * i + 1]);
}
T query(int i, int l, int r, int tl, int tr){
push(i, l, r);
if(l > tr || r < tl)return neutral;
if(l >= tl && r <= tr)return t[i];
int mid = (l + r) >> 1;
T left = query(2 * i, l, mid, tl, tr);
T right = query(2 * i + 1, mid + 1, r, tl, tr);
return merge(left, right);
}
void modif(int l, int r, T val){
modif(1, 0, n - 1, l, r, val);
}
void modif(int poz, T val){
modif(1, 0, n - 1, poz, poz, val);
}
T query(int l, int r){
return query(1, 0, n - 1, l, r);
}
T query(int poz){
return query(1, 0, n - 1, poz, poz);
}
//n, neutral, lazy neutral, merge, upd, bool range update
};
long long mergex(long long a, long long b)
{
return (a*b)%MOD;
}
long long updx(long long a, long long b)
{
return (power(a, MOD-2, MOD)*b)%MOD;
}
long long mergey(long long a, long long b)
{
return max(a, b);
}
long long updy(long long a, long long b)
{
return b;
}
LazySegmentTree<long long> stx(500000, 1, 0, mergex, updx, 0);
LazySegmentTree<long long> sty(500000, 0, 0, mergey, updy, 0);
set<int> s;
int init(int n, int* x, int* y)
{
ng = n;
s.insert(0);
s.insert(ng);
for(int i = 0; i < n; i++)
{
stx.modif(i, x[i]);
if(x[i] > 1)
{
s.insert(i);
}
sty.modif(i, y[i]);
}
auto it = s.end();
it--;
while(true)
{
if(stx.query(*it, n-1) > 1000000000)
{
break;
}
if(it == s.begin())
{
break;
}
it--;
}
auto first = it;
long long should_multiply = stx.query(0LL, *it);
long long now = 1;
long long mx = 0;
for(; it != s.end(); it++)
{
if(it != first)
{
now*=stx.query(*it);
}
auto urmatorul = it;
urmatorul++;
if(urmatorul == s.end()){break;}
long long now_range = now*sty.query(*it, *urmatorul-1);
mx = max(mx, now_range);
}
mx%=MOD;
return (int)((mx*should_multiply)%MOD);
}
int updateX(int pos, int val)
{
if(stx.query(pos) == 1 && val != 1)
{
s.insert(pos);
stx.modif(pos, val);
}
else if(stx.query(pos) != 1 && val == 1)
{
s.erase(s.find(pos));
stx.modif(pos, val);
}
auto it = s.end();
it--;
while(true)
{
if(stx.query(*it, ng-1) > 1000000000)
{
break;
}
if(it == s.begin())
{
break;
}
it--;
}
auto first = it;
long long should_multiply = stx.query(0LL, *it);
long long now = 1;
long long mx = 0;
for(; it != s.end(); it++)
{
if(it != first)
{
now*=stx.query(*it);
}
auto urmatorul = it;
urmatorul++;
if(urmatorul == s.end()){break;}
long long now_range = now*sty.query(*it, *urmatorul-1);
mx = max(mx, now_range);
}
mx%=MOD;
return (int)((mx*should_multiply)%MOD);
}
int updateY(int pos, int val)
{
sty.modif(pos, val);
auto it = s.end();
it--;
while(true)
{
if(stx.query(*it, ng-1) > 1000000000)
{
break;
}
if(it == s.begin())
{
break;
}
it--;
}
auto first = it;
long long should_multiply = stx.query(0LL, *it);
long long now = 1;
long long mx = 0;
for(; it != s.end(); it++)
{
if(it != first)
{
now*=stx.query(*it);
}
auto urmatorul = it;
urmatorul++;
if(urmatorul == s.end()){break;}
long long now_range = now*sty.query(*it, *urmatorul-1);
mx = max(mx, now_range);
}
mx%=MOD;
return (int)((mx*should_multiply)%MOD);
}
Compilation message
horses.cpp: In function 'long long int updy(long long int, long long int)':
horses.cpp:123:26: warning: unused parameter 'a' [-Wunused-parameter]
123 | long long updy(long long a, long long b)
| ~~~~~~~~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
62828 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
62908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1581 ms |
90360 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
62932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
62932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
