Submission #944960

#TimeUsernameProblemLanguageResultExecution timeMemory
944960hmm789Meetings (IOI18_meetings)C++14
19 / 100
3190 ms401416 KiB
#include "meetings.h" #include <bits/stdc++.h> using namespace std; #define INF 1000000000000000000 #define int long long int fw[5000][5005]; void update(int i, int x, int v) { for(x++; x < 5005; x += x&-x) fw[i][x] += v; } int query(int i, int x) { int ans = 0; for(x++; x; x -= x&-x) ans += fw[i][x]; return ans; } int query(int i, int x, int y) { return query(i, y) - query(i, x-1); } struct node2 { int s, e, m, v; node2 *l, *r; node2(int _s, int _e) { s = _s, e = _e, m = (s+e)/2, v = 0; if(s != e) { l = new node2(s, m); r = new node2(m+1, e); } } void update(int x, int val) { if(s == e) {v = val; return;} else if(x > m) r->update(x, val); else l->update(x, val); v = max(l->v, r->v); } int rmax(int x, int y) { if(x <= s && e <= y) return v; else if(x > m) return r->rmax(x, y); else if(y <= m) return l->rmax(x, y); else return max(l->rmax(x, y), r->rmax(x, y)); } } *root2; #undef int std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) { #define int long long int n = H.size(), q = L.size(); root2 = new node2(0, n-1); for(int i = 0; i < n; i++) root2->update(i, H[i]); for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) update(i, j, root2->rmax(min(i,j), max(i,j))); } vector<int> ans(q); for(int i = 0; i < q; i++) { int tmp = INF; for(int j = L[i]; j <= R[i]; j++) tmp = min(tmp, query(j, L[i], R[i])); ans[i] = tmp; } return ans; #undef int }
#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...