# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
494458 | iulia13 | Floppy (RMI20_floppy) | C++14 | 103 ms | 15144 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "floppy.h"
using namespace std;
const int NMAX = 100005;
const int LG = 20;
int st[NMAX];
int rmq[NMAX][LG];
int lft[NMAX];
///void save_to_floppy(string &bits);
void read_array(int subtask_id, const vector <int> &v)
{
string a = "";
int k = 0, n = v.size();
for (int i = 0; i < n; i++)
{
while (k && st[k] < v[i])
{
a += '1';
k--;
}
st[++k] = v[i];
a += '0';
}
save_to_floppy(a);
}
vector <int> sol;
int lg[NMAX];
vector<int> solve_queries(int subtask_id, int N, const string &bits, const vector<int> &a, const vector<int> &b)
{
int k = 0, m = bits.size(), jj = 0;
for (int i = 1; i <= N; i++)
{
if (1 < i)
lg[i] = 1 + lg[i / 2];
while(k && bits[jj] == '1')
k--, jj++;
jj++;
lft[i] = st[k];
st[++k] = i;
rmq[i][0] = i;
}
for (int j = 1; (1 << j) <= N; j++)
for (int i = 1; i <= N; i++)
{
rmq[i][j] = rmq[i][j - 1];
if (lft[rmq[i + (1 << (j - 1))][j - 1]] < i)
rmq[i][j] = rmq[i + (1 << (j - 1))][j - 1];
}
int q = a.size();
for (int i = 0; i < q; i++)
{
int aa = a[i], bb = b[i];
aa++, bb++;
int lgg = lg[bb - aa + 1];
int ans = rmq[aa][lgg];
if (lft[rmq[bb - (1 << lgg) + 1][lgg]] < aa)
ans = rmq[bb - (1 << lgg) + 1][lgg];
sol.push_back(ans - 1);
}
return sol;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |