Cod sursa(job #1986923)

Utilizator ArkinyStoica Alex Arkiny Data 29 mai 2017 12:06:46
Problema Range minimum query Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.45 kb
#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;
}