제출 #444603

#제출 시각아이디문제언어결과실행 시간메모리
444603PeppaPigEvent Hopping 2 (JOI21_event2)C++14
0 / 100
63 ms21276 KiB
#include <bits/stdc++.h> #define pii pair<int, int> #define x first #define y second using namespace std; const int N = 1e5 + 5; int n, k; int L[N], R[N], par[N][18]; vector<int> coord, Q[N]; int solve(int l, int r) { int ret = 0; for(int i = 17; ~i; i--) if(par[l][i] <= r) { ret += (1 << i); l = par[l][i]; } return ret; } int main() { scanf("%d %d", &n, &k); for(int i = 1; i <= n; i++) { scanf("%d %d", L + i, R + i); coord.emplace_back(L[i]); coord.emplace_back(R[i]); } sort(coord.begin(), coord.end()); coord.resize(unique(coord.begin(), coord.end()) - coord.begin()); for(int i = 1; i <= n; i++) { L[i] = lower_bound(coord.begin(), coord.end(), L[i]) - coord.begin(); R[i] = lower_bound(coord.begin(), coord.end(), R[i]) - coord.begin(); Q[L[i]].emplace_back(i); } par[coord.size()][0] = coord.size(); for(int i = coord.size() - 1; ~i; i--) { par[i][0] = par[i + 1][0]; for(int idx : Q[i]) par[i][0] = min(par[i][0], R[idx]); } for(int j = 1; j <= 17; j++) for(int i = 0; i <= coord.size(); i++) par[i][j] = par[par[i][j - 1]][j - 1]; int mx_ans = solve(0, coord.size() - 1); if(mx_ans < k) return !printf("-1\n"); vector<int> ans; set<pii> S = { pii(0, 0), pii(coord.size() - 1, coord.size() - 1) }; for(int i = 1; i <= n && ans.size() < k; i++) { int l = prev(S.lower_bound(pii(L[i], -1e9)))->y; int r = S.lower_bound(pii(R[i], -1e9))->x; if(L[i] < l || r < R[i]) continue; int now = mx_ans - solve(l, r) + solve(l, L[i]) + 1 + solve(R[i], r); if(now >= k) { S.emplace(L[i], R[i]); ans.emplace_back(i); mx_ans = now; } } for(int x : ans) printf("%d\n", x); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

event2.cpp: In function 'int main()':
event2.cpp:48:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for(int i = 0; i <= coord.size(); i++)
      |                        ~~^~~~~~~~~~~~~~~
event2.cpp:58:41: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |     for(int i = 1; i <= n && ans.size() < k; i++) {
      |                              ~~~~~~~~~~~^~~
event2.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
event2.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf("%d %d", L + i, R + i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...