oj.uz

답안 #417285

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
417285 2021-06-03T14:24:41 Z maomao90 Event Hopping 2 (JOI21_event2) C++17
7 / 100
 234 ms 28452 KB 
#include <bits/stdc++.h> 
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb emplace_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

#define INF 1000000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 200005

int n, k;
ii lr[MAXN];
vi events;
set<int> st;
map<int, int> mp;
int d[MAXN];
vi ans;

int v[MAXN * 4];
void update(int p, int x, int u, int lo, int hi) {
	int mid = lo + hi >> 1;
	if (lo == hi) {
		v[u] = x;
		return;
	}
	int lc = u * 2, rc = u * 2 + 1;
	if (p <= mid) update(p, x, lc, lo, mid);
	else update(p, x, rc, mid + 1, hi);
	v[u] = max(v[lc], v[rc]);
}
void update(int p, int x) {
	update(p, x, 1, 0, 2 * n);
}
int query(int s, int e, int u, int lo, int hi) {
	if (lo >= s && hi <= e) {
		return v[u];
	}
	int mid = lo + hi >> 1;
	int lc = u * 2, rc = u * 2 + 1;
	if (e <= mid) return query(s, e, lc, lo, mid);
	else if (s > mid) return query(s, e, rc, mid + 1, hi);
	else return max(query(s, e, lc, lo, mid), query(s, e, rc, mid + 1, hi));
}
int query(int s, int e) {
	return query(s, e, 1, 0, 2 * n);
}

int main() {
	scanf("%d%d", &n, &k);
	REP (i, 0, n) {
		scanf("%d%d", &lr[i].FI, &lr[i].SE);
		st.insert(lr[i].FI);
		st.insert(lr[i].SE);
	}
	int ptr = 0;
	for (auto i : st) {
		mp[i] = ptr++;
	}
	REP (i, 0, n) {
		lr[i].FI = mp[lr[i].FI];
		lr[i].SE = mp[lr[i].SE];
	}
	REP (i, 0, n) {
		if (events.empty() || lr[events.back()].FI != lr[i].FI ||
				lr[events.back()].SE > lr[i].SE) {
			mp[lr[i].FI] = events.size();
			events.pb(i);
		}
	}
	RREP (i, events.size() - 1, 0) {
		int l = lr[events[i]].FI, r = lr[events[i]].SE;
		d[i] = query(r, 2 * n) + 1;
		update(l, d[i]);
	}
	int prvr = -1;
	REP (i, 0, events.size()) {
		if (k == 0) break;
		int l = lr[events[i]].FI, r = lr[events[i]].SE;
		if (d[i] >= k && l >= prvr) {
			ans.pb(events[i]);
			prvr = r;
			k--;
		}
	}
	if (ans.empty()) {
		printf("-1\n");
		return 0;
	} else {
		for (int i : ans) {
			printf("%d\n", i + 1);
		}
	}
	return 0;
}

/*
4 2
1 4
3 5
4 9
7 10

12 3
1 4
1 8
1 3
1 2
1 4
3 8
3 5
3 9
6 11
6 10
6 12
6 7

6 1
1 7
2 5
2 4
4 8
4 7
8 9

6 4
1 3
1 2
2 4
4 5
5 6
6 7
*/

Compilation message

event2.cpp: In function 'void update(int, int, int, int, int)':
event2.cpp:40:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |  int mid = lo + hi >> 1;
      |            ~~~^~~~
event2.cpp: In function 'int query(int, int, int, int, int)':
event2.cpp:57:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |  int mid = lo + hi >> 1;
      |            ~~~^~~~
