oj.uz

Submission #574190

# Submission time Handle Problem Language Result Execution time Memory
574190 2022-06-08T07:12:49 Z 8e7 Event Hopping (BOI22_events) C++17
30 / 100
 202 ms 28316 KB 
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int inf = 1<<30;
pii seg[maxn];
vector<int> ev[maxn];
bool on[maxn];
int to[17][maxn];

struct query{
	int l, r, id;
	query(){l = r = id = 0;}
	query(int a, int b, int c){l = a, r = b, id = c;}
};
vector<query> que[maxn];
struct BIT{
	int bit[maxn];
	void modify(int ind, int val) {
		for (;ind < maxn;ind += ind & (-ind)) bit[ind] += val;
	}
	int query(int ind) {
		int ret = 0;
		for (;ind > 0;ind -= ind &(-ind)) ret += bit[ind];
		return ret;
	}
} bit;

int ans[maxn];
int main() {
	io
	int n, q;
	cin >> n >> q;
	{
		vector<int> val;
		for (int i = 1;i <= n;i++) {
			cin >> seg[i].ff >> seg[i].ss;
			val.push_back(seg[i].ff);
			val.push_back(seg[i].ss);
		}
		sort(val.begin(), val.end());
		val.resize(int(unique(val.begin(), val.end()) - val.begin()));
		for (int i = 1;i <= n;i++) {
			seg[i].ff = lower_bound(val.begin(), val.end(), seg[i].ff) - val.begin();
			seg[i].ss = lower_bound(val.begin(), val.end(), seg[i].ss) - val.begin();
			ev[seg[i].ff].push_back(i);
			ev[seg[i].ss].push_back(i);
		}
	}
	seg[0].ss = inf;
	priority_queue<pii, vector<pii>, less<pii> > pq;
	for (int i = 0;i < 2*n;i++) {
		vector<int> tmp;
		for (int j:ev[i]) {
			if (!on[j]) {
				on[j] = 1;
				pq.push({seg[j].ss, j});
			} else {
				tmp.push_back(j);
				on[j] = 0;
			}
		}
		while (pq.size() && pq.top().ff <= i) pq.pop();
		for (int j:tmp) {
			to[0][j] = (pq.size() ? pq.top().ss : 0);
		}
	}
	//pary(to[0], to[0] + n + 1);
	for (int i = 1;i < 17;i++) {
		for (int j = 0;j <= n;j++) to[i][j] = to[i-1][to[i-1][j]];
	}
	for (int id = 0;id < q;id++) {
		int s, t;
		cin >> s >> t;	
		ans[id] = -1;
		if (seg[t].ss >= seg[s].ss) {
			if (seg[t].ff <= seg[s].ss) {
				if (s == t) ans[id] = 0;
				else ans[id] = 1;
			} else {
				int cur = s, dis = 0;
				for (int i = 16;i >= 0;i--) {
					if (seg[to[i][cur]].ss < seg[t].ff) {
						cur = to[i][cur];
						dis += 1<<i;
					}
				}
				ans[id] = dis;
				que[seg[cur].ss].push_back(query(seg[t].ff, seg[t].ss, id));
			}
		}
	}
	for (int i = 0;i < 2*n;i++) {
		for (int j:ev[i]) {
			if (!on[j]) {
				on[j] = 1;
				bit.modify(seg[j].ss, 1);
			}
		}
		for (auto [l, r, id]:que[i]) {
			if (bit.query(r) - bit.query(l-1) > 0) ans[id] += 2;
			else ans[id] = -1;
		}
	}
	for (int i = 0;i < q;i++) {
		if (ans[i] == -1) cout << "impossible\n";
		else cout << ans[i] << "\n";
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 126 ms 25512 KB Output is correct
3 Correct 143 ms 24328 KB Output is correct
4 Correct 202 ms 24140 KB Output is correct
5 Correct 148 ms 24628 KB Output is correct
6 Correct 148 ms 25136 KB Output is correct
7 Correct 148 ms 25140 KB Output is correct
8 Correct 144 ms 28316 KB Output is correct
9 Correct 163 ms 27496 KB Output is correct
10 Correct 168 ms 23588 KB Output is correct
11 Correct 162 ms 25152 KB Output is correct
12 Correct 82 ms 25012 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 5 ms 9796 KB Output is correct
3 Correct 8 ms 9940 KB Output is correct
4 Correct 7 ms 9920 KB Output is correct
5 Incorrect 6 ms 9940 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 5 ms 9796 KB Output is correct
3 Correct 8 ms 9940 KB Output is correct
4 Correct 7 ms 9920 KB Output is correct
5 Incorrect 6 ms 9940 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 5 ms 9796 KB Output is correct
3 Correct 8 ms 9940 KB Output is correct
4 Correct 7 ms 9920 KB Output is correct
5 Incorrect 6 ms 9940 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 25640 KB Output is correct
2 Correct 153 ms 24200 KB Output is correct
3 Correct 177 ms 24160 KB Output is correct
4 Correct 134 ms 27528 KB Output is correct
5 Correct 158 ms 23560 KB Output is correct
6 Correct 170 ms 27496 KB Output is correct
7 Correct 174 ms 27440 KB Output is correct
8 Correct 158 ms 27260 KB Output is correct
9 Correct 130 ms 25740 KB Output is correct
10 Correct 167 ms 27828 KB Output is correct
11 Correct 160 ms 27276 KB Output is correct
12 Correct 160 ms 27412 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 126 ms 25512 KB Output is correct
3 Correct 143 ms 24328 KB Output is correct
4 Correct 202 ms 24140 KB Output is correct
5 Correct 148 ms 24628 KB Output is correct
6 Correct 148 ms 25136 KB Output is correct
7 Correct 148 ms 25140 KB Output is correct
8 Correct 144 ms 28316 KB Output is correct
9 Correct 163 ms 27496 KB Output is correct
10 Correct 168 ms 23588 KB Output is correct
11 Correct 162 ms 25152 KB Output is correct
12 Correct 82 ms 25012 KB Output is correct
13 Correct 5 ms 9812 KB Output is correct
14 Correct 5 ms 9796 KB Output is correct
15 Correct 8 ms 9940 KB Output is correct
16 Correct 7 ms 9920 KB Output is correct
17 Incorrect 6 ms 9940 KB Output isn't correct
18 Halted 0 ms 0 KB -