제출 #735590

#제출 시각아이디문제언어결과실행 시간메모리
735590cadmiumsky모임들 (IOI18_meetings)C++17
0 / 100
148 ms211020 KiB
#include "meetings.h" #include <bits/stdc++.h> using namespace std; using ll = long long; //#define int ll using pii = pair<int,int>; #define sz(x) ((int)(x).size()) const int nmax = 75e4 + 5; const int nbit = 20; const ll inf = 1e18 + 5; namespace RMQ { vector<int> costs; int rmq[nbit][nmax]; int lg2[nmax]; void init(vector<int> H) { costs = move(H); int n = sz(costs); for(int i = 2; i <= n; i++) lg2[i] = lg2[i >> 1] + 1; for(int i = 0; i < n; i++) rmq[0][i] = i; for(int step = 1; step < nbit; step++) for(int i = 0; i + (1 << step) <= n; i++) rmq[step][i] = (costs[rmq[step - 1][i]] <= costs[rmq[step - 1][i + (1 << step - 1)]]? rmq[step - 1][i + (1 << step - 1)] : rmq[step - 1][i]); } int query(int l, int r) { int step = lg2[r - l + 1]; return costs[rmq[step][l]] <= costs[rmq[step][r - (1 << step) + 1]]? rmq[step][r - (1 << step) + 1] : rmq[step][l]; } }; pii qs[nmax]; ll rez[nmax]; struct line { ll m, b; line(ll x = 0, ll y = inf): m(x), b(y) {;} ll operator()(const ll& x) const { return m * x + b; } line operator + (const line& x) const { return line(x.m + m, x.b + b); } line operator += (const line& x) { return *this = *this + x; } }; int N; struct LiChao { line aint[nmax * 4]; line lazy[nmax * 4]; void pushlazy(int node) { aint[2 * node] += lazy[node]; aint[2 * node + 1] += lazy[node]; lazy[2 * node + 1] += lazy[node]; lazy[2 * node] += lazy[node]; lazy[node] = line(0, 0); } void forcepush(line x, int node, int cl, int cr) { int mid = cl + cr >> 1; if(x(mid) < aint[node](mid)) swap(x, aint[node]); if(cl == cr) return; pushlazy(node); if(x(cl) <= aint[node](cl)) forcepush(x, 2 * node, cl, mid); else forcepush(x, 2 * node + 1, mid + 1, cr); return; } void pushline(int node, int cl, int cr) { int mid = cl + cr >> 1; forcepush(aint[node], 2 * node, cl, mid); forcepush(aint[node], 2 * node + 1, mid + 1, cr); aint[node] = line(); } void maxline(int l, int r, line x, int node, int cl, int cr) { if(r < cl || cr < l) return; if(l <= cl && cr <= r) { forcepush(x, node, cl, cr); return; } pushlazy(node); int mid = cl + cr >> 1; maxline(l, r, x, 2 * node, cl, mid); maxline(l, r, x, 2 * node + 1, mid + 1, cr); } void addline(int l, int r, line x, int node, int cl, int cr) { if(r < cl || cr < l) return; if(l <= cl && cr <= r) { aint[node] += x; lazy[node] += x; return; } pushlazy(node); pushline(node, cl, cr); int mid = cl + cr >> 1; addline(l, r, x, 2 * node, cl, mid); addline(l, r, x, 2 * node + 1, mid + 1, cr); } ll query(int p, int node, int cl, int cr) { if(cr < p || p < cl) return inf; if(cl == cr) {return aint[node](p); } int mid = cl + cr >> 1; pushlazy(node); //cerr << p << ' ' << cl << ' ' << cr << '\t' << aint[node].m << ' ' << aint[node].b << '\t' << aint[node](p) << '\n'; return min({aint[node](p), query(p, 2 * node, cl, mid), query(p, 2 * node + 1, mid + 1, cr)}); } ll query(int p) { return query(p, 1, 0, N - 1); } void addline(int l, int r, line x) { addline(l, r, x, 1, 0, N - 1); } void maxline(int l, int r, line x) { maxline(l, r, x, 1, 0, N - 1); } }; namespace CartTree { int Ls[nmax], Rs[nmax]; int L[nmax], R[nmax]; int val[nmax]; vector<int> atrqs[nmax]; int root; LiChao toleft, toright; void init(vector<int> H) { vector<int> st; for(int i = 0; i < sz(H); i++) { val[i] = H[i]; int last = -1; while(!st.empty() && H[st.back()] <= H[i]) R[st.back()] = i - 1, last = st.back(), st.pop_back(); L[i] = (st.empty()? 0 : st.back() + 1); Ls[i] = last; Rs[i] = -1; if(!st.empty()) Rs[st.back()] = i; else root = i; st.emplace_back(i); } for(auto x : st) R[x] = sz(H) - 1; } void push(int idx, int l, int r) { int mid = RMQ::query(l, r); atrqs[mid].emplace_back(idx); } void start(int node) { if(node == -1) return; start(Ls[node]); start(Rs[node]); for(auto idx : atrqs[node]) { auto [l, r] = qs[idx]; ll lv = (l == node? 0 : toright.query(l)); ll rv = (r == node? 0 : toright.query(l)); //cerr << idx << ' ' << l << ' ' << r << '\t' << lv << ' ' << rv << '\t'; lv += val[node] * (r - node + 1); rv += val[node] * (node - l + 1); //cerr << lv << ' ' << rv << '\n'; rez[idx] = min(lv, rv); } auto [l, r] = pii{L[node], R[node]}; toleft.addline(node, r, line{0, (node - l + 1) * val[node]}); toleft.maxline(node, r, line(val[node], (l == node? 0 : toleft.query(node - 1)) + -(node - 1) * val[node])); toright.addline(l, node, line{0, (r - node + 1) * val[node]}); toright.maxline(l, node, line(-val[node], (r == node? 0 : toright.query(node + 1)) + (node + 1) * val[node])); if(l == r) toright.maxline(node, node, line(0, val[node])), toleft.maxline(node, node, line(0, val[node])); //cerr << l << ' ' << node << ' ' << r << '\n'; //for(int i = l; i <= r; i++) cerr << toleft.query(i) << ' '; cerr << '\n'; //for(int i = l; i <= r; i++) cerr << toright.query(i) << ' '; cerr << '\n'; //cerr << "-----\n"; return; } } std::vector<long long> minimum_costs(std::vector<signed> H, std::vector<signed> L, std::vector<signed> R) { N = sz(H); CartTree::init(H); RMQ::init(H); for(int i = 0; i < sz(L); i++) { qs[i] = pii{L[i], R[i]}; CartTree::push(i, L[i], R[i]); } CartTree::start(CartTree::root); vector<ll> r; r.reserve(sz(L)); for(int i = 0; i < sz(L); i++) r.emplace_back(rez[i]); return r; }