event2.cpp: In function 'int main()':
event2.cpp:8:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define REP(i, s, e) for (int i = s; i < e; i++)
......
   95 |  REP (i, 0, events.size()) {
      |       ~~~~~~~~~~~~~~~~~~~               
event2.cpp:95:2: note: in expansion of macro 'REP'
   95 |  REP (i, 0, events.size()) {
      |  ^~~
event2.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
event2.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |   scanf("%d%d", &lr[i].FI, &lr[i].SE);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 216 ms 28452 KB Output is correct
5 Correct 222 ms 28388 KB Output is correct
6 Correct 198 ms 28308 KB Output is correct
7 Correct 196 ms 28256 KB Output is correct
8 Correct 200 ms 28348 KB Output is correct
9 Correct 202 ms 28276 KB Output is correct
10 Correct 201 ms 28312 KB Output is correct
11 Correct 234 ms 28244 KB Output is correct
12 Correct 194 ms 28220 KB Output is correct
13 Correct 191 ms 28124 KB Output is correct
14 Correct 191 ms 28100 KB Output is correct
15 Correct 186 ms 28088 KB Output is correct
16 Correct 189 ms 27580 KB Output is correct
17 Correct 193 ms 27644 KB Output is correct
18 Correct 182 ms 27532 KB Output is correct
19 Correct 190 ms 27336 KB Output is correct
20 Correct 193 ms 27528 KB Output is correct
21 Correct 194 ms 27328 KB Output is correct
22 Correct 197 ms 27324 KB Output is correct
23 Correct 199 ms 27456 KB Output is correct
24 Correct 200 ms 27400 KB Output is correct
25 Correct 218 ms 27280 KB Output is correct
26 Correct 218 ms 27220 KB Output is correct
27 Correct 217 ms 27284 KB Output is correct
28 Correct 189 ms 27312 KB Output is correct
29 Correct 185 ms 27324 KB Output is correct
30 Correct 183 ms 27324 KB Output is correct
31 Correct 197 ms 27308 KB Output is correct
32 Correct 199 ms 27320 KB Output is correct
33 Correct 214 ms 27264 KB Output is correct
34 Correct 190 ms 27964 KB Output is correct
35 Correct 188 ms 27704 KB Output is correct
36 Correct 185 ms 27580 KB Output is correct
37 Correct 202 ms 28248 KB Output is correct
38 Correct 201 ms 28036 KB Output is correct
39 Correct 196 ms 28056 KB Output is correct
40 Correct 205 ms 27964 KB Output is correct
41 Correct 198 ms 28064 KB Output is correct
42 Correct 185 ms 27324 KB Output is correct
43 Correct 189 ms 28040 KB Output is correct
44 Correct 193 ms 28032 KB Output is correct
45 Correct 187 ms 28028 KB Output is correct
46 Correct 192 ms 28152 KB Output is correct

Subtask #2
0 / 1.0

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

Subtask #3
0 / 31.0

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

Subtask #4
0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 216 ms 28452 KB Output is correct
5 Correct 222 ms 28388 KB Output is correct
6 Correct 198 ms 28308 KB Output is correct
7 Correct 196 ms 28256 KB Output is correct
8 Correct 200 ms 28348 KB Output is correct
9 Correct 202 ms 28276 KB Output is correct
10 Correct 201 ms 28312 KB Output is correct
11 Correct 234 ms 28244 KB Output is correct
12 Correct 194 ms 28220 KB Output is correct
13 Correct 191 ms 28124 KB Output is correct
14 Correct 191 ms 28100 KB Output is correct
15 Correct 186 ms 28088 KB Output is correct
16 Correct 189 ms 27580 KB Output is correct
17 Correct 193 ms 27644 KB Output is correct
18 Correct 182 ms 27532 KB Output is correct
19 Correct 190 ms 27336 KB Output is correct
20 Correct 193 ms 27528 KB Output is correct
21 Correct 194 ms 27328 KB Output is correct
22 Correct 197 ms 27324 KB Output is correct
23 Correct 199 ms 27456 KB Output is correct
24 Correct 200 ms 27400 KB Output is correct
25 Correct 218 ms 27280 KB Output is correct
26 Correct 218 ms 27220 KB Output is correct
27 Correct 217 ms 27284 KB Output is correct
28 Correct 189 ms 27312 KB Output is correct
29 Correct 185 ms 27324 KB Output is correct
30 Correct 183 ms 27324 KB Output is correct
31 Correct 197 ms 27308 KB Output is correct
32 Correct 199 ms 27320 KB Output is correct
33 Correct 214 ms 27264 KB Output is correct
34 Correct 190 ms 27964 KB Output is correct
35 Correct 188 ms 27704 KB Output is correct
36 Correct 185 ms 27580 KB Output is correct
37 Correct 202 ms 28248 KB Output is correct
38 Correct 201 ms 28036 KB Output is correct
39 Correct 196 ms 28056 KB Output is correct
40 Correct 205 ms 27964 KB Output is correct
41 Correct 198 ms 28064 KB Output is correct
42 Correct 185 ms 27324 KB Output is correct
43 Correct 189 ms 28040 KB Output is correct
44 Correct 193 ms 28032 KB Output is correct
45 Correct 187 ms 28028 KB Output is correct
46 Correct 192 ms 28152 KB Output is correct
47 Correct 1 ms 204 KB Output is correct
48 Correct 1 ms 204 KB Output is correct
49 Incorrect 0 ms 204 KB Output isn't correct
50 Halted 0 ms 0 KB -