Submission #601280

#TimeUsernameProblemLanguageResultExecution timeMemory
601280lordlorincEvent Hopping 2 (JOI21_event2)C++17
100 / 100
254 ms22156 KiB
#include <bits/stdc++.h> using namespace std; vector<pair<pair<int, int>, int> > sor, sor2; vector<vector<int> > tabla; set<pair<pair<int, int>, int> > ck; int maxDb(int l, int r){ int pos = lower_bound(sor.begin(), sor.end(), make_pair(make_pair(l, 1000000003), -1)) - sor.begin() - 1; int res = 0; for (int i = tabla[0].size() - 1; i >= 0; i--){ if (tabla[pos][i] == -1) continue; if (sor[tabla[pos][i]].first.first <= r){ pos = tabla[pos][i]; res += (1 << i); } } // cout << l << " " << r << " " << res << endl; return res; } int main(){ int n, m; cin >> n >> m; sor.resize(n + 2); for (int i = 0; i < n; i++){ cin >> sor[i].first.second >> sor[i].first.first; sor[i].second = i + 1; } sor[n] = make_pair(make_pair(0, -1), 0); sor[n + 1] = make_pair(make_pair(1e9+2, 1e9+1), n + 1); n += 2; tabla.assign(n, vector<int>(log2(n + 1) + 1, -1)); sor2 = sor; sort(sor.begin(), sor.end()); int ind = 0; for (int i = 0; i < n; i++){ while (ind < i && sor[ind].first.first <= sor[i].first.second){ tabla[ind][0] = i; ind++; } // cout << i << " " << ind << endl; // cout << sor[i].first.first << " " << sor[i].first.second << " " << sor[i].second << endl; } for (int i = 1; i < tabla[0].size(); i++){ for (int j = 0; j < n; j++){ if (tabla[j][i - 1] == -1) continue; tabla[j][i] = tabla[tabla[j][i - 1]][i - 1]; } } // for (int i = 0; i < tabla[0].size(); i++){ // for (int j = 0; j < n; j++){ // cout << tabla[j][i] << " "; // } // cout << endl; // } ck.insert(make_pair(make_pair(0, -1), 0)); ck.insert(make_pair(make_pair(1e9+2, 1e9+1), n + 1)); int db = maxDb(0, 1e9); if (db < m){ cout << -1 << endl; return 0; } // cout << db << endl; for (int i = 0; i < n - 2; i++){ // if (ck.size() == m + 2) break; auto pos = ck.upper_bound(make_pair(make_pair(sor2[i].first.first, -2), -1)); if (pos -> first.second < sor2[i].first.first){ continue; } int r = pos -> first.second; pos--; if (pos -> first.first > sor2[i].first.second){ continue; } int l = pos -> first.first; // cout << i << ": " << l << " " << r << endl; // cout << maxDb(l, r) << " " << maxDb(l, sor[i].first.second) << " " << maxDb(sor[i].first.first, r) << endl; if (db - maxDb(l, r) + maxDb(l, sor2[i].first.second) + maxDb(sor2[i].first.first, r) + 1 >= m){ db = db - maxDb(l, r) + maxDb(l, sor2[i].first.second) + maxDb(sor2[i].first.first, r) + 1; ck.insert(sor2[i]); } } vector<int> mo; for (auto x : ck){ mo.push_back(x.second); } sort(mo.begin(), mo.end()); for (int i = 1; i <= m; i++){ cout << mo[i] << '\n'; } return 0; } /* 5 4 1 3 2 5 8 9 6 8 10 15 */

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:55:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (int i = 1; i < tabla[0].size(); 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...