Submission #1120830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120830		vjudge1	Event Hopping (BOI22_events)	C++17	0 / 100	154 ms	16604 KiB

events

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <fstream>
#include <unordered_map>
using namespace std;
#define int long long
#define ll long long
#define ff first
#define ss second
#define pb push_back 
#define pf push_front
#define UseOFF ios_base::sync_with_stdio(0);cin.tie(0), cout.tie(0);
#define sz size
#define ins insert
#define new junkedseduneon
#define prev usfdjik
const ll N = 2e6 + 111;
pair <ll, ll> a[N];
map <pair <ll, ll>, ll> ans;
map <pair <ll, ll>, ll> mp;
void solve() {
	ll n, q;
	cin >> n >> q;
	vector < pair <ll, ll> > v;
	for(int i = 1; i <= n; i++) {
		cin >> a[i].ff >> a[i].ss;
		v.pb({a[i].ss, a[i].ff});
		mp[{a[i].ff, a[i].ss}] = i;
	}
	sort(v.begin(), v.end());
	for(int i = 0; i < v.sz(); i++) {
		a[i + 1].ff = v[i].ss;
		a[i + 1].ss = v[i].ff;
		//cout << a[i].ff << " " << a[i].ss << " || " << v[i].ss << " " << v[i].ff << '\n';
	}
	ll x = 1;
	ll p = 0;
	for(int i = 1; i <= n; i++) {
	    //cout << a[i].ff << " " << a[i].ss << '\n';
	    if(a[i].ff > a[i - 1].ss) {
	        x += n + n;
	    }
	    ans[{a[i].ff, a[i].ss}] = x;
	    x++;
	}
	for(int i = 1; i <= q; i++) {
		ll s, f;
		cin >> s >> f;
		if(s == f) {
		    cout << "0\n";
		    continue;
		}
		//cout << i << " - " << q << endl;
		//cout << s << " " << f << " ||  " << a[f].ff << " " << a[f].ss << " || " << a[s].ff << " " << a[s].ss << '\n';
		if(ans[{a[f].ff, a[f].ss}] - ans[{a[s].ff, a[s].ss}] < 0 || ans[{a[f].ff, a[f].ss}] - ans[{a[s].ff, a[s].ss}] >= n) {
			cout << "impossible\n";
		}
		else {
		    //cout << s << " " << f << " ||  " << a[f].ff << " " << a[f].ss << " || " << a[s].ff << " " << a[s].ss << '\n';
			cout << ans[{a[f].ff, a[f].ss}] - ans[{a[s].ff, a[s].ss}] << '\n';
		}
	}
}
signed main()
{
	UseOFF
    ll ttt = 1;
    //cin >> ttt;
    while(ttt--)
    {
        solve();
    }
}

Compilation message (stderr)

events.cpp: In function 'void solve()':
events.cpp:53:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  for(int i = 0; i < v.sz(); i++) {
      |                 ~~^~~~~~~~
events.cpp:59:5: warning: unused variable 'p' [-Wunused-variable]
   59 |  ll p = 0;
      |     ^

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