제출 #1020904

#제출 시각아이디문제언어결과실행 시간메모리
1020904MohamedFaresNebili밀림 점프 (APIO21_jumps)C++14
0 / 100
7 ms26968 KiB
#include <bits/stdc++.h> using namespace std; int N; int P[200005]; int MX[800005]; vector<int> ST[800005]; vector<int> adj[200005]; int UP[200005][20], DN[200005][20]; vector<int> H; void build(int v, int l, int r) { if(l == r) { ST[v].push_back(P[l]); return; } build(v * 2, l, (l + r) / 2); build(v * 2 + 1, (l + r) / 2 + 1, r); int i = 0, j = 0; while(i < ST[v * 2].size() || j < ST[v * 2 + 1].size()) { if(i == ST[v * 2].size()) ST[v].push_back(ST[v * 2 + 1][j++]); else if(j == ST[v * 2 + 1].size()) ST[v].push_back(ST[v * 2][i++]); else { if(ST[v * 2][i] < ST[v * 2 + 1][j]) ST[v].push_back(ST[v * 2][i++]); else ST[v].push_back(ST[v * 2 + 1][j++]); } } } void buildM(int v, int l, int r) { if(l == r) { MX[v] = H[l]; return; } buildM(v * 2, l, (l + r) / 2); buildM(v * 2 + 1, (l + r) / 2 + 1, r); MX[v] = max(MX[v * 2], MX[v * 2 + 1]); } int query(int v, int l, int r, int lo, int hi) { if(l > hi || r < lo) return 0; if(l >= lo && r <= hi) return MX[v]; return max(query(v * 2, l, (l + r) / 2, lo, hi), query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi)); } int queryR(int v, int l, int r, int lo, int hi, int K) { if(l > hi || r < lo) return 1e9 + 7; if(l >= lo && r <= hi) { int R = lower_bound(ST[v].begin(), ST[v].end(), K) - ST[v].begin(); if(R == ST[v].size()) return 1e9 + 7; return ST[v][R]; } return min(queryR(v * 2, l, (l + r) / 2, lo, hi, K), queryR(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, K)); } int queryL(int v, int l, int r, int lo, int hi, int K) { if(l > hi || r < lo) return -1; if(l >= lo && r <= hi) { int L = lower_bound(ST[v].begin(), ST[v].end(), K) - ST[v].begin(); if(L == 0) return -1; return ST[v][--L]; } return max(queryL(v * 2, l, (l + r) / 2, lo, hi, K), queryL(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, K)); } void init(int _N, vector<int> _H) { N = _N; for(int l = 0; l < _N; l++) { H.push_back(_H[l]); P[_H[l]] = l; } for(int l = 0; l < 20; l++) UP[N + 1][l] = DN[N + 1][l] = N + 1; build(1, 1, N); buildM(1, 0, N - 1); for(int l = 0; l < _N; l++) { int i = queryL(1, 1, N, _H[l] + 1, N, l); int j = queryR(1, 1, N, _H[l] + 1, N, l); UP[_H[l]][0] = (i != -1 ? _H[i] : N + 1); DN[_H[l]][0] = (j != 1e9 + 7 ? _H[j] : N + 1); if(UP[_H[l]][0] < DN[_H[l]][0]) swap(UP[_H[l]][0], DN[_H[l]][0]); } for(int l = 1; l < 20; l++) for(int i = 0; i < _N; i++) { UP[H[i]][l] = UP[UP[H[i]][l - 1]][l - 1]; DN[H[i]][l] = DN[DN[H[i]][l - 1]][l - 1]; } } int solve(int U, int V) { if(U > V) return N + 1; int best = 0; for(int l = 19; l >= 0 && U < V; l--) if(UP[U][l] <= V) best += (1 << l), U = UP[U][l]; if(U == V) return best; for(int l = 19; l >= 0 && U < V; l--) if(DN[U][l] <= V) best += (1 << l), U = DN[U][l]; if(U == V) return best; return -1; } int minimum_jumps(int A, int B, int C, int D) { int lo = A, hi = B, ans = -1; while(lo <= hi) { int md = (lo + hi) / 2; int q = query(1, 0, N - 1, md, B); if(q < C) ans = md, hi = md - 1; else lo = md + 1; } if(ans == -1) return -1; int U = query(1, 0, N - 1, ans, B), V = H[C]; int res = solve(U, V); return (res > N ? -1 : res); }

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

jumps.cpp: In function 'void build(int, int, int)':
jumps.cpp:22:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |                 while(i < ST[v * 2].size() || j < ST[v * 2 + 1].size()) {
      |                       ~~^~~~~~~~~~~~~~~~~~
jumps.cpp:22:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |                 while(i < ST[v * 2].size() || j < ST[v * 2 + 1].size()) {
      |                                               ~~^~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:23:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |                     if(i == ST[v * 2].size())
      |                        ~~^~~~~~~~~~~~~~~~~~~
jumps.cpp:25:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |                     else if(j == ST[v * 2 + 1].size())
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp: In function 'int queryR(int, int, int, int, int, int)':
jumps.cpp:55:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |                     if(R == ST[v].size()) return 1e9 + 7;
      |                        ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...