제출 #601813

#제출 시각아이디문제언어결과실행 시간메모리
601813Mazaalai모임들 (IOI18_meetings)C++17
0 / 100
34 ms2064 KiB
#include "meetings.h" #include <bits/stdc++.h> #define sz(x) (int)x.size() #define ALL(x) x.begin(), x.end() #define chmax(a, b) a=max(a,b) #define chmin(a, b) a=min(a,b) #define pb push_back #define ff first #define ss second using namespace std; using ll = long long; using VI = vector <int>; using PII = pair <int, int>; int n, m, q; const int N = 1e5+1; const int M = 3*N; int nums[N]; struct Node { int l, r, mx; bool full; } node[M]; Node merge(Node a, Node b) { Node res = { (a.full ? a.mx + b.l : a.l), (b.full ? b.mx + a.r : b.r), max(a.mx, b.mx), a.full&&b.full }; res.mx = max({res.mx, res.l, res.r, a.r+b.l}); return res; } void build(int l, int r, int head) { if (l == r) { int x = (nums[l] == 1); node[head] = {x, x, x, (bool)x}; // cout << l << ' ' << r << ": " << node[head].l << ' ' << node[head].r << ' ' << node[head].mx << ' ' << node[head].full << '\n'; return; } int mid = (l+r)>>1; build(l, mid, head*2+1); build(mid+1, r, head*2+2); node[head] = merge(node[head*2+1], node[head*2+2]); // cout << l << ' ' << r << ": " << node[head].l << ' ' << node[head].r << ' ' << node[head].mx << ' ' << node[head].full << '\n'; } Node query(int l, int r, int L, int R, int head) { if (l > R || L > r) return {0, 0, 1, 0}; if (L <= l && r <= R) return node[head]; int mid = (l+r)>>1; return merge( query(l, mid, L, R, head*2+1), query(mid+1, r, L, R, head*2+2) ); } vector<long long> minimum_costs(vector<int> h, vector<int> L, vector<int> R) { n = sz(h); q = sz(L); vector<long long> ans(q, 1e18); for (int i = 0; i < n; i++) nums[i] = h[i]; build(0, n-1, 0); for (int i = 0; i < q; i++) { int len = R[i] - L[i] + 1; ans[i] = len * 2 - query(0, n-1, L[i], R[i], 0).mx; } return ans; }
#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...