제출 #386762

#제출 시각아이디문제언어결과실행 시간메모리
386762BartolMEvent Hopping 2 (JOI21_event2)C++17
1 / 100
125 ms17376 KiB
#define DEBUG 0 #include <bits/stdc++.h> using namespace std; #define X first #define Y second #define mp make_pair #define pb push_back typedef long long ll; typedef pair <int, int> pii; typedef pair <int, pii> pip; typedef pair <pii, int> ppi; typedef pair <ll, ll> pll; const int INF=0x3f3f3f3f; const int N=1e5+5; const int LOG=18; int n, m, k; ppi p[N]; pii poc[N]; vector <pii> v; int nx[LOG][N]; vector <int> res; set <pii> S; vector <int> sol; void build() { for (int i=1; i<LOG; ++i) { for (int j=0; j<=m; ++j) { nx[i][j]=nx[i-1][nx[i-1][j]]; } } } int calc(pii pp, int gr) { if (pp.Y>gr) return -INF; int x=lower_bound(v.begin(), v.end(), mp(pp.Y, -1))-v.begin(); if (v[x].Y>gr) return 1; int ret=2; for (int i=LOG-1; i>=0; --i) { if (v[nx[i][x]].Y<=gr) { ret+=(1<<i); x=nx[i][x]; } } return ret; } int cmp(ppi a, ppi b) { if (a.X.X==b.X.X) return a.X.Y>b.X.Y; return a.X.X<b.X.X; } void solve() { sort(p, p+n, cmp); int rig=INF; for (int i=n-1; i>=0; --i) { if (p[i].X.Y<rig) { rig=p[i].X.Y; v.pb(p[i].X); } } reverse(v.begin(), v.end()); #if DEBUG printf("----------------\n"); for (pii pp:v) printf("%d %d\n", pp.X, pp.Y); #endif // DEBUG m=v.size(); v.pb(mp(INF, INF+1)); nx[0][m]=m; for (int i=0; i<m; ++i) nx[0][i]=lower_bound(v.begin(), v.end(), mp(v[i].Y, -1))-v.begin(); build(); S.insert(mp(-2, -1)); S.insert(mp(INF, INF+1)); int uk=calc(v[0], INF); if (uk<k) { printf("-1\n"); return; } for (int i=0; i<n; ++i) { if ((int)sol.size()>=k) break; pii pp=poc[i]; if (S.count(pp)) continue; auto it=S.insert(pp).X; auto pr=it, slj=it; pr--; slj++; int prije=calc((*pr), slj->X); int sad=calc((*pr), it->X)+calc(pp, slj->X); #if DEBUG printf("pp: (%d, %d), prije: %d, sad: %d\n", pp.X, pp.Y, prije, sad); #endif if (uk-prije+sad<k) S.erase(it); else sol.pb(i+1); } for (int x:sol) printf("%d\n", x); } void load() { scanf("%d %d", &n, &k); for (int i=0; i<n; ++i) { scanf("%d %d", &p[i].X.X, &p[i].X.Y); p[i].Y=i; poc[i]=p[i].X; } } int main() { load(); solve(); return 0; } /* 5 6 11 2 4 1 5 4 10 4 6 */

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

event2.cpp: In function 'void load()':
event2.cpp:108:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  108 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
event2.cpp:110:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  110 |         scanf("%d %d", &p[i].X.X, &p[i].X.Y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...