| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 315428 | VROOM_VARUN | Dancing Elephants (IOI11_elephants) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// /*
// ID: varunra2
// LANG: C++
// TASK: elephants
// */
// // cp ~/SNIPPETS/Template/testing/*
// // gen.cpp and build with IORun
// // create brute.cpp and build with IORun
// // this runs 5 random tests against a with checkts against brute
// // ./test.sh 5 a
// // any failed tests will be saved under data/failed*{inp,out,oac} pattern. .oac is output of brute, .out is output of program, .inp is output of gen
// #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 = 3;
// 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.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;
// }