컴파일 시 표준 에러 (stderr) 메시지

meetings.cpp: In function 'void RMQ::init(std::vector<int>)':
meetings.cpp:28:87: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   28 |         rmq[step][i] = (costs[rmq[step - 1][i]] <= costs[rmq[step - 1][i + (1 << step - 1)]]? rmq[step - 1][i + (1 << step - 1)] : rmq[step - 1][i]);
      |                                                                                  ~~~~~^~~
meetings.cpp:28:124: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   28 |         rmq[step][i] = (costs[rmq[step - 1][i]] <= costs[rmq[step - 1][i + (1 << step - 1)]]? rmq[step - 1][i + (1 << step - 1)] : rmq[step - 1][i]);
      |                                                                                                                       ~~~~~^~~
meetings.cpp: In member function 'void LiChao::forcepush(line, int, int, int)':
meetings.cpp:63:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
meetings.cpp: In member function 'void LiChao::pushline(int, int, int)':
meetings.cpp:75:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
meetings.cpp: In member function 'void LiChao::maxline(int, int, line, int, int, int)':
meetings.cpp:85:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
meetings.cpp: In member function 'void LiChao::addline(int, int, line, int, int, int)':
meetings.cpp:98:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
meetings.cpp: In member function 'll LiChao::query(int, int, int, int)':
meetings.cpp:105:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  105 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
#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...