oj.uz

Submission #750728

# Submission time Handle Problem Language Result Execution time Memory
750728 2023-05-30T08:21:36 Z Melika0gh Event Hopping (BOI22_events) C++17
0 / 100
 1071 ms 524288 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define sync 	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pii	pair<int, int>
#define pb	push_back
#define mp	make_pair
#define fi	first
#define se	second

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e5 + 10, inf = 1e9 + 7, mood = 1e9+7, mood2 = 19025953, base = 31, maxsq = 400, maxlg = 20; 
vector<pii> query[maxn];
int s[maxn], f[maxn], ans[maxn];
vector<int> order;
int n, q;

bool cmp(int a, int b)
{
	return mp(s[a], f[a]) < mp(s[b], f[b]);
}

bool cmp2(int a, int b)
{
	return mp(f[a], s[a]) < mp(f[b], s[b]);
}

int main()
{
	sync;
	cin >> n >> q;
	for(int i = 1; i <= n; i++)
		cin >> s[i] >> f[i], order.pb(i);

	for(int i = 0; i < q; i++)
	{
		int ss, ff;
		cin >> ss >> ff;
		query[ss].pb(mp(ff, i));
		ans[i] = 0 - maxn;
	}

	sort(order.begin(), order.end(), cmp);

	for(int i = 0; i < n; i++)
	{
		int v = order[i];
		vector<int> vc, vc2;
		int j = i+1;
		int u;
		if(j < n)
		{
			u = order[j];
			while(s[u] <= f[v] && j < n)
			{
				vc.pb(f[u]);
				vc2.pb(u);
			
				j++;
				if(j >= n)
					break;

				u = order[j];
			}
		}

		if(!vc.empty())
		{
			sort(vc.begin(), vc.end());
			sort(vc2.begin(), vc2.end(), cmp2);
		}

		for(auto x : query[v])
		{
		//	cout << v << endl;
			u = x.fi;
			int ind = x.se;
			if(u == v)
			{
				ans[ind] += maxn;
				continue;
			}	

			if(vc.empty())
				continue;

			if(vc.back() <= f[u])
			{
				ans[ind]++;
				int tmpp = lower_bound(vc.begin(), vc.end(), vc.back()) - vc.begin();
				query[vc2[tmpp]].pb(x);
				continue;
			}	

			int tmp = lower_bound(vc.begin(), vc.end(), f[u]) - vc.begin();
			while(vc[tmp] > f[u] && tmp > 0)
				tmp--;

			if(vc[tmp] > f[u])
				continue;

			ans[ind]++;
			query[vc2[tmp]].pb(x);
		}

		query[v].clear();

	}

	for(int i = 0; i < q; i++)
	{
		if(ans[i] < 0)
			cout << "impossible" << '\n';
		else
			cout << ans[i] << '\n';
	}

}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Runtime error 1053 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 3 ms 3668 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2900 KB Output is correct
6 Incorrect 17 ms 2644 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 3 ms 3668 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2900 KB Output is correct
6 Incorrect 17 ms 2644 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 3 ms 3668 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2900 KB Output is correct
6 Incorrect 17 ms 2644 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1071 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Runtime error 1053 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -