제출 #1244875

#제출 시각아이디문제언어결과실행 시간메모리
1244875joenpoenmanaltMeetings (IOI18_meetings)C++20
0 / 100
3139 ms30152 KiB
#include "meetings.h" // #include "grader.cpp" #include <bits/stdc++.h> using namespace std; typedef int ll; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<vi> vvi; #define ALL(x) begin(x), end(x) int np2(int n) { int N = 1; while (N < n) N *= 2; return N; } const ll maxh = 20; struct Node { ll mx = -1e18; ll very_best = 1e18; ll best[maxh][maxh]{}; ll lstart[maxh]{}; ll rstart[maxh]{}; Node() { for (int h = 0; h < maxh; h++) { this->lstart[h] = 0; this->rstart[h] = 0; for (int h2 = 0; h2 < maxh; h2++) { this->best[h][h2] = 1e18; } } } Node(int x) { this->mx = x; this->very_best = x; for (int h = 0; h < maxh; h++) { this->lstart[h] = max(h, x); this->rstart[h] = max(h, x); for (int h2 = 0; h2 < maxh; h2++) { this->best[h][h2] = 1e18; } } this->best[x][x] = x; } }; Node merge(Node a, Node b) { Node r{}; r.mx = max(a.mx, b.mx); for (int h = 0; h < maxh; h++) { for (int h2 = 0; h2 < maxh; h2++) { r.best[h][h2] = 1e18; } } for (ll h = 0; h < maxh; h++) { r.lstart[h] = a.lstart[h] + b.lstart[min(max(h, a.mx), maxh-1)]; r.rstart[h] = b.rstart[h] + a.rstart[min(max(h, b.mx), maxh-1)]; for (ll h2 = 0; h2 < maxh; h2++) { r.best[h][min(max(h2, b.mx), maxh-1)] = min(r.best[h][min(max(h2, b.mx), maxh-1)], a.best[h][h2] + b.lstart[h2]); r.best[min(max(h2, a.mx), maxh-1)][h] = min(r.best[min(max(h2, a.mx), maxh-1)][h], b.best[h2][h] + a.rstart[h2]); } } r.very_best = 1e18; for (int h = 0; h < maxh; h++) { for (int h2 = 0; h2 < maxh; h2++) { r.very_best = min(r.best[h][h2], r.very_best); } } return r; } vector<Node> tree; Node query(int l, int r, int a, int b, int k) { if (a > r || b < l) return {}; if (a >= l && b <= r) return tree[k]; int m = (a+b)/2; return merge(query(l, r, a, m, 2*k), query(l, r, m+1, b, 2*k+1)); } std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) { for (int& x : H) x--; int n = H.size(); int Q = L.size(); std::vector<long long> C(Q); int N = np2(n); tree.assign(2*N, {}); for (int i = 0; i < n; i++) tree[N+i] = Node(H[i]); for (int i = N-1; i > 0; i--) tree[i] = merge(tree[2*i], tree[2*i+1]); for (int i = 0; i < Q; i++) C[i] = query(L[i], R[i], 0, N-1, 1).very_best + R[i] - L[i]+1; return C; } /* 4 2 2 4 3 5 0 2 1 3 4 1 2 4 3 5 1 3 */

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

meetings.cpp:22:13: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '-1.0e+18' to '-2147483648' [-Woverflow]
   22 |     ll mx = -1e18;
      |             ^~~~~
meetings.cpp:23:20: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   23 |     ll very_best = 1e18;
      |                    ^~~~
meetings.cpp: In constructor 'Node::Node()':
meetings.cpp:33:37: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   33 |                 this->best[h][h2] = 1e18;
      |                                     ^~~~
meetings.cpp: In constructor 'Node::Node(int)':
meetings.cpp:45:37: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   45 |                 this->best[h][h2] = 1e18;
      |                                     ^~~~
meetings.cpp: In function 'Node merge(Node, Node)':
meetings.cpp:57:29: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   57 |             r.best[h][h2] = 1e18;
      |                             ^~~~
meetings.cpp:68:19: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   68 |     r.very_best = 1e18;
      |                   ^~~~
#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...