# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
494365 | jasen_penchev | Floppy (RMI20_floppy) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "floppy.h"
#include <iostream>
#include <utility>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#define endl '\n'
using namespace std;
const int MAXN = 40000;
int deg[MAXN + 5];
int tsort[MAXN + 5];
vector<int> G[MAXN + 5];
pair<int, int> tree[4 * MAXN + 5];
void save_to_floppy(const string &bits);
void read_array(int subtask_id, const vector<int> &v)
{
int n = v.size();
string bits = "";
stack<int> st;
for (int i = 0; i < n; ++ i)
{
while (st.size() and v[st.top()] < v[i])
{
bits += '1';
st.pop();
}
st.push(i);
bits += '0';
}
save_to_floppy(bits);
}
void build(int v, int l, int r)
{
if (l == r)
{
tree[v] = make_pair(tsort[l], l);
return;
}
int mid = (l + r) / 2;
build(2 * v, l, mid);
build(2 * v + 1, mid + 1, r);
tree[v] = max(tree[2 * v], tree[2 * v + 1]);
}
void query(int v, int l, int r, int L, int R)
{
if (R < l or r < L) return make_pair(0, -1);
if (L <= l and r <= R) return tree[v];
int mid = (l + r) / 2;
pair<int, int> ret = make_pair(0, -1);
ret = max(ret, query(2 * v, l, mid, L, R));
ret = max(ret, query(2 * v + 1, mid + 1, r, L, R));
return ret;
}
vector<int> solve_queries(int subtask_id, int n, const string &bits, const vector<int> &a, const vector<int> &b)
{
int pos = 0;
stack<int> st;
for (int i = 0; i < n; ++ i)
{
while (bits[pos] == '1')
{
G[i].push_back(st.top());
st.pop();
pos++;
}
if (st.size()) G[st.top()].push_back(i);
st.push(i);
pos++;
}
for (int u = 0; u < n; ++ u)
{
for (auto v : G[u])
{
deg[v]++;
}
}
queue<int> q;
for (int u = 0; u < n; ++ u)
{
if (deg[u] == 0) q.push(u);
}
for (int i = 0; i < n; ++ i)
{
int u = q.front();
q.pop();
tsort[u] = n - i;
for (auto v : G[u])
{
deg[v]--;
if (deg[v] == 0) q.push(v);
}
}
build(1, 0, n - 1);
vector<int> v;
int m = a.size();
for (int i = 0; i < m; ++ i)
{
v.push_back(query(1, 0, n - 1, a[i], b[i]).second);
}
return v;
}