제출 #446866

#제출 시각아이디문제언어결과실행 시간메모리
446866ivan_tudorEvent Hopping 2 (JOI21_event2)C++14
0 / 100
207 ms25460 KiB
#include<bits/stdc++.h> using namespace std; const int N = 100005; struct Intervale{ int l, r; bool operator < (Intervale oth) const{ return r < oth.r; } }; struct Nodes{ int h; int id; Nodes *jump; Nodes *par; }; Nodes *poz[2 * N]; void add_leaf(int dad, int son){ poz[son] = new Nodes; poz[son] ->id = son; poz[son]->h = poz[dad]->h + 1; poz[son]->par = poz[dad]; if(poz[dad]->h - poz[dad]->jump->h == poz[dad]->jump->h - poz[dad]->jump->jump->h) poz[son]->jump = poz[dad]->jump->jump; else poz[son]->jump = poz[dad]; } int longest_subseq(int l, int r){ Nodes *nod = poz[r]; int ans = 0; while(nod->id >= l && nod->par != NULL){ if(nod->jump->id >= l){ ans += nod->h - nod->jump->h; nod = nod->jump; } else{ nod = nod->par; ans ++; } } if(nod ->id < l) ans--; return ans; } Intervale itv[N]; int main() { //freopen(".in","r",stdin); ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int n, k; cin>>n>>k; map<int, int> normal; for(int i = 1; i<=n; i++){ cin>>itv[i].l>>itv[i].r; normal[itv[i].l] = 1; normal[itv[i].r] = 1; } int val = 0; for(auto &x:normal) x.second = ++val; for(int i = 1; i <=n; i++){ itv[i].l = normal[itv[i].l]; itv[i].r = normal[itv[i].r]; } sort(itv + 1, itv + n + 1); int lpoz = -1; int j = 1; for(int i = 1; i <= val; i++){ while(j <=n && itv[j].r == i){ lpoz = max(lpoz, itv[j].l); j++; } if(lpoz != -1){ add_leaf(lpoz, i); } else{ poz[i] = new Nodes; poz[i]->h = 0; poz[i]->id = i; poz[i]->par = NULL; poz[i]->jump = poz[i]; } } set<Intervale> free; free.insert({1, val}); vector<int> ans; int cur = longest_subseq(1, val); for(int i = 1 ; i <= n; i++){ if(ans.size() == k) break; auto itr = free.lower_bound(itv[i]); if(itr == free.end()) continue; Intervale found = (*itr); if(found.l <= itv[i].l && itv[i].r <= found.r){ int newcur = cur - longest_subseq(found.l, found.r); Intervale st = {found.l, itv[i].l}; if(st.l < st.r) newcur += longest_subseq(st.l, st.r); Intervale dr = {itv[i].r, found.r}; if(dr.l < dr.r) newcur += longest_subseq(dr.l, dr.r); newcur++; if(newcur >= k){ ans.push_back(i); free.erase(found); if(st.l < st.r) free.insert(st); if(dr.l < dr.r) free.insert(dr); cur = newcur; } } } if(ans.size() < k){ cout<<-1; return 0 ; } for(auto x:ans) cout<<x<<"\n"; return 0; }

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

event2.cpp: In function 'int main()':
event2.cpp:89:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |     if(ans.size() == k)
      |        ~~~~~~~~~~~^~~~
event2.cpp:115:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  115 |   if(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...