Submission #1244765

#TimeUsernameProblemLanguageResultExecution timeMemory
1244765Boas모임들 (IOI18_meetings)C++20
0 / 100
22 ms2244 KiB
#include "meetings.h" #include <bits/stdc++.h> using namespace std; #define int long long #define pb push_back #define sz(x) (int)x.size() #define ALL(x) begin(x), end(x) #define loop(n, i) for (int i = 0; i < n; i++) #define rev(n, i) for (int i = n - 1; i >= 0; i--) typedef signed i32; typedef long long i64; typedef vector<int> vi; typedef pair<int, int> ii; typedef vector<i32> vi32; typedef vector<vi32> vvi32; typedef vector<vi> vvi; typedef vector<ii> vii; typedef vector<vii> vvii; struct node { int cnt = 0, cntl = 0, cntr = 0, sz = 0; node operator+(node b) { int cntl2 = cntl, cntr2 = b.cntr; if (cntl == sz) cntl2 += b.cntl; if (b.cntr == sz) cntr2 += cntr; return {max({cnt, b.cnt, cntr + b.cntl}), cntl2, cntr2, sz + b.sz}; }; void operator+=(node b) { *this = *this + b; } }; vector<node> s; node query(int i, int l, int r, int ql, int qr) { if (qr < l || r < ql) return {}; if (ql <= l && r <= qr) return s[i]; int m = (l + r) / 2; return query(2 * i, l, m, ql, qr) + query(2 * i + 1, m + 1, r, ql, qr); } vi minimum_costs(vi32 H, vi32 L, vi32 R) { int Q = sz(L); vi C(Q); int N = sz(H); int treeN = 1; while (treeN < N) treeN *= 2; s.assign(2 * treeN, {}); loop(N, i) { s[i + treeN].sz = 1; if (H[i] == 1) s[i + treeN] = {1, 1, 1, 1}; } rev(treeN, i) { s[i] = s[2 * i] + s[2 * i + 1]; } for (int j = 0; j < Q; ++j) { int l = L[j]; int r = R[j]; int res = 2 * (r - l + 1) - query(1, 0, treeN - 1, l, r).cnt; C[j] = res; } 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...