| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 701621 | lovrot | Event Hopping (BOI22_events) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm> a#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstring>
#include <map>
#define X first
#define Y second
#define pb push_back
using namespace std;
typedef pair<int, int> pii;
const int LOG = 18;
const int OFF = 1 << LOG;
int n, t;
int S[OFF], E[OFF], up[OFF][LOG], T[2 * OFF];
vector<int> vri, sweep;
map<int, int> mp;
int merge(int a, int b) {
if(a == -1 || b == -1) return a > -1 ? a : b;
return S[a] < S[b] ? a : b;
}
void update(int a, int val) {
a += OFF;
T[a] = merge(T[a], val);
a /= 2;
while(a) {
T[a] = merge(T[2 * a], T[2 * a + 1]);
a /= 2;
}
}
int query(int l, int r, int lo = 0, int hi = OFF, int x = 1) {
if(r <= lo || hi <= l) return -1;
if(l <= lo && hi <= r) return T[x];
int mi = (lo + hi) / 2;
return merge(query(l, r, lo, mi, 2 * x), query(l, r, mi, hi, 2 * x + 1));
}
bool comp(int a, int b) {
return E[a] == E[b] ? S[a] < S[b] : E[a] < E[b];
}
pii climb(int a, int b) {
int res = 0;
for(int i = LOG - 1; i >= 0; i--) {
if(up[b][i] == -1) continue;
else if(E[a] < S[up[b][i]]) {
b = up[b][i];
res += 1 << i;
}
}
if(E[a] < S[b] && up[b][0] != -1) {
b = up[b][0];
res++;
}
return {b, res};
}
int main() {
memset(up, -1, sizeof(up));
memset(T, -1, sizeof(T));
scanf("%d%d", &n, &t);
for(int i = 0; i < n; i++) {
scanf("%d%d", S + i, E + i);
vri.pb(S[i]);
vri.pb(E[i]);
//vri.pb(E[i] + 1);
}
sort(vri.begin(), vri.end());
vri.erase(unique(vri.begin(), vri.end()), vri.end());
for(int i = 0; i < (int) vri.size(); i++) mp[vri[i]] = i;
for(int i = 0; i < n; i++) {
S[i] = mp[S[i]];
E[i] = mp[E[i]];
//printf("Si = %d Ei = %d\n", S[i] + 1, E[i] + 1);
sweep.pb(i);
}
sort(sweep.begin(), sweep.end(), comp);
for(int i : sweep) {
up[i][0] = query(S[i], E[i] + 1);
update(E[i], i);
if(S[i] <= S[up[i][0]]) up[i][0] = -1;
//printf("UP%d = %d\n", i, up[i][0]);
}
for(int j = 1; j < LOG; j++)
for(int i = 0; i < n; i++)
if(up[i][j - 1] != -1) up[i][j] = up[up[i][j - 1]][j - 1];
for(int i = 0; i < t; i++) {
int s, e;
scanf("%d%d", &s, &e);
//printf("%d %d\n", s, e);
s--;
e--;
// if(t >= 20) continue;
if(e == s) {
printf("0\n");
} else if(E[e] < E[s]) {
printf("impossible\n");
} else {
pii r = climb(s, e);
if(S[r.X] <= E[s] && E[s] <= E[r.X]) printf("%d\n", r.Y + 1);
else printf("impossible\n");
}
}
return 0;
}
#include <cstring>
#include <map>
#define X first
#define Y second
#define pb push_back
using namespace std;
typedef pair<int, int> pii;
const int LOG = 18;
const int OFF = 1 << LOG;
int n, t;
int S[OFF], E[OFF], up[OFF][LOG], T[2 * OFF];
vector<int> vri, sweep;
map<int, int> mp;
int merge(int a, int b) {
if(a == -1 || b == -1) return a > -1 ? a : b;
return S[a] < S[b] ? a : b;
}
void update(int a, int val) {
a += OFF;
T[a] = merge(T[a], val);
a /= 2;
while(a) {
T[a] = merge(T[2 * a], T[2 * a + 1]);
a /= 2;
}
}
int query(int l, int r, int lo = 0, int hi = OFF, int x = 1) {
if(r <= lo || hi <= l) return -1;
if(l <= lo && hi <= r) return T[x];
int mi = (lo + hi) / 2;
return merge(query(l, r, lo, mi, 2 * x), query(l, r, mi, hi, 2 * x + 1));
}
bool comp(int a, int b) {
return E[a] == E[b] ? S[a] < S[b] : E[a] < E[b];
}
pii climb(int a, int b) {
int res = 0;
for(int i = LOG - 1; i >= 0; i--) {
if(up[b][i] == -1) continue;
else if(E[a] < S[up[b][i]]) {
b = up[b][i];
res += 1 << i;
}
}
if(E[a] < S[b] && up[b][0] != -1) {
b = up[b][0];
res++;
}
return {b, res};
}
int main() {
memset(up, -1, sizeof(up));
memset(T, -1, sizeof(T));
scanf("%d%d", &n, &t);
for(int i = 0; i < n; i++) {
scanf("%d%d", S + i, E + i);
vri.pb(S[i]);
vri.pb(E[i]);
//vri.pb(E[i] + 1);
}
sort(vri.begin(), vri.end());
vri.erase(unique(vri.begin(), vri.end()), vri.end());
for(int i = 0; i < (int) vri.size(); i++) mp[vri[i]] = i;
for(int i = 0; i < n; i++) {
S[i] = mp[S[i]];
E[i] = mp[E[i]];
//printf("Si = %d Ei = %d\n", S[i] + 1, E[i] + 1);
sweep.pb(i);
}
sort(sweep.begin(), sweep.end(), comp);
for(int i : sweep) {
up[i][0] = query(S[i], E[i] + 1);
update(E[i], i);
if(S[i] <= S[up[i][0]]) up[i][0] = -1;
//printf("UP%d = %d\n", i, up[i][0]);
}
for(int i = 0; i < n; i++)
for(int j = 1; j < LOG; j++)
if(up[i][j - 1] != -1) up[i][j] = up[up[i][j - 1]][j - 1];
for(int i = 0; i < t; i++) {
int s, e;
scanf("%d%d", &s, &e);
//printf("%d %d\n", s, e);
s--;
e--;
if(e == s) {
printf("0\n");
} else if(E[e] < E[s]) {
printf("impossible\n");
} else {
pii r = climb(s, e);
if(S[r.X] <= E[s] && E[s] <= E[r.X]) printf("%d\n", r.Y + 1);
else printf("impossible\n");
}
}
return 0;
}