#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node
{
int s, e, m, v;
node *l, *r;
node (int _s, int _e) : s(_s), e(_e), m((_s + _e) / 2), v(-1)
{
if (s != e)
l = new node(s, m),
r = new node(m + 1, e);
}
void upd(int n, int x)
{
if (s == e)
{
v = x;
return;
}
if (n <= m)
l->upd(n, x);
else
r->upd(n, x);
v = max(l->v, r->v);
}
int qry(int a, int b)
{
if (b < s || a > e)
return -1;
if (a <= s && b >= e)
return v;
return max(l->qry(a, b), r->qry(a, b));
}
} *root;
vector<long long> minimum_costs(vector<signed> H, vector<signed> L,
vector<signed> R) {
int N = H.size(), Q = L.size();
stack<int> stk;
vector<pair<int, int>> ranges;
vector<int> l, r;
bool done = false;
for (int i = 0; i < N; i++)
{
if (H[i] == 1)
{
if (!done)
{
ranges.push_back(pair<int, int>(i, i));
done = true;
}
else
{
ranges[ranges.size() - 1].second = i;
}
}
else
{
done = false;
}
}
root = new node(0, ranges.size() - 1);
for (int i = 0; i < ranges.size(); i++)
{
root->upd(i, ranges[i].second + 1 - ranges[i].first);
l.push_back(ranges[i].first);
r.push_back(ranges[i].second);
}
vector<int> ans;
for (int i = 0; i < Q; i++)
{
int an = INT_MAX;
auto iter1 = upper_bound(l.begin(), l.end(), L[i]);
if (iter1 != l.begin())
{
iter1--;
auto iter2 = lower_bound(r.begin(), r.end(), L[i]);
if (iter2 != r.end() && iter1 == iter2)
{
an = min(an, *iter2 - L[i] + 1);
}
}
iter1 = upper_bound(l.begin(), l.end(), R[i]);
if (iter1 != l.begin())
{
iter1--;
auto iter2 = lower_bound(r.begin(), r.end(), R[i]);
if (iter2 != r.end() && iter1 == iter2)
{
an = min(an, R[i] - *iter1 + 1);
}
}
iter1 = lower_bound(r.begin(), r.end(), L[i]);
auto iter2 = upper_bound(l.begin(), l.end(), R[i]);
if (iter2 != l.begin())
{
an = min(an, root->qry(distance(r.begin(), iter1), distance(l.begin(), iter2)));
}
ans.push_back((R[i] + 1 - L[i]) * 2 - an);
}
return ans;
}
Compilation message
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:69:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for (int i = 0; i < ranges.size(); i++)
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
556 ms |
786432 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
556 ms |
786432 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
434 ms |
786432 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
434 ms |
786432 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
556 ms |
786432 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
