Submission #588935

#	Time	Username	Problem	Language	Result	Execution time	Memory
588935		pooyashams	Event Hopping (BOI22_events)	C++14	100 / 100	280 ms	53516 KiB

events

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <iomanip>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define endl '\n'

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int maxn = 2e5+10;
const int lgmx = 20;
const int inf = 1e9;

#define X first
#define Y second

pii segs[maxn];
int alxs[maxn];
pii mn[maxn][lgmx];
map<int, int> mp;

int lft[maxn][lgmx];

int n;

inline void compress()
{
	for(int i = 0; i < n; i++)
	{
		alxs[2*i] = segs[i].X;
		alxs[2*i+1] = segs[i].Y;
	}
	sort(alxs, alxs+2*n);
	int c = 0;
	mp[alxs[0]] = c++;
	for(int i = 1; i < 2*n; i++)
	{
		if(alxs[i] != alxs[i-1])
			mp[alxs[i]] = c++;
	}
	for(int i = 0; i < n; i++)
	{
		segs[i].X = mp[segs[i].X];
		segs[i].Y = mp[segs[i].Y];
		//cerr << segs[i].X << " " << segs[i].Y << endl;
	}
}

inline pii get(int l, int r)
{
	int x = __lg(r-l);
	return min( mn[l][x], mn[r-(1<<x)][x] );
}

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int q; cin >> n >> q;
	for(int i = 0; i < n; i++)
		cin >> segs[i].first >> segs[i].second;
	compress();
	for(int j = 0; j < maxn; j++)
		for(int i = 0; i < lgmx; i++)
			mn[j][i] = pii(inf, inf);
	for(int i = 0; i < n; i++)
		mn[segs[i].Y][0] = min(mn[segs[i].Y][0], pii(segs[i].X, i));
	for(int k = 1; k < lgmx; k++)
	{
		int x = (1<<(k-1));
		for(int i = 0; i < 2*n; i++)
		{
			mn[i][k] = min( mn[i][k-1], mn[ min(2*n-1, i+x) ][k-1] );
		}
	}
	//for(int i = 0; i < 12; i++) cerr << i << ": " << mn[i][1].X << "," << mn[i][1].Y << endl; cerr << endl;
	for(int i = 0; i < n; i++)
	{
		pii p = get(segs[i].X, segs[i].Y+1);
		if(p.X >= segs[i].X)
			lft[i][0] = i;
		else
			lft[i][0] = p.Y;
		//cerr << lft[i][0] << endl;
	}
	for(int k = 1; k < lgmx; k++)
	{
		for(int i = 0; i < n; i++)
			lft[i][k] = lft[lft[i][k-1]][k-1];
	}
	while(q--)
	{
		int s, e; cin >> s >> e;
		s--; e--;
		if(segs[s].Y > segs[e].Y or segs[lft[e][lgmx-1]].X > segs[s].Y)
		{
			cout << "impossible" << endl;
			continue;
		}
		if(s == e)
		{
			cout << 0 << endl;
			continue;
		}
		if(segs[e].X <= segs[s].Y and segs[s].Y <= segs[e].Y)
		{
			cout << 1 << endl;
			continue;
		}
		int x = e;
		int t = 2;
		//cerr << lft[e][0] << endl;
		for(int k = lgmx-1; k >= 0; k--)
		{
			if(segs[lft[x][k]].X > segs[s].Y)
			{
				t += (1<<k);
				x = lft[x][k];
			}
		}
		cout << t << endl;
	}
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30