oj.uz

답안 #944068

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
944068 2024-03-12T08:00:30 Z pan Event Hopping (BOI22_events) C++17
0 / 100
 219 ms 42532 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include "bits_stdc++.h"
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
using namespace std;
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, srb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<pi, ll> pii;

ll const INF = 1e13;
bool compare(pii a, pii b)
{
	if (a.f.s==b.f.s) return a.f.f<b.f.f;
	return a.f.s<b.f.s;
}
// RMQ
struct node {
    int s, e, m; 
    pi val;
    node * l, * r; 
    node(int S, int E) { 
        s = S, e = E, m = (s + e) / 2;
        val = mp(INF, -1);
        if (s != e) { 
            l = new node(s, m); 
            r = new node(m + 1, e); 
        }
    }
    void update(int X, pi V) { 
        if (s == e)  {val = min(val, V);}
        else { 
            if (X <= m) l -> update(X, V); 
            else r -> update(X, V); 
            val = max(val = l -> val, r -> val); 
        }
    }
    pi query(int S, int E) {
        if (s == S && e == E) return val;
        else if (E <= m) return l -> query(S, E);
        else if (S >= m + 1) return r -> query(S, E);
        else return min(l -> query(S, m), r -> query(m + 1, E));
    }
}* root;

// Twok decomp
ll twok[100005][25];
int main()
{
	ll n,q, l, r;
	input2(n,q);
	vector<pii> eve(n);
	vector<pi> save(n);
	vector<ll> dis;
	for (ll i=0; i<n; ++i) {input2(save[i].f, save[i].s); eve[i] = mp(save[i], i); dis.pb(save[i].f), dis.pb(save[i].s);}
	discretize(dis);
	sort(eve.begin(), eve.end(), compare);
	root = new node(0, dis.size()-1);
	for (ll i=0; i<n; ++i)
	{
		ll l = lb(dis.begin(), dis.end(), eve[i].f.f)-dis.begin(), r = lb(dis.begin(), dis.end(), eve[i].f.s)-dis.begin(), ind = eve[i].s;
		root->update(r, mp(l, ind));
		pi nxt = root->query(l, r);
		if (nxt.f>=l) twok[ind][0] = -1;
		else  twok[ind][0] = nxt.s;
	}
	for (ll k=1; k<20; ++k)
	{
		for (ll x = 0; x<n; ++x)
		{
			if (twok[x][k-1]==-1) twok[x][k]=-1;
			else twok[x][k] = twok[twok[x][k-1]][k-1];
		}
	}
	while (q--)
	{
		input2(l, r);
		l--; r--;
		ll ans = 0;
		if (l==r) {print(0LL, '\n'); continue;}
		if (save[l].s>save[r].s){ cout << "impossible" << '\n'; continue;}
		if (save[r].f<=save[l].s) print(1LL, '\n');
		for (ll i=19; i>=0; --i)
		{
			if (twok[r][i]==-1) continue;
			if (save[twok[r][i]].f<= save[l].s) continue;
			r = twok[r][i];
			ans += (1LL<<i);
		}
		if (twok[r][0]==-1) {cout << "impossible" << endl; continue;}
		print(ans+2, '\n');
	}
	return 0;
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:12:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input2(x, y) scanf("%lld%lld", &x, &y);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~
events.cpp:71:2: note: in expansion of macro 'input2'
   71 |  input2(n,q);
      |  ^~~~~~
events.cpp:12:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input2(x, y) scanf("%lld%lld", &x, &y);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~
events.cpp:75:26: note: in expansion of macro 'input2'
   75 |  for (ll i=0; i<n; ++i) {input2(save[i].f, save[i].s); eve[i] = mp(save[i], i); dis.pb(save[i].f), dis.pb(save[i].s);}
      |                          ^~~~~~
events.cpp:12:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input2(x, y) scanf("%lld%lld", &x, &y);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~
events.cpp:97:3: note: in expansion of macro 'input2'
   97 |   input2(l, r);
      |   ^~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 219 ms 42532 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 2 ms 2652 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 2 ms 2652 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 2 ms 2652 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 218 ms 42176 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 219 ms 42532 KB Output isn't correct
3 Halted 0 ms 0 KB -