Submission #611958

#TimeUsernameProblemLanguageResultExecution timeMemory
611958JomnoiMeetings (IOI18_meetings)C++17
19 / 100
1522 ms20612 KiB
#include <bits/stdc++.h> #include "meetings.h" using namespace std; const int MAX_N = 75e4 + 5; const long long INF = 1e18 + 7; int N, Q; long long H[MAX_N]; pair <int, int> table[MAX_N][20]; int table2[MAX_N][20]; vector <int> graph[MAX_N]; pair <int, int> getMax(int l, int r) { int j = log2(r - l + 1); return max(table[l][j], table[r - (1<<j) + 1][j]); } int getMin(int l, int r) { int j = log2(r - l + 1); return min(table2[l][j], table2[r - (1<<j) + 1][j]); } int build_tree(int l, int r) { if(l > r) { return -1; } int u = getMax(l, r).second; int L = build_tree(l, u - 1); int R = build_tree(u + 1, r); if(L != -1) { graph[u].push_back(L); } if(R != -1) { graph[u].push_back(R); } return u; } long long dfs(int u, int l, int r, long long total = 0) { long long now = total + H[u] * (r - l + 1); for(auto v : graph[u]) { if(v < u) { now = min(now, dfs(v, l, u - 1, total + H[u] * (r - u + 1))); } else { now = min(now, dfs(v, u + 1, r, total + H[u] * (u - l + 1))); } } return now; } vector <long long> minimum_costs(vector <int> h, vector <int> L, vector <int> R) { N = h.size(), Q = L.size(); vector <long long> C; for(int i = 1; i <= N; i++) { H[i] = h[i - 1]; } for(int i = 0; i < Q; i++) { L[i]++, R[i]++; } if(N <= 5000 and Q <= 5000) { for(int i = 1; i <= N; i++) { table[i][0] = make_pair(H[i], i); } for(int j = 1; j < 20; j++) { for(int i = 1; i + (1<<j) - 1 <= N; i++) { table[i][j] = max(table[i][j - 1], table[i + (1<<(j - 1))][j - 1]); } } for(int i = 0; i < Q; i++) { for(int i = 1; i <= N; i++) { graph[i].clear(); } C.push_back(dfs(build_tree(L[i], R[i]), L[i], R[i])); } } else { for(int i = 1; i <= N; i++) { table2[i][0] = H[i]; } for(int j = 1; j < 20; j++) { for(int i = 1; i + (1<<j) - 1 <= N; i++) { table2[i][j] = min(table2[i][j - 1], table2[i + (1<<(j - 1))][j - 1]); } } for(int i = 0; i < Q; i++) { int l = L[i], r = R[i], pos1 = N + 2, pos2 = N + 1; while(l <= r) { int mid = (l + r) / 2; if(getMin(L[i], mid) == 1) { r = mid - 1; pos1 = mid; } else { l = mid + 1; } } l = pos1, r = R[i]; while(l <= r) { int mid = (l + r) / 2; if(getMin(mid, R[i]) == 1) { l = mid + 1; pos2 = mid; } else { r = mid - 1; } } C.push_back((pos2 - pos1 + 1) + 2 * ((R[i] - L[i] + 1) - (pos2 - pos1 + 1))); } } return C; }
#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...