Submission #597942

#	Time	Username	Problem	Language	Result	Execution time	Memory
597942		maomao90	Event Hopping (BOI22_events)	C++17	100 / 100	147 ms	37288 KiB

events

#include <bits/stdc++.h>
using namespace std;

#define REP(i, j, k) for (int i = j; i < k; i++)
#define RREP(i, j, k) for (int i = j; i >= k; i--)

template <class T>
inline bool mnto(T &a, const T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T &a, const T b) {return a < b ? a = b, 1 : 0;}

typedef long long ll;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int) x.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef tuple<int, int, int> iii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int MAXN = 200005;
const int INF = 1000000005;
const ll LINF = 1000000000000000005;
const int MAXL = 20;

struct event {
    int s, e, i;
};

int n, q;
event se[MAXN];
int mp[MAXN];
int p[MAXL][MAXN];

int m;
int sp[MAXL][MAXN];
int qmn(int s, int e) {
    int k = 31 - __builtin_clz(e - s + 1);
    return min(sp[k][s], sp[k][e - (1 << k) + 1]);
}


int main() {
#ifndef DEBUG
    ios::sync_with_stdio(0), cin.tie(0);
#endif
    cin >> n >> q;
    REP (i, 1, n + 1) {
	cin >> se[i].s >> se[i].e;
	se[i].i = i;
    }
    sort(se + 1, se + n + 1, [&] (event l, event r) {
	    return l.s < r.s;
	    });
    vii disc;
    REP (i, 1, n + 1) {
	mp[se[i].i] = i;
	disc.pb({se[i].s, i});
	disc.pb({se[i].e, i + n});
    }
    sort(ALL(disc));
    int prv = -1;
    for (auto [x, i] : disc) {
	if (x != prv) {
	    prv = x;
	    m++;
	}
	if (i <= n) {
	    se[i].s = m;
	} else {
	    se[i - n].e = m;
	}
    }
    REP (i, 1, n + 1) {
	cerr << i << ": " << se[i].s << ' ' << se[i].e << '\n';
    }
    memset(p, -1, sizeof p);
    REP (i, 1, m + 1) {
	sp[0][i] = INF;
    }
    REP (i, 1, n + 1) {
	mnto(sp[0][se[i].e], i);
    }
    REP (k, 1, MAXL) {
	REP (i, 1, m + 1 - (1 << k - 1)) {
	    sp[k][i] = min(sp[k - 1][i], sp[k - 1][i + (1 << k - 1)]);
	}
    }
    REP (i, 1, n + 1) {
	p[0][i] = qmn(se[i].s, se[i].e);
	cerr << i << " -> " << p[0][i] << '\n';
    }
    /*
    REP (i, 1, n + 1) {
	ii mn = {INF, -1};
	REP (j, 1, n + 1) {
	    if (i == j) {
		continue;
	    }
	    if (se[i].s <= se[j].e && se[j].e <= se[i].e) {
		mnto(mn, {se[j].s, j});
	    }
	}
	p[0][i] = mn.SE;
	cerr << i << " -> " << p[0][i] << '\n';
    }
    */
    REP (k, 1, MAXL) {
	REP (i, 1, n + 1) {
	    if (p[k - 1][i] == -1) {
		p[k][i] = -1;
	    } else {
		p[k][i] = p[k - 1][p[k - 1][i]];
	    }
	}
    }
    while (q--) {
	int a, b; cin >> a >> b;
	a = mp[a]; b = mp[b];
	if (a == b) {
	    cout << 0 << '\n';
	    continue;
	}
	if (se[b].s <= se[a].e && se[a].e <= se[b].e) {
	    cout << 1 << '\n';
	    continue;
	}
	if (se[a].e > se[b].e) {
	    cout << "impossible\n";
	    continue;
	}
	int ans = 0;
	RREP (k, MAXL - 1, 0) {
	    if (p[k][b] == -1) {
		continue;
	    }
	    if (se[p[k][b]].s > se[a].e) {
		b = p[k][b];
		ans += 1 << k;
	    }
	}
	if (p[0][b] != -1 && se[p[0][b]].s <= se[a].e) {
	    ans += 2;
	    cout << ans << '\n';
	} else {
	    cout << "impossible\n";
	}
    }
    return 0;
}

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:93:29: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   93 |  REP (i, 1, m + 1 - (1 << k - 1)) {
      |                           ~~^~~
events.cpp:4:42: note: in definition of macro 'REP'
    4 | #define REP(i, j, k) for (int i = j; i < k; i++)
      |                                          ^
events.cpp:94:57: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   94 |      sp[k][i] = min(sp[k - 1][i], sp[k - 1][i + (1 << k - 1)]);
      |                                                       ~~^~~

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