제출 #493410

#제출 시각아이디문제언어결과실행 시간메모리
493410Jarif_RahmanEvent Hopping 2 (JOI21_event2)C++17
32 / 100
3074 ms6168 KiB
#include <bits/stdc++.h> #define pb push_back #define f first #define sc second using namespace std; typedef long long int ll; typedef string str; const int inf = 1e9+7; int n, k; vector<pair<int, int>> events; vector<int> succ; int dfs(int nd, int lim){ if(nd == -1) return 0; if(events[nd].sc > lim) return 0; return dfs(succ[nd], lim)+1; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> k; events.resize(n); succ.resize(n, -1); for(auto &p: events) cin >> p.f >> p.sc; vector<pair<int, int>> sth; for(int i = 0; i < n; i++){ sth.pb({events[i].f, i+1}); sth.pb({events[i].sc, -i-1}); } sort(sth.begin(), sth.end()); int mn = inf, cur = -1, start = -1, start_end = inf; for(int i = (int)sth.size()-1; i >= 0; i--){ int in = sth[i].sc; if(in < 0){ in*=-1; in--; if(events[in].sc == start_end) start = min(start, in); else if(events[in].sc < start_end) start_end = events[in].sc, start = in; succ[in] = cur; } else{ in--; if(events[in].sc == mn) cur = min(cur, in); else if(events[in].sc < mn) mn = events[in].sc, cur = in; } } int sum = dfs(start, inf); set<array<int, 4>> ss; ss.insert({inf, 0, start, sum}); vector<int> ans; int kk = k; for(int i = 0; i < n; i++){ if(kk == 0) break; auto it = ss.lower_bound({events[i].sc, 0, 0, 0}); if(it == ss.end() || (*it)[1] > events[i].f) continue; auto [r, l, st, cnt] = *it; int a = dfs(st, events[i].f); int b = dfs(succ[i], r); if(a+b+sum-cnt+1 < kk) continue; ans.pb(i); sum-=cnt; sum+=a+b; ss.erase(it); ss.insert({events[i].f, l, st, a}); ss.insert({r, events[i].sc, succ[i], b}); kk--; } if(ans.size() != k) cout << "-1\n", exit(0); for(int x: ans) cout << x+1 << "\n"; }

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

event2.cpp: In function 'int main()':
event2.cpp:76:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   76 |     if(ans.size() != k) cout << "-1\n", exit(0);
      |        ~~~~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...