Submission #885887

#TimeUsernameProblemLanguageResultExecution timeMemory
885887ZaniteHoliday (IOI14_holiday)C++17
7 / 100
268 ms16256 KiB
// When we're in drama, // there's that person over there // polishing their skill. // 抗えぬ運命と決まっているのなら // 私はあなたの為に生きたい // 誰かの為に生きてこその人生 // 輝を増すこと知っているから // Zanite's template #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include "holiday.h" // Pragmas // #pragma GCC optimize("Ofast") // #pragma GCC optimize("unroll-loops") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") // Namespaces using namespace std; using namespace __gnu_pbds; // Data types using si = short int; using ll = long long; using ull = unsigned long long; using lll = __int128; using ld = long double; // Pairs using pii = pair<int, int>; using psi = pair<si, si>; using pll = pair<ll, ll>; using plll = pair<lll, lll>; using pld = pair<ld, ld>; #define fi first #define se second // PBDS template<typename Z> using ordered_set = tree<Z, null_type, less<Z>, rb_tree_tag, tree_order_statistics_node_update>; // Various outputs template<typename Y, typename Z> ostream& operator<<(ostream &os, const pair<Y, Z> &p) { return os << '(' << p.fi << ',' << p.se << ')'; } template<typename Z> ostream& operator<<(ostream &os, const vector<Z> &v) { os << '{'; bool _first = 1; for (auto &i : v) {if (!_first) os << ", "; os << i; _first = 0;} return os << '}'; } template<typename Z, ull sz> ostream& operator<<(ostream &os, const array<Z, sz> &arr) { os << '{'; bool _first = 1; for (auto &i : arr) {if (!_first) os << ", "; os << i; _first = 0;} return os << '}'; } // Quick macro functions #define sqr(x) ((x)*(x)) #define debug(x) cout << #x << " = " << (x) << '\n' #define debugV(v, x) cout << #v << "[" << (x) << "] = " << (v[x]) << '\n' #define rrebug(x) cerr << #x << " = " << (x) << '\n' #define rrebugV(v, x) cerr << #v << "[" << (x) << "] = " << (v[x]) << '\n' #define All(x) x.begin(), x.end() #define Sort(x) sort(All(x)) #define Reverse(x) reverse(All(x)) #define Uniqueify(x) Sort(x); x.erase(unique(All(x)), x.end()) #define RandomSeed chrono::steady_clock::now().time_since_epoch().count() #define MultipleTestcases int _tc; cin >> _tc; for (int _cur_tc = 1; _cur_tc <= _tc; _cur_tc++) // Check min and max template<typename Z> bool chmin(Z &a, Z b) {return (b < a) ? a = b, true : false;} template<typename Z> bool chmax(Z &a, Z b) {return (b > a) ? a = b, true : false;} // Modular arithmetic template<int MOD> class ModInt { public: int v; ModInt() : v(0) {} ModInt(long long _v) { v = int((-MOD < _v && _v < MOD) ? (_v) : (_v % MOD)); if (v < 0) v += MOD; } friend bool operator==(const ModInt &a, const ModInt &b) {return a.v == b.v;} friend bool operator!=(const ModInt &a, const ModInt &b) {return a.v != b.v;} friend bool operator< (const ModInt &a, const ModInt &b) {return a.v < b.v;} friend bool operator<=(const ModInt &a, const ModInt &b) {return a.v <= b.v;} friend bool operator> (const ModInt &a, const ModInt &b) {return a.v > b.v;} friend bool operator>=(const ModInt &a, const ModInt &b) {return a.v >= b.v;} ModInt &operator+=(const ModInt &a) {if ((v += a.v) >= MOD) v -= MOD; return *this;} ModInt &operator-=(const ModInt &a) {if ((v -= a.v) < 0) v += MOD; return *this;} ModInt &operator*=(const ModInt &a) {v = 1ll * v * a.v % MOD; return *this;} ModInt &operator/=(const ModInt &a) {return (*this) *= inverse(a);} friend ModInt pow(ModInt a, long long x) { ModInt res = 1; for (; x; x /= 2, a *= a) if (x & 1) res *= a; return res; } friend ModInt inverse(ModInt a) {return pow(a, MOD - 2);} ModInt operator+ () const {return ModInt( v);} ModInt operator- () const {return ModInt(-v);} ModInt operator++() const {return *this += 1;} ModInt operator--() const {return *this -= 1;} friend ModInt operator+(ModInt a, const ModInt &b) {return a += b;} friend ModInt operator-(ModInt a, const ModInt &b) {return a -= b;} friend ModInt operator*(ModInt a, const ModInt &b) {return a *= b;} friend ModInt operator/(ModInt a, const ModInt &b) {return a /= b;} friend istream &operator>>(istream &is, ModInt &v) {return is >> v.v;} friend ostream &operator<<(ostream &os, const ModInt &v) {return os << v.v;} }; const int ModA = 998244353; const int ModC = 1e9 + 7; using MintA = ModInt<ModA>; using MintC = ModInt<ModC>; // Other constants const ll INF = 1e18; const ll iINF = 1e9; const ld EPS = 1e-9; const ld iEPS = 1e-6; pll operator+(const pll &a, const pll &b) { return make_pair(a.fi + b.fi, a.se + b.se); } pll operator-(const pll &a, const pll &b) { return make_pair(a.fi - b.fi, a.se - b.se); } struct FenwickTree { using Elm = pll; int sz; vector<Elm> BIT; FenwickTree(int sz) : sz(sz) { BIT.assign(sz+1, {0, 0}); } void update(int idx, Elm val) { for (; idx <= sz; idx += (idx & -idx)) {BIT[idx] = BIT[idx] + val;} } Elm sum(int idx) { Elm ret = {0, 0}; for (; idx > 0; idx -= (idx & -idx)) {ret = ret + BIT[idx];} return ret; } Elm query(int l, int r) {return sum(r) - sum(l-1);} }; const int maxN = 100'023; // int N, start, D; ll A[maxN]; vector<ll> getOpt(vector<ll> &P, int mult) { int K = P.size(); vector<pll> compress; for (int i = 0; i < K; i++) { compress.push_back({P[i], i}); } sort(All(compress), greater<pll>()); vector<int> idx(K); for (int i = 0; i < K; i++) { idx[compress[i].se] = i + 1; } vector<ll> ret; int copt = 0; FenwickTree F(K); F.update(idx[0], {P[0], 1}); auto get = [&](int consider, int t, bool &success) { int tk = t - mult * (consider + 1); if (tk <= 0) { success = false; return 0ll; } int l = 1, r = K; ll ans = 0; while (l <= r) { int m = (l + r) / 2; pll cur = F.sum(m); if (cur.se <= tk) { ans = cur.fi; l = m + 1; } else { r = m - 1; } } success = true; // cout << "get " << consider << " " << t << ": " << ans << "\n"; return ans; }; for (int i = 0; i <= 3*K; i++) { bool csucc = false; ll cur = get(copt, i, csucc); if (!csucc) { ret.push_back(cur); continue; } while (true) { if (copt == K-1) break; F.update(idx[copt + 1], {P[copt + 1], 1}); bool nsucc = false; ll nxt = get(copt + 1, i, nsucc); if (nsucc && (nxt >= cur)) { cur = nxt; copt++; } else { F.update(idx[copt + 1], {-P[copt + 1], -1}); break; } } ret.push_back(cur); } return ret; } ll findMaxAttraction(int N, int start, int D, int attraction[]) { for (int i = 1; i <= N; i++) A[i] = attraction[i-1]; D = min(D, 3*N); start++; vector<ll> L, R; for (int i = start-1; i >= 0; i--) L.push_back(A[i]); for (int i = start+1; i <= N+1; i++) R.push_back(A[i]); // debug(L); debug(R); ll ans = 0; for (int tl = 1; tl <= 2; tl++) { int tr = 3 - tl; vector<ll> optL = getOpt(L, tl); vector<ll> optR = getOpt(R, tr); while ((int)optL.size() <= D) optL.push_back(optL.back()); while ((int)optR.size() <= D) optR.push_back(optR.back()); // debug(optL); debug(optR); // don't visit attraction at start for (int i = 0; i <= D; i++) { chmax(ans, optL[i] + optR[D - i]); } // visit attraction at start for (int i = 0; i <= D-1; i++) { chmax(ans, optL[i] + optR[D-1 - i] + A[start]); } } return ans; } // あなたの傍に居させて... // dibisakan
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...