이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// M
#include<bits/stdc++.h>
#include "meetings.h"
using namespace std;
typedef long long ll;
const int N = 100005, MXN = 5005, LG = 20;
int n, q, A[N], L[N], R[N], Nxt[N][LG], MX[N][LG];
int mx[MXN][MXN];
ll le[MXN][MXN], ri[MXN][MXN];
vector < ll > Brute()
{
for (int len = 1; len <= n; len ++)
{
for (int l = 1, r = len; r <= n; l ++, r ++)
{
if (len == 1)
{
mx[l][r] = A[l];
le[l][r] = ri[l][r] = A[l];
continue;
}
mx[l][r] = max(mx[l][r - 1], A[r]);
le[l][r] = le[l][r - 1] + mx[l][r];
ri[l][r] = ri[l + 1][r] + mx[l][r];
}
}
vector < ll > res;
for (int i = 1; i <= q; i ++)
{
ll Mn = 1e18;
for (int j = L[i]; j <= R[i]; j ++)
Mn = min(Mn, le[j][R[i]] + ri[L[i]][j] - A[j]);
res.push_back(Mn);
}
return res;
}
vector < long long > minimum_costs(vector < int > _H, vector < int > _L, vector < int > _R)
{
n = (int)_H.size();
q = (int)_L.size();
for (int i = 1; i <= n; i ++)
A[i] = _H[i - 1];
for (int i = 1; i <= q; i ++)
L[i] = _L[i - 1] + 1, R[i] = _R[i - 1] + 1;
if (n <= 5000)
return Brute();
for (int i = 1; i <= n; i ++)
assert(A[i] <= 2);
int last = n + 1;
for (int i = n; i; i --)
{
Nxt[i][0] = last;
MX[i][0] = last - i - 1;
if (A[i] == 2)
last = i;
}
Nxt[n + 1][0] = n + 1;
for (int j = 1; j < LG; j ++)
for (int i = 1; i <= n; i ++)
{
Nxt[i][j] = Nxt[Nxt[i][j - 1]][j - 1];
MX[i][j] = max(MX[i][j - 1], MX[Nxt[i][j - 1]][j - 1]);
}
vector < int > vec;
for (int i = 1; i <= n; i ++)
if (A[i] == 2)
vec.push_back(i);
vector < ll > res;
for (int i = 1; i <= q; i ++)
{
int lb = lower_bound(vec.begin(), vec.end(), L[i]) - vec.begin();
int Mx = 0;
if (lb == vec.size() || vec[lb] > R[i])
Mx = R[i] - L[i] + 1;
else
{
int nw = vec[lb];
Mx = max(Mx, nw - L[i]);
for (int j = LG - 1; j >= 0; j --)
if (Nxt[nw][j] <= R[i])
Mx = max(Mx, MX[nw][j]), nw = Nxt[nw][j];
assert(Nxt[nw][0] > R[i]);
Mx = max(Mx, R[i] - nw);
}
ll sm = (R[i] - L[i] + 1) * 2LL - Mx;
res.push_back(sm);
}
return res;
}
컴파일 시 표준 에러 (stderr) 메시지
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:82:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | if (lb == vec.size() || vec[lb] > R[i])
| ~~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |