| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 955775 |
2024-03-31T12:08:56 Z |
emad234 |
Horses (IOI15_horses) |
C++17 |
|
0 ms |
0 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;
ll NN;
struct tree
{
vector<pii> seg;
ll s, e;
void init(ll n)
{
NN = exp2(ceil(log2(n)));
seg.resize(NN * 4);
}
ll queryMax(ll l = 1, ll r = NN, ll ind = 1)
{
if (l > e || r < s)
return 0;
if (l >= s && r <= e)
return seg[ind].F;
ll md = (l + r) / 2;
return max(queryMax(l, md, ind * 2), queryMax(md + 1, r, ind * 2 + 1));
}
ll queryProd(ll l = 1, ll r = NN, ll ind = 1)
{
if (l > e || r < s)
return 1;
if (l >= s && r <= e)
return seg[ind].S;
ll md = (l + r) / 2;
return (queryProd(l, md, ind * 2) * queryProd(md + 1, r, ind * 2 + 1)) % mod;
}
void update(pii val, ll 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;
set<int> s;
ll st[mxN], ed[mxN];
ll x[mxN], y[mxN];
ll vals[mxN];
ll n;
ll solve()
{
ll id = 0;
int i = n - 1;
while (i > 0 && id <= 70)
{
if (x[i] == 1)
{
i = st[i];
id--;
}
i--;
id++;
}
if (i == -1)
i = 0;
ll mx = -1, mxid = -1;
ll prd = 1;
for (i; i < n; i++)
{
if (x[i] == 1)
{
seg.s = i + 1, seg.e = ed[i] + 1;
if (vals[i] * prd > mx)
{
mx = vals[i];
mxid = i;
prd = 1;
}
i = ed[i];
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;
}
ll NN;
struct tree
{
vector<pii> seg;
ll s, e;
void init(ll n)
{
NN = exp2(ceil(log2(n)));
seg.resize(NN * 4);
}
ll queryMax(ll l = 1, ll r = NN, ll ind = 1)
{
if (l > e || r < s)
return 0;
if (l >= s && r <= e)
return seg[ind].F;
ll md = (l + r) / 2;
return max(queryMax(l, md, ind * 2), queryMax(md + 1, r, ind * 2 + 1));
}
ll queryProd(ll l = 1, ll r = NN, ll ind = 1)
{
if (l > e || r < s)
return 1;
if (l >= s && r <= e)
return seg[ind].S;
ll md = (l + r) / 2;
return (queryProd(l, md, ind * 2) * queryProd(md + 1, r, ind * 2 + 1)) % mod;
}
void update(pii val, ll 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;
set<int> s;
ll st[mxN], ed[mxN];
ll x[mxN], y[mxN];
ll vals[mxN];
ll n;
ll solve()
{
ll id = 0;
int i = n - 1;
while (i > 0 && id <= 70)
{
if (x[i] == 1)
{
i = st[i];
id--;
}
i--;
id++;
}
if (i == -1)
i = 0;
ll mx = -1, mxid = -1;
ll prd = 1;
for (i; i < n; i++)
{
// fprintf(_outputFile, "%d ", i);
if (x[i] == 1)
{
seg.s = i + 1, seg.e = ed[i] + 1;
if (vals[i] * prd > mx)
{
mx = vals[i];
mxid = i;
prd = 1;
}
i = ed[i];
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;
}
}
// fprintf(_outputFile, "%d\n", 0);
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 (ll i = 0; i < N; i++)
{
y[i] = Y[i];
x[i] = X[i];
seg.update({Y[i], X[i]}, i);
}
ll l = -1, r = -1;
for (ll i = 0; i < N; i++)
{
if (X[i] == 1)
{
if (l == -1)
l = i;
r = i;
}
else
{
if (l != -1)
{
s.insert(l);
st[r] = l;
ed[l] = r;
l = r = -1;
}
}
}
if (l != -1)
{
s.insert(l);
st[r] = l;
ed[l] = r;
l = r = -1;
}
// for (auto el : s)
// {
// fprintf(_outputFile, "%d ", el);
// fprintf(_outputFile, "%d\n", ed[el]);
// }
return solve();
}
int updateX(int pos, int val)
{
if (x[pos] != 1 && val == 1)
{
auto it = s.upper_bound(pos);
ll l = pos, r = pos;
if (it != s.end() && (*it) == pos + 1)
{
l = pos, r = ed[(*it)];
s.erase(it);
}
s.insert(l);
it = s.lower_bound(l);
if (it != s.begin())
{
it--;
if (ed[(*it)] == l - 1)
{
l = (*it);
s.erase(it);
s.erase(s.lower_bound(pos));
s.insert(l);
}
}
st[r] = l;
ed[l] = r;
seg.s = l + 1, seg.e = r + 1;
vals[l] = seg.queryMax();
}
if (x[pos] == 1 && val != 1)
{
auto it = s.upper_bound(pos);
it--;
ll l = (*it), r = pos - 1, l1 = pos + 1, r1 = ed[(*it)];
s.erase(it);
if (l <= r)
{
s.insert(l);
st[r] = l;
ed[l] = r;
seg.s = l + 1, seg.e = r + 1;
vals[l] = seg.queryMax();
}
if (l1 <= r1)
{
s.insert(l1);
st[r1] = l1;
ed[l1] = r1;
seg.s = l1 + 1, seg.e = r1 + 1;
vals[l1] = seg.queryMax();
}
}
x[pos] = val;
seg.update({y[pos], x[pos]}, pos);
// for (auto el : s)
// {
// fprintf(_outputFile, "%d ", el);
// fprintf(_outputFile, "%d\n", ed[el]);
// }
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(long long int)':
horses.cpp:17:12: warning: conversion from 'double' to 'long long int' may change value [-Wfloat-conversion]
17 | NN = exp2(ceil(log2(n)));
| ~~~~^~~~~~~~~~~~~~~
horses.cpp: In function 'long long int solve()':
horses.cpp:57:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
57 | int i = n - 1;
| ~~^~~
horses.cpp:62:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
62 | i = st[i];
| ~~~~^
horses.cpp:72:7: warning: statement has no effect [-Wunused-value]
72 | for (i; i < n; i++)
| ^
horses.cpp:83:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
83 | i = ed[i];
| ~~~~^
horses.cpp: At global scope:
horses.cpp:106:4: error: redefinition of 'long long int NN'
106 | ll NN;
| ^~
horses.cpp:10:4: note: 'long long int NN' previously declared here
10 | ll NN;
| ^~
horses.cpp:107:8: error: redefinition of 'struct tree'
107 | struct tree
| ^~~~
horses.cpp:11:8: note: previous definition of 'struct tree'
11 | struct tree
| ^~~~
horses.cpp:144:3: error: conflicting declaration 'int seg'
144 | } seg;
| ^~~
horses.cpp:48:3: note: previous declaration as 'tree seg'
48 | } seg;
| ^~~
horses.cpp:145:10: error: redefinition of 'std::set<int> s'
145 | set<int> s;
| ^
horses.cpp:49:10: note: 'std::set<int> s' previously declared here
49 | set<int> s;
| ^
horses.cpp:146:4: error: redefinition of 'long long int st [500005]'
146 | ll st[mxN], ed[mxN];
| ^~
horses.cpp:50:4: note: 'long long int st [500005]' previously declared here
50 | ll st[mxN], ed[mxN];
| ^~
horses.cpp:146:13: error: redefinition of 'long long int ed [500005]'
146 | ll st[mxN], ed[mxN];
| ^~
horses.cpp:50:13: note: 'long long int ed [500005]' previously declared here
50 | ll st[mxN], ed[mxN];
| ^~
horses.cpp:147:4: error: redefinition of 'long long int x [500005]'
147 | ll x[mxN], y[mxN];
| ^
horses.cpp:51:4: note: 'long long int x [500005]' previously declared here
51 | ll x[mxN], y[mxN];
| ^
horses.cpp:147:12: error: redefinition of 'long long int y [500005]'
147 | ll x[mxN], y[mxN];
| ^
horses.cpp:51:12: note: 'long long int y [500005]' previously declared here
51 | ll x[mxN], y[mxN];
| ^
horses.cpp:148:4: error: redefinition of 'long long int vals [500005]'
148 | ll vals[mxN];
| ^~~~
horses.cpp:52:4: note: 'long long int vals [500005]' previously declared here
52 | ll vals[mxN];
| ^~~~
horses.cpp:149:4: error: redefinition of 'long long int n'
149 | ll n;
| ^
horses.cpp:53:4: note: 'long long int n' previously declared here
53 | ll n;
| ^
horses.cpp:150:4: error: redefinition of 'long long int solve()'
150 | ll solve()
| ^~~~~
horses.cpp:54:4: note: 'long long int solve()' previously defined here
54 | ll solve()
| ^~~~~
horses.cpp: In function 'long long int solve()':
horses.cpp:153:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
153 | int i = n - 1;
| ~~^~~
horses.cpp:158:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
158 | i = st[i];
| ~~~~^
horses.cpp:168:7: warning: statement has no effect [-Wunused-value]
168 | for (i; i < n; i++)
| ^
horses.cpp:180:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
180 | i = ed[i];
| ~~~~^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:227:14: warning: conversion from 'long long int' to 'std::set<int>::value_type' {aka 'int'} may change value [-Wconversion]
227 | s.insert(l);
| ^
horses.cpp:236:12: warning: conversion from 'long long int' to 'std::set<int>::value_type' {aka 'int'} may change value [-Wconversion]
236 | s.insert(l);
| ^
horses.cpp:246:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
246 | return solve();
| ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:260:12: warning: conversion from 'long long int' to 'std::set<int>::value_type' {aka 'int'} may change value [-Wconversion]
260 | s.insert(l);
| ^
horses.cpp:261:22: warning: conversion from 'long long int' to 'std::set<int>::key_type' {aka 'int'} may change value [-Wconversion]
261 | it = s.lower_bound(l);
| ^
horses.cpp:270:14: warning: conversion from 'long long int' to 'std::set<int>::value_type' {aka 'int'} may change value [-Wconversion]
270 | s.insert(l);
| ^
horses.cpp:286:13: warning: conversion from 'long long int' to 'std::set<int>::value_type' {aka 'int'} may change value [-Wconversion]
286 | s.insert(l);
| ^
horses.cpp:294:13: warning: conversion from 'long long int' to 'std::set<int>::value_type' {aka 'int'} may change value [-Wconversion]
294 | s.insert(l1);
| ^~
horses.cpp:308:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
308 | return solve();
| ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:315:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
315 | return solve();
| ~~~~~^~
