제출 #139269

#제출 시각아이디문제언어결과실행 시간메모리
139269fredbr모임들 (IOI18_meetings)C++17
0 / 100
35 ms2184 KiB
#include "meetings.h" #include <bits/stdc++.h> using namespace std; using ll = long long; struct Seg { struct Node { int l, r, tot; static Node join(Node const& a, Node const& b) { return Node{a.l, b.r, max({a.tot, b.tot, a.r+b.l})}; } }; vector<Node> tree; vector<int> const& v; Seg(vector<int> const& v) : tree(v.size()*4), v(v) { build(0, 0, v.size()); } void build(int no, int l, int r) { if (l == r) { if (v[l] == 1) tree[no] = Node{1, 1, 1}; else tree[no] = Node{0, 0, 0}; } else { int m = (l+r)/2; build(no*2+1, l, m); build(no*2+2, m+1, r); tree[no] = Node::join(tree[no*2+1], tree[no*2+2]); } } Node get(int no, int l, int r, int a, int b) { if (a <= l and r <= b) return tree[no]; else { int m = (l+r)/2; if (b <= m) return get(no*2+1, l, m, a, b); if (a > m) return get(no*2+2, m+1, r, a, b); return Node::join(get(no*2+1, l, m, a, b), get(no*2+2, m+1, r, a, b)); } } }; vector<ll> minimum_costs(vector<int> h, vector<int> L, vector<int> R) { int n = h.size(); Seg sg(h); int q = L.size(); vector<ll> res; for (int at = 0; at < q; at++) { int l = L[at], r = R[at]; Seg::Node ans = sg.get(0, 0, n-1, l, r); res.push_back(2ll*(r-l+1) - ans.tot); } return res; }
#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...