Pagini recente » Cod sursa (job #2314590) | Cod sursa (job #3223403) | Cod sursa (job #2584410) | Cod sursa (job #305699) | Cod sursa (job #1986923)
#include<fstream>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
int RMQ[20][100010];
int p[100010];
ifstream in("queries.in");
ofstream out("queries.out");
int query(int x, int y)
{
return max(RMQ[p[y - x + 1]][x], RMQ[p[y - x + 1]][y - (1 << p[y - x + 1]) + 1]);
}
struct comp
{
bool operator() (const pair<int,int> &pr1, const pair<int,int> &pr2) const
{
if (pr1.second - pr1.first + 1 != pr2.second - pr2.first + 1)
return pr1.second - pr1.first + 1 < pr2.second - pr2.first + 1;
else if (pr1.first != pr2.first)
return pr1.first < pr2.first;
else
return pr1.second < pr2.second;
}
};
set<pair<int, int> > was;
set<pair<int, int>,comp> inter[100010];
map<int, int> mp;
int v[100010];
int main()
{
int t;
in >> t;
for (int i = 2; i <= 100000; ++i)
p[i] = 1 + p[i / 2];
t = 1;
while (t--)
{
was.clear();
int N, M;
in >> N >> M;
mp.clear();
for (int i = 1; i <= 100000; ++i)
inter[i].clear();
for (int i = 1; i <= N; ++i)
{
in >> v[i];
mp[v[i]] = i;
RMQ[0][i] = v[i];
}
for (int i = 1; i <= p[N]; ++i)
for (int j = 1; (j + (1 << i) - 1) <= N; ++j)
RMQ[i][j] = max(RMQ[i - 1][j], RMQ[i - 1][j + (1 << (i - 1))]);
/*for (int i = 1; i <= N; ++i)
{
int l = i, r = N;
int mid = 0;
pair<int, int> pr;
while (l <= r)
{
mid = (l + r) / 2;
if (query(i,mid) > v[i])
r = mid - 1;
else
l= mid + 1;
}
pr.second = r;
l = 1, r = i;
while (l <= r)
{
mid = (l + r) / 2;
if (query(mid,i) > v[i])
l= mid + 1;
else
r= mid - 1;
}
pr.first = l;
inter[mp[v[i]]].insert(pr);
}*/
int i=0;
long long s = 0;
for ( i = 1; i <= M; ++i)
{
int el;
in >> el;
/*if (!inter[mp[el]].size())
break;
else
{
pair<int, int> pr = (*inter[mp[el]].rbegin());
s += pr.second - pr.first + 1;
inter[mp[el]].erase(pr);
was.insert(pr);
if (pr.second - pr.first + 1 != 1)
{
pr.second -= 1;
if (was.find(pr) == was.end() && query(pr.first,pr.second) == el)
inter[mp[el]].insert(pr);
pr.second += 1;
pr.first += 1;
if (was.find(pr) == was.end() && query(pr.first, pr.second) == el)
inter[mp[el]].insert(pr);
}
}
*/
}
if (i <= M)
out << -1 << "\n";
else
out << s << "\n";
}
return 0;
}