Submission #417225

#TimeUsernameProblemLanguageResultExecution timeMemory
417225maomao90Event Hopping 2 (JOI21_event2)C++17
0 / 100
67 ms17212 KiB
#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; map<int, int> mp; vi adj[MAXN]; vi ans; int d[MAXN], p[MAXN];; void dfs(int u) { for (int v : adj[u]) { d[v] = d[u] + 1; p[v] = u; dfs(v); } } int main() { scanf("%d%d", &n, &k); REP (i, 0, n) { scanf("%d%d", &lr[i].FI, &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); } } mp[INF] = events.size(); REP (i, 0, events.size()) { int r = lr[events[i]].SE; int nxt = mp.lower_bound(r) -> SE; adj[nxt].pb(i); } dfs(events.size()); int i = mp.begin() -> SE; while (1) { if (k == 0) break; int l = lr[events[i]].FI; for (; i >= 0 && lr[events[i]].FI == l; i--) { if (d[i] < k) { i++; if (lr[events[i]].FI != l) { printf("-1\n"); return 0; } ans.pb(events[i]); i = p[i]; break; } } if (i < 0 || lr[events[i]].FI <= l) { i++; ans.pb(events[i]); i = p[i]; } k--; } //assert(ans.size() == k); for (int i : ans) { printf("%d\n", i + 1); } //REP (i, 0, events.size() + 1) { //printf("%d:", i); //for (int v : adj[i]) { //printf(" %d", v); //} //printf("\n"); //} } /* 4 2 1 4 3 5 4 9 7 10 8 3 1 4 1 3 1 2 3 8 3 5 6 11 6 10 6 7 */

Compilation message (stderr)

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++)
......
   59 |  REP (i, 0, events.size()) {
      |       ~~~~~~~~~~~~~~~~~~~               
event2.cpp:59:2: note: in expansion of macro 'REP'
   59 |  REP (i, 0, events.size()) {
      |  ^~~
event2.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
event2.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |   scanf("%d%d", &lr[i].FI, &lr[i].SE);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...