제출 #474447

#제출 시각아이디문제언어결과실행 시간메모리
474447PetyEvent Hopping 2 (JOI21_event2)C++14
0 / 100
76 ms17132 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double using namespace std; int n, k, dp[17][200004]; pair<int, int>event[100002]; int dist (int l, int r) { l = max(0, l); int ans = 0; for (int i = 16; i >= 0; i--) { if (dp[i][l] <= r) { l = dp[i][l]; ans += (1 << i); } } return ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> k; vector<int>norm; for (int i = 1; i <= n; i++) { int a, b; cin >> a >> b; event[i] = {a, b}; norm.push_back(a); norm.push_back(b); } sort(norm.begin(), norm.end()); int aux = 0; for (int i = 0; i < norm.size(); i++) { if (i == 0 || norm[i - 1] != norm[i]) { norm[aux++] = norm[i]; } } norm.resize(aux); for (int i = 0; i < aux + 1; i++) { dp[0][i] = aux + 1; } for (int i = 0; i < 17; i++) dp[i][aux + 1] = aux + 1; for (int i = 1; i <= n; i++) { event[i].first = lower_bound(norm.begin(), norm.end(), event[i].first) - norm.begin(); event[i].second = lower_bound(norm.begin(), norm.end(), event[i].second) - norm.begin(); dp[0][event[i].first] = min(dp[0][event[i].first], event[i].second); } for (int i = aux - 1; i >= 0; i--) { dp[0][i] = min(dp[0][i], dp[0][i + 1]); for (int j = 1; j < 17; j++) { dp[j][i] = dp[j - 1][dp[j - 1][i]]; } } set<pair<int, int> > s; s.insert({-1, -1}); s.insert({aux, aux}); int sum = dist(0, aux - 1); int newsum; vector<int>ans; for (int i = 1; i <= n; i++) { pair<int, int>p = event[i]; auto it = s.lower_bound({p.first, 0}); auto it2 = it; it2--; if (p.second > it->first || p.first < it2->second) continue; newsum = sum - dist(it2->second, it->first) + dist(it2->second, p.first) + dist(p.second, it->first) + 1; if (sum >= k) { s.insert(p); sum = newsum; ans.push_back(i); } if (ans.size() == k) break; } if (sum >= k && ans.size() == k) for (auto it : ans) { cout << it << "\n"; } else cout << "-1\n"; return 0; }

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

event2.cpp: In function 'int main()':
event2.cpp:37:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   for (int i = 0; i < norm.size(); i++) {
      |                   ~~^~~~~~~~~~~~~
event2.cpp:79:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   79 |     if (ans.size() == k)
      |         ~~~~~~~~~~~^~~~
event2.cpp:82:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   82 |   if (sum >= k && ans.size() == k)
      |                   ~~~~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...