제출 #952930

#제출 시각아이디문제언어결과실행 시간메모리
952930SirCovidThe19thThe short shank; Redemption (BOI21_prison)C++17
80 / 100
2077 ms104772 KiB
/* * ___ * _ / _\_ * / | |___| * | | | * \_| __ | * \_/ \_/ * uwu amogus */ #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") /** * date : 2020-11-26 16:01:43 */ #pragma region kyopro_template #define Nyaan_template #include <immintrin.h> #include <bits/stdc++.h> #define pb push_back #define eb emplace_back #define fi first #define se second #define each(x, v) for (auto &x : v) #define all(v) (v).begin(), (v).end() #define sz(v) ((int)(v).size()) #define mem(a, val) memset(a, val, sizeof(a)) #define ini(...) \ int __VA_ARGS__; \ in(__VA_ARGS__) #define inl(...) \ long long __VA_ARGS__; \ in(__VA_ARGS__) #define ins(...) \ string __VA_ARGS__; \ in(__VA_ARGS__) #define inc(...) \ char __VA_ARGS__; \ in(__VA_ARGS__) #define in2(s, t) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i]); \ } #define in3(s, t, u) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i]); \ } #define in4(s, t, u, v) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i], v[i]); \ } #define rep(i, N) for (long long i = 0; i < (long long)(N); i++) #define repr(i, N) for (long long i = (long long)(N)-1; i >= 0; i--) #define rep1(i, N) for (long long i = 1; i <= (long long)(N); i++) #define repr1(i, N) for (long long i = (N); (long long)(i) > 0; i--) #define reg(i, a, b) for (long long i = (a); i < (b); i++) #define die(...) \ do { \ out(__VA_ARGS__); \ return; \ } while (0) using namespace std; using ll = long long; template <class T> using V = vector<T>; using vi = vector<int>; using vl = vector<long long>; using vvi = vector<vector<int>>; using vd = V<double>; using vs = V<string>; using vvl = vector<vector<long long>>; using P = pair<long long, long long>; using vp = vector<P>; using pii = pair<int, int>; using vpi = vector<pair<int, int>>; constexpr int inf = 1001001001; constexpr long long infLL = (1LL << 61) - 1; template <typename T, typename U> inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; } template <typename T, typename U> inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; } template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) { os << p.first << " " << p.second; return os; } template <typename T, typename U> istream &operator>>(istream &is, pair<T, U> &p) { is >> p.first >> p.second; return is; } template <typename T> ostream &operator<<(ostream &os, const vector<T> &v) { int s = (int)v.size(); for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i]; return os; } template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; } void in() {} template <typename T, class... U> void in(T &t, U &... u) { cin >> t; in(u...); } void out() { cout << "\n"; } template <typename T, class... U> void out(const T &t, const U &... u) { cout << t; if (sizeof...(u)) cout << " "; out(u...); } #ifdef NyaanDebug #define trc(...) \ do { \ cerr << #__VA_ARGS__ << " = "; \ dbg_out(__VA_ARGS__); \ } while (0) #define trca(v, N) \ do { \ cerr << #v << " = "; \ array_out(v, N); \ } while (0) #define trcc(v) \ do { \ cerr << #v << " = {"; \ each(x, v) { cerr << " " << x << ","; } \ cerr << "}" << endl; \ } while (0) template <typename T> void _cout(const T &c) { cerr << c; } void _cout(const int &c) { if (c == 1001001001) cerr << "inf"; else if (c == -1001001001) cerr << "-inf"; else cerr << c; } void _cout(const unsigned int &c) { if (c == 1001001001) cerr << "inf"; else cerr << c; } void _cout(const long long &c) { if (c == 1001001001 || c == (1LL << 61) - 1) cerr << "inf"; else if (c == -1001001001 || c == -((1LL << 61) - 1)) cerr << "-inf"; else cerr << c; } void _cout(const unsigned long long &c) { if (c == 1001001001 || c == (1LL << 61) - 1) cerr << "inf"; else cerr << c; } template <typename T, typename U> void _cout(const pair<T, U> &p) { cerr << "{ "; _cout(p.fi); cerr << ", "; _cout(p.se); cerr << " } "; } template <typename T> void _cout(const vector<T> &v) { int s = v.size(); cerr << "{ "; for (int i = 0; i < s; i++) { cerr << (i ? ", " : ""); _cout(v[i]); } cerr << " } "; } template <typename T> void _cout(const vector<vector<T>> &v) { cerr << "[ "; for (const auto &x : v) { cerr << endl; _cout(x); cerr << ", "; } cerr << endl << " ] "; } void dbg_out() { cerr << endl; } template <typename T, class... U> void dbg_out(const T &t, const U &... u) { _cout(t); if (sizeof...(u)) cerr << ", "; dbg_out(u...); } template <typename T> void array_out(const T &v, int s) { cerr << "{ "; for (int i = 0; i < s; i++) { cerr << (i ? ", " : ""); _cout(v[i]); } cerr << " } " << endl; } template <typename T> void array_out(const T &v, int H, int W) { cerr << "[ "; for (int i = 0; i < H; i++) { cerr << (i ? ", " : ""); array_out(v[i], W); } cerr << " ] " << endl; } #else #define trc(...) #define trca(...) #define trcc(...) #endif inline int popcnt(unsigned long long a) { return __builtin_popcountll(a); } inline int lsb(unsigned long long a) { return __builtin_ctzll(a); } inline int msb(unsigned long long a) { return 63 - __builtin_clzll(a); } template <typename T> inline int getbit(T a, int i) { return (a >> i) & 1; } template <typename T> inline void setbit(T &a, int i) { a |= (1LL << i); } template <typename T> inline void delbit(T &a, int i) { a &= ~(1LL << i); } template <typename T> int lb(const vector<T> &v, const T &a) { return lower_bound(begin(v), end(v), a) - begin(v); } template <typename T> int ub(const vector<T> &v, const T &a) { return upper_bound(begin(v), end(v), a) - begin(v); } template <typename T> int btw(T a, T x, T b) { return a <= x && x < b; } template <typename T, typename U> T ceil(T a, U b) { return (a + b - 1) / b; } constexpr long long TEN(int n) { long long ret = 1, x = 10; while (n) { if (n & 1) ret *= x; x *= x; n >>= 1; } return ret; } template <typename T> vector<T> mkrui(const vector<T> &v) { vector<T> ret(v.size() + 1); for (int i = 0; i < int(v.size()); i++) ret[i + 1] = ret[i] + v[i]; return ret; }; template <typename T> vector<T> mkuni(const vector<T> &v) { vector<T> ret(v); sort(ret.begin(), ret.end()); ret.erase(unique(ret.begin(), ret.end()), ret.end()); return ret; } template <typename F> vector<int> mkord(int N, F f) { vector<int> ord(N); iota(begin(ord), end(ord), 0); sort(begin(ord), end(ord), f); return ord; } template <typename T = int> vector<T> mkiota(int N) { vector<T> ret(N); iota(begin(ret), end(ret), 0); return ret; } template <typename T> vector<int> mkinv(vector<T> &v) { vector<int> inv(v.size()); for (int i = 0; i < (int)v.size(); i++) inv[v[i]] = i; return inv; } struct IoSetupNya { IoSetupNya() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(7); } } iosetupnya; #pragma endregion using namespace std; template <typename T> struct BinaryIndexedTree { int N; vector<T> data; BinaryIndexedTree() = default; BinaryIndexedTree(int size) { init(size); } void init(int size) { N = size + 2; data.assign(N + 1, 0); } // get sum of [0,k] T sum(int k) const { if (k < 0) return 0; // return 0 if k < 0 T ret = 0; for (++k; k > 0; k -= k & -k) ret += data[k]; return ret; } // getsum of [l,r] inline T sum(int l, int r) const { return sum(r) - sum(l - 1); } // get value of k inline T operator[](int k) const { return sum(k) - sum(k - 1); } // data[k] += x void add(int k, T x) { for (++k; k < N; k += k & -k) data[k] += x; } // range add x to [l,r] void imos(int l, int r, T x) { add(l, x); add(r + 1, -x); } // minimize i s.t. sum(i) >= w int lower_bound(T w) { if (w <= 0) return 0; int x = 0; for (int k = 1 << __lg(N); k; k >>= 1) { if (x + k <= N - 1 && data[x + k] < w) { w -= data[x + k]; x += k; } } return x; } // minimize i s.t. sum(i) > w int upper_bound(T w) { if (w < 0) return 0; int x = 0; for (int k = 1 << __lg(N); k; k >>= 1) { if (x + k <= N - 1 && data[x + k] <= w) { w -= data[x + k]; x += k; } } return x; } }; /** * @brief Binary Indexed Tree(Fenwick Tree) * @docs docs/data-structure/binary-indexed-tree.md */ using namespace std; namespace StaticGraphImpl { template <typename T, bool Cond = is_void<T>::value> struct E; template <typename T> struct E<T, false> { int to; T cost; E() {} E(const int& v, const T& c) : to(v), cost(c) {} operator int() const { return to; } }; template <typename T> struct E<T, true> { int to; E() {} E(const int& v) : to(v) {} operator int() const { return to; } }; template <typename T = void> struct StaticGraph { private: template <typename It> struct Es { It b, e; It begin() const { return b; } It end() const { return e; } int size() const { return int(e - b); } }; int N, M, ec; vector<int> head; vector<pair<int, E<T>>> buf; vector<E<T>> es; void build() { partial_sum(begin(head), end(head), begin(head)); es.resize(M); for (auto&& [u, e] : buf) es[--head[u]] = e; } public: StaticGraph(int _n, int _m) : N(_n), M(_m), ec(0), head(N + 1, 0) { buf.reserve(M); } template <typename... Args> void add_edge(int u, Args&&... args) { buf.emplace_back(u, E<T>{std::forward<Args>(args)...}); ++head[u]; if ((int)buf.size() == M) build(); } Es<typename vector<E<T>>::iterator> operator[](int u) { return {begin(es) + head[u], begin(es) + head[u + 1]}; } const Es<typename vector<E<T>>::const_iterator> operator[](int u) const { return {begin(es) + head[u], begin(es) + head[u + 1]}; } int size() const { return N; } }; } // namespace StaticGraphImpl using StaticGraphImpl::StaticGraph; /** * @brief Static Graph */ using namespace std; namespace fastio { static constexpr int SZ = 1 << 17; char ibuf[SZ], obuf[SZ]; int pil = 0, pir = 0, por = 0; struct Pre { char num[40000]; constexpr Pre() : num() { for (int i = 0; i < 10000; i++) { int n = i; for (int j = 3; j >= 0; j--) { num[i * 4 + j] = n % 10 + '0'; n /= 10; } } } } constexpr pre; inline void load() { memcpy(ibuf, ibuf + pil, pir - pil); pir = pir - pil + fread(ibuf + pir - pil, 1, SZ - pir + pil, stdin); pil = 0; } inline void flush() { fwrite(obuf, 1, por, stdout); por = 0; } inline void rd(char& c) { c = ibuf[pil++]; } template <typename T> inline void rd(T& x) { if (pil + 32 > pir) load(); char c; do c = ibuf[pil++]; while (c < '-'); bool minus = 0; if (c == '-') { minus = 1; c = ibuf[pil++]; } x = 0; while (c >= '0') { x = x * 10 + (c & 15); c = ibuf[pil++]; } if (minus) x = -x; } inline void rd() {} template <typename Head, typename... Tail> inline void rd(Head& head, Tail&... tail) { rd(head); rd(tail...); } inline void wt(char c) { obuf[por++] = c; } template <typename T> inline void wt(T x) { if (por > SZ - 32) flush(); if (!x) { obuf[por++] = '0'; return; } if (x < 0) { obuf[por++] = '-'; x = -x; } int i = 12; char buf[16]; while (x >= 10000) { memcpy(buf + i, pre.num + (x % 10000) * 4, 4); x /= 10000; i -= 4; } if (x < 100) { if (x < 10) { wt(char('0' + char(x))); } else { uint32_t q = (uint32_t(x) * 205) >> 11; uint32_t r = uint32_t(x) - q * 10; obuf[por + 0] = '0' + q; obuf[por + 1] = '0' + r; por += 2; } } else { if (x < 1000) { memcpy(obuf + por, pre.num + (x << 2) + 1, 3); por += 3; } else { memcpy(obuf + por, pre.num + (x << 2), 4); por += 4; } } memcpy(obuf + por, buf + i + 4, 12 - i); por += 12 - i; } inline void wt() {} template <typename Head, typename... Tail> inline void wt(Head head, Tail... tail) { wt(head); wt(tail...); } template <typename T> inline void wtn(T x) { wt(x, '\n'); } struct Dummy { Dummy() { atexit(flush); } } dummy; } // namespace fastio using fastio::rd; using fastio::wt; using fastio::wtn; using namespace std; using namespace std; template <typename T> struct edge { int src, to; T cost; edge(int _to, T _cost) : src(-1), to(_to), cost(_cost) {} edge(int _src, int _to, T _cost) : src(_src), to(_to), cost(_cost) {} edge &operator=(const int &x) { to = x; return *this; } operator int() const { return to; } }; template <typename T> using Edges = vector<edge<T>>; template <typename T> using WeightedGraph = vector<Edges<T>>; using UnweightedGraph = vector<vector<int>>; // Input of (Unweighted) Graph UnweightedGraph graph(int N, int M = -1, bool is_directed = false, bool is_1origin = true) { UnweightedGraph g(N); if (M == -1) M = N - 1; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; if (is_1origin) x--, y--; g[x].push_back(y); if (!is_directed) g[y].push_back(x); } return g; } // Input of Weighted Graph template <typename T> WeightedGraph<T> wgraph(int N, int M = -1, bool is_directed = false, bool is_1origin = true) { WeightedGraph<T> g(N); if (M == -1) M = N - 1; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; T c; cin >> c; if (is_1origin) x--, y--; g[x].eb(x, y, c); if (!is_directed) g[y].eb(y, x, c); } return g; } // Input of Edges template <typename T> Edges<T> esgraph(int N, int M, int is_weighted = true, bool is_1origin = true) { Edges<T> es; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; T c; if (is_weighted) cin >> c; else c = 1; if (is_1origin) x--, y--; es.emplace_back(x, y, c); } return es; } // Input of Adjacency Matrix template <typename T> vector<vector<T>> adjgraph(int N, int M, T INF, int is_weighted = true, bool is_directed = false, bool is_1origin = true) { vector<vector<T>> d(N, vector<T>(N, INF)); for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; T c; if (is_weighted) cin >> c; else c = 1; if (is_1origin) x--, y--; d[x][y] = c; if (!is_directed) d[y][x] = c; } return d; } template <typename G> struct EulerTour { private: struct RMQ { int s; using P = pair<int, int>; vector<P> seg; P UNIT = P(1 << 30, -1); RMQ(int N) : s(1) { while (s < N) s <<= 1; seg.assign(2 * s, UNIT); } void set(int k, P x) { seg[k + s] = x; } P operator[](int k) const { return seg[k + s]; } void build() { for (int k = s - 1; k > 0; k--) { seg[k] = min(seg[2 * k], seg[2 * k + 1]); } } P query(int a, int b) const { P R = UNIT; for (a += s, b += s; a < b; a >>= 1, b >>= 1) { if (a & 1) R = min(R, seg[a++]); if (b & 1) R = min(R, seg[--b]); } return R; } int size() const { return s; } }; vector<int> down, up; int id; RMQ rmq; void init(G &g, int root) { rmq.set(id++, {-1, -1}); dfs(g, root, -1, 0); for (int i = 0; i < (int)g.size(); i++) { if (down[i] == -1) { rmq.set(id++, {-1, -1}); dfs(g, i, -1, 0); } } rmq.build(); } void dfs(G &g, int c, int p, int dp) { down[c] = id; rmq.set(id++, {dp, c}); for (auto &d : g[c]) { if (d == p) continue; dfs(g, d, c, dp + 1); } up[c] = id; rmq.set(id++, {dp - 1, p}); } public: // remind : because of additional node, // DS on tour should reserve 2 * n + 2 nodes. EulerTour(G &g, int root = 0) : down(g.size(), -1), up(g.size(), -1), id(0), rmq(2 * g.size() + 2) { init(g, root); trc(down); trc(up); } pair<int, int> idx(int i) const { return {down[i], up[i]}; } int lca(int a, int b) const { if (down[a] > down[b]) swap(a, b); return rmq.query(down[a], down[b] + 1).second; } template <typename F> void node_query(int a, int b, F &f) { int l = lca(a, b); f(down[l], down[a] + 1); f(down[l] + 1, down[b] + 1); } template <typename F> void edge_query(int a, int b, F &f) { int l = lca(a, b); f(down[l] + 1, down[a] + 1); f(down[l] + 1, down[b] + 1); } int size() const { return int(rmq.size()); } }; using namespace std; #define ll long long #define inf 0x7FFFFFFF #define llinf 0x7FFFFFFFFFFFFFFF #define ff first #define ss second #define FOR(i, a, b) for(int i = a; i < b; i++) #define ROF(i, a, b) for(int i = a - 1; i >= b; i--) //#define assert void //#pragma GCC optimize("O3") //#pragma GCC optimize("unroll-loops") //#define int ll struct dsu { dsu(int n) { p.resize(n, -1); pp.resize(n); for (int i = 0; i < n; i++) pp[i] = i; r.resize(n, 0); } inline int par(int x) { return pp[_par(x)]; } inline int _par(int x) { return p[x] == -1 ? x : p[x] = _par(p[x]); } inline void merge(int a, int b) { a = _par(a); b = _par(b); if (a == b)return; if (r[a] < r[b]) { swap(a, b); swap(pp[a], pp[b]); } if (r[a] == r[b]) r[a]++; p[b] = a; } vector<int> p, r, pp; }; signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int N, D, T; rd(N, D, T); vector<int> t(N); for (int i = 0; i < N; i++) rd(t[i]); int l = 0, r = 2e6, m = 0; int ans = 0; while (l < r) {//aliens HAHAHAhaha ha ha :sob: m = (l + r) / 2; vector<pair<int,int>> st; st.reserve(N); struct node { int p = -1;//prev int n = -1;//next int lz = 0; double v = 0; int c = 0; // count owo!!! node() {}; node(double v, int c) : v(v), c(c) {}; }; vector<node> st2; st2.reserve(N); dsu pls(N); int start = 0; int amt = 0;//amount added function<void(int)> kill = [&](int i) { int n = st2[i].n; //assert(n != -1); if (n == -1) return; if ((st2[i].v + (double)st2[i].lz > st2[n].v)) { int p = st2[i].p; st2[n].p = p; if (p != -1) { st2[p].lz += st2[i].lz; st2[p].n = n; pls.merge(p, i); //merge i to p kill(p); } else { // DEAD amt -= st2[i].lz; //recycle owo start = n; } } }; for (int i = 0; i < N; i++) { //create and then upd if (st2.size()) { st2.push_back(node(st2[start].v + (double)amt + m, st2[start].c+1)); st2[i - 1].n = i; st2[i].p = i - 1; kill(i - 1); } else { st2.push_back(node()); } int o = i; if (t[i] <= T) { while (st.size() && st.back().ff >= t[i] - i) { st.pop_back(); } st.push_back({ t[i] - i, i}); } else { while (st.size() && st.back().ff > T - i) st.pop_back(); if (st.size()) { o = st.back().ss; } else o = -1; } //cout << o << ","; if(o >= start){ int t = pls.par(o); st2[t].lz++; amt++; kill(t); } //cout << amt << ","; } //cout << endl; int c = st2[start].c; //cout << c << endl; if (c <= D) { r = m; ans = round((double)st2[start].v + (double)amt - (double)D * m); } else { //cout << "fuck" << endl; l = m + 1; } } cout << ans << endl; // n log n inverse ackermann n please pass i swear to god }

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

prison.cpp:17: warning: ignoring '#pragma region kyopro_template' [-Wunknown-pragmas]
   17 | #pragma region kyopro_template
      | 
prison.cpp:314: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
  314 | #pragma endregion
      |
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...