# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
723394 | Quentolosse | Measures (CEOI22_measures) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 1e9;
struct node
{
int maxi = -inf, mini = inf, reponse = -inf, decalage = 0;
};
vector<node> segtree;
int n, m, d;
node merge (node a, node b)
{
node c;
c.maxi = max(a.max + a.decalage, b.max + b.decalage);
c.mini = min(a.min + a.decalage, b.min + b.decalage);
c.reponse = max(b.max - a.min, max(a.reponse, b.reponse));
return c;
}
void update (int i, node a)
{
segtree[i] = a;
if (i == 1)
{
return;
}
if (i % 2)
{
update((i - 1) / 2, merge(segtree[i - 1], segtree[i]));
}
else
{
update(i / 2, merge(segtree[i], segtree[i + 1]));
}
}
void decalage (int i, int L, int l, int r, int R)
{
if (L == l && r == R)
{
segtree[i].decalage =
}
decalage(i * 2, )
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> n >> m >> d;
segtree.resize(2 * (n + m));
vector<int> debut (n);
for (int i = 0; i < n; i++)
{
cin >> debut[i];
}
vector<int> requetes (m);
for (int i = 0; i < m; i++)
{
cin >> requetes[i];
}
vector<pair<int, int>> points (n + m);
for (int i = 0; i < n; i++)
{
points[i].first = debut[i];
points[i].second = i;
}
for (int i = 0; i < m; i ++)
{
points[n + i].first = requetes[i];
points[n + i].second = n + i;
}
sort(points.begin(), points.end());
vector<int> posRequete (m);
for (int i = 0; i < n + m; i++)
{
if (points[i].second < n)
{
segtree[n + m + i + 1].max = points[i].first;
segtree[n + m + i + 1].min = points[i].first;
}
else
{
posRequete[points[i].first] = i;
}
}
for (int i = 0; i < m; i++)
{
int pos = posRequete[i];
node a;
a.max = points[pos];
a.min = points[pos];
update(n + m + i + pos, a);
decalage(1, 0, pos, n + m, n + m)
cout << segtree[1].reponse << ' ';
}
}