| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 955672 |
2024-03-31T10:04:53 Z |
emad234 |
Horses (IOI15_horses) |
C++17 |
|
171 ms |
45924 KB |
#include "horses.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair<ll, ll>
const ll mod = 1e9 + 7;
const ll mxN = 5e5 + 5;
using namespace std;
int NN;
struct tree
{
vector<pii> seg;
ll s, e;
void init(int n)
{
NN = exp2(ceil(log2(n)));
seg.resize(NN * 4);
}
ll queryMax(int l = 1, int r = NN, int ind = 1)
{
if (l > e || r < s)
return 0;
if (l >= s && r <= e)
return seg[ind].F;
int md = (l + r) / 2;
return max(queryMax(l, md, ind * 2), queryMax(md + 1, r, ind * 2 + 1));
}
ll queryProd(int l = 1, int r = NN, int ind = 1)
{
if (l > e || r < s)
return 1;
if (l >= s && r <= e)
return seg[ind].S;
int md = (l + r) / 2;
return (queryProd(l, md, ind * 2) * queryProd(md + 1, r, ind * 2 + 1)) % mod;
}
void update(pii val, int ind)
{
ind += NN;
seg[ind] = val;
while (ind /= 2)
{
seg[ind].F = max(seg[ind * 2].F, seg[ind * 2 + 1].F);
seg[ind].S = (seg[ind * 2].S * seg[ind * 2 + 1].S) % mod;
}
}
} seg;
struct ones
{
ll l, r;
friend bool operator<(ones a, ones b)
{
return a.l < b.l;
}
};
set<ones> s;
ll x[mxN], y[mxN];
int n;
ll solve()
{
int st, id = 0;
int i = n - 1;
while (i && id <= 100)
{
if (x[i] == 1)
{
auto it = s.upper_bound({i, i});
it--;
i = (*it).l;
}
i--;
id++;
}
ll mx = -1, mxid = -1;
ll prd = 1;
for (i; i < n; i++)
{
if (x[i] == 1)
{
auto it = s.lower_bound({i, i});
seg.s = (*it).l + 1, seg.e = (*it).r + 1;
ll val = seg.queryMax();
if (val * prd > mx)
{
mx = val;
mxid = i;
prd = 1;
}
i = (*it).r;
continue;
}
if (prd * x[i] > mx)
{
mx = y[i];
mxid = i;
prd = 1;
continue;
}
prd *= x[i];
if (prd * y[i] > mx)
{
mx = y[i];
mxid = i;
prd = 1;
continue;
}
}
seg.s = 1;
seg.e = mxid + 1;
return (mx * seg.queryProd()) % mod;
}
int init(int N, int X[], int Y[])
{
seg.init(N);
n = N;
for (int i = 0; i < N; i++)
{
y[i] = Y[i];
x[i] = X[i];
seg.update({Y[i], X[i]}, i);
}
int l = -1, r = -1;
for (int i = 0; i < N; i++)
{
if (X[i] == 1)
{
if (l == -1)
l = i;
r = i;
}
else
{
if (l != -1)
{
s.insert({l, r});
l = r = -1;
}
}
}
if (l != -1)
{
s.insert({l, r});
l = r = -1;
}
return solve();
}
int updateX(int pos, int val)
{
if (x[pos] != 1 && val == 1)
{
auto it = s.upper_bound({pos, pos});
int l = pos, r = pos;
if (it != s.end() && (*it).l == pos + 1)
{
l = pos, r = (*it).r;
s.erase(it);
s.insert({l, r});
}
else
s.insert({pos, pos});
it = s.lower_bound({pos, pos});
auto p = s.lower_bound({l, r});
if (it != s.begin())
{
it--;
if ((*it).r == l - 1)
{
l = (*it).l;
s.erase(it);
s.erase(s.lower_bound({pos, pos}));
s.insert({l, r});
}
}
}
if (x[pos] == 1 && val != 1)
{
auto it = s.upper_bound({pos, 0});
it--;
int l = (*it).l, r = pos - 1, l1 = pos + 1, r1 = (*it).r;
s.erase(it);
if (l <= r)
s.insert({l, r});
if (l1 <= r1)
s.insert({l1, r1});
}
x[pos] = val;
seg.update({y[pos], x[pos]}, pos);
return solve();
}
int updateY(int pos, int val)
{
y[pos] = val;
seg.update({y[pos], x[pos]}, pos);
return solve();
}
Compilation message
horses.cpp: In member function 'void tree::init(int)':
horses.cpp:18:12: warning: conversion from 'double' to 'int' may change value [-Wfloat-conversion]
18 | NN = exp2(ceil(log2(n)));
| ~~~~^~~~~~~~~~~~~~~
horses.cpp: In function 'long long int solve()':
horses.cpp:71:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
71 | i = (*it).l;
| ~~~~~~^
horses.cpp:78:7: warning: statement has no effect [-Wunused-value]
78 | for (i; i < n; i++)
| ^
horses.cpp:91:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
91 | i = (*it).r;
| ~~~~~~^
horses.cpp:63:6: warning: unused variable 'st' [-Wunused-variable]
63 | int st, id = 0;
| ^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:147:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
147 | return solve();
| ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:158:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
158 | l = pos, r = (*it).r;
| ~~~~~~^
horses.cpp:171:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
171 | l = (*it).l;
| ~~~~~~^
horses.cpp:165:8: warning: variable 'p' set but not used [-Wunused-but-set-variable]
165 | auto p = s.lower_bound({l, r});
| ^
horses.cpp:182:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
182 | int l = (*it).l, r = pos - 1, l1 = pos + 1, r1 = (*it).r;
| ~~~~~~^
horses.cpp:182:58: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
182 | int l = (*it).l, r = pos - 1, l1 = pos + 1, r1 = (*it).r;
| ~~~~~~^
horses.cpp:191:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
191 | return solve();
| ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:198:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
198 | return solve();
| ~~~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
2396 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
131 ms |
45828 KB |
Output is correct |
| 2 |
Correct |
171 ms |
45904 KB |
Output is correct |
| 3 |
Correct |
146 ms |
45924 KB |
Output is correct |
| 4 |
Correct |
157 ms |
45904 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
