Submission #315350

#TimeUsernameProblemLanguageResultExecution timeMemory
315350VROOM_VARUNDancing Elephants (IOI11_elephants)C++14
26 / 100
24 ms1792 KiB
/* ID: varunra2 LANG: C++ TASK: elephants */ #include <bits/stdc++.h> using namespace std; #ifdef DEBUG #include "lib/debug.h" #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #define debug_arr(...) \ cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__) #pragma GCC diagnostic ignored "-Wsign-compare" //#pragma GCC diagnostic ignored "-Wunused-parameter" //#pragma GCC diagnostic ignored "-Wunused-variable" #else #define debug(...) 42 #endif #define EPS 1e-9 #define IN(A, B, C) assert(B <= A && A <= C) #define INF (int)1e9 #define MEM(a, b) memset(a, (b), sizeof(a)) #define MOD 1000000007 #define MP make_pair #define PB push_back #define all(cont) cont.begin(), cont.end() #define rall(cont) cont.end(), cont.begin() #define x first #define y second const double PI = acos(-1.0); typedef long long ll; typedef long double ld; typedef pair<int, int> PII; typedef map<int, int> MPII; typedef multiset<int> MSETI; typedef set<int> SETI; typedef set<string> SETS; typedef vector<int> VI; typedef vector<PII> VII; typedef vector<VI> VVI; typedef vector<string> VS; #define rep(i, a, b) for (int i = a; i < (b); ++i) #define trav(a, x) for (auto& a : x) #define sz(x) (int)(x).size() typedef pair<int, int> pii; typedef vector<int> vi; #pragma GCC diagnostic ignored "-Wsign-compare" // util functions int n, l; const int BLOCK = 400; multiset<PII> st; VI vals; struct block { VI pnts; int siz; VI dp1; // how many blocks for suffix starting at i, ending at pnts.size()? VI dp2; // where does the optimal solution held at dp1[i] end? void init() { sort(all(pnts)); siz = sz(pnts); dp1.clear(); dp2.clear(); dp1.resize(siz); dp2.resize(siz); } void calc() { init(); int p1 = siz - 1; for (int i = siz - 1; i >= 0; i--) { while ((pnts[p1] - pnts[i]) > l) p1--; if (p1 == siz - 1) { dp1[i] = 1; dp2[i] = pnts[i] + l + 1; } else { dp1[i] = dp1[p1 + 1] + 1; dp2[i] = dp2[p1 + 1]; } } } void ins(int x) { pnts.PB(x); calc(); } void del(int x) { VI cop; trav(xx, pnts) { if (xx == x) continue; cop.PB(xx); } pnts = cop; calc(); } PII get(int x) { // how many to cover rest of this block starting at x // where would it end at auto it = lower_bound(all(pnts), x); if (it == pnts.end()) { return MP(0, x); } int ind = it - pnts.begin(); return MP(dp1[ind], dp2[ind]); } }; vector<block> blocks; void rebuild(bool done = true) { // we are rebuilding blocks VI pnts; pnts = vals; blocks.clear(); sort(all(pnts)); VI cur; st.clear(); for (int i = 0; i < sz(pnts); i++) { cur.PB(pnts[i]); st.insert(MP(pnts[i], sz(blocks))); if (sz(cur) == BLOCK) { block nw; nw.pnts = cur; nw.calc(); cur.clear(); blocks.PB(nw); } } if (!cur.empty()) { block nw; nw.pnts = cur; nw.calc(); cur.clear(); blocks.PB(nw); } } void ins(int x) { // what block are we in? auto xx = *st.lower_bound(MP(x, -1)); blocks[xx.y].ins(x); st.insert(MP(x, xx.y)); } void del(int x) { auto xx = *st.lower_bound(MP(x, -1)); blocks[xx.y].del(x); st.erase(st.lower_bound(MP(x, -1))); } int qry() { int ret = 0; int ind = -1; for (int i = 0; i < sz(blocks); i++) { auto x = blocks[i].get(ind); ret += x.x; ind = x.y; } return ret; } void init(int N, int L, int X[]) { n = N; l = L; for (int i = 0; i < n; i++) { vals.PB(X[i]); } rebuild(false); // first time building } int cnt = 0; int update(int i, int y) { int cur = vals[i]; vals[i] = y; del(cur); ins(y); cnt++; if (cnt % BLOCK == 0) { rebuild(); } return qry(); } // int main() { // #ifndef ONLINE_JUDGE // freopen("elephants.in", "r", stdin); // freopen("elephants.out", "w", stdout); // #endif // cin.sync_with_stdio(0); // cin.tie(0); // int n, l; // int x[n]; // int q; // cin >> n >> l; // for (int i = 0; i < n; i++) { // cin >> x[i]; // } // init(n, l, x); // cin >> q; // while (q--) { // int i, y; // cin >> i >> y; // cout << update(i, y) << '\n'; // } // return 0; // }
#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...