Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <map>
- #include <cmath>
- #include <cassert>
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- #define De cerr<<
- #define W cout <<
- #define R cin >>
- const ll INF(1e9);
- template <class T> void
- multiass(T& a, T& b, T c, T d)
- { a = c, b = d; }
- template <class data>
- class Lazy
- { /* arr[K + IND * K]: [ (null) # # ] [ 1 # # ] [ 2 # # ] <- IND = 2; INS = 0; K = 3; (K != sqrt(IND) just for ex.)
- Index: 0 1 2 3 4 5 6 7 8
- Pred: 6 * * 0 * * 3 * *
- Index from 1 to IND */
- public:
- const ll mCNT = 1e4, mSIZE = mCNT * getK(mCNT); // mCNT -- max IND; mSIZE - max IND * K;
- const ll EMPTY = -1e5;
- ll IND = 0, INS = 0, K = 0;
- vector< pair<data, int> > arr;
- /* IND -- number of indexed.
- INS -- number of inserted.
- K = getK(IND) -- number of empty cells after not empty. */
- ll getK (ll n) { return max((ll)2, (ll)(sqrt(n))); }
- Lazy () { W "DEFAULT" << endl;
- }
- Lazy (int len){ W "LENGTH" << endl;
- IND = len, K = getK(len);
- arr.resize(K + IND * K);
- for (int i(0); i < K + IND * K; ++i) arr[i] = {EMPTY, EMPTY};
- for (int i(0); i <= IND * K; i += K)
- { arr[i].first = 0;
- arr[i].second = i - K;
- } arr[0].second = IND * K;
- }
- data& operator [] (int index) { //W "OPER.[]" << endl;
- assert(0 <= index and index <= IND);
- if (!index) W "You really want null?" << endl;
- return arr[K * index].first;
- }
- data& at (int index) { W "AT IND." << endl;
- norm();
- return (*this)[index];
- }
- void inside () {
- W "--------------------------------[ INSIDE ]--------------------------------" << endl;
- W "IND = " << IND << ";\t" << "INS = " << INS << ";\t" << "K = " << K << ";\n";
- W "\tValues:\t"; for (auto i : arr) W " "<<i.first << '\t'; W endl;
- W "\t Index:\t"; for (auto i(0); i < K + IND*K; ++i) W "["<<i<<"]\t"; W endl;
- W "\t Prevs:\t"; for (auto i : arr) W " "<<i.second << '\t';W endl;
- W "--------------------------------[ INSIDE ]--------------------------------" << endl;
- }
- void print () { W "PRINT" << endl;
- for (int i(1); i <= IND; ++i)
- W (*this)[i] << ' ';
- W endl;
- }
- void norm () { W "NORM" << endl;
- int old = IND * K + K;
- IND += INS; INS = 0; K = getK(IND);
- int cut(arr[0].second), paste(K * IND), prev(0);
- arr.resize(IND * K + K);
- for (int i(old); i < arr.size(); ++i) arr[i] = {EMPTY, EMPTY};
- while (cut)
- { //W cut << ' ' << paste << ' ' << prev << endl;
- assert(cut <= paste);
- if (cut < paste)
- assert(arr[paste].second == EMPTY);
- /*--------------------------------*/
- swap(arr[cut], arr[paste]);
- arr[prev].second = paste;
- /*--------------------------------*/
- cut = arr[paste].second;
- prev = paste;
- paste -= K;
- /*--------------------------------*/
- }
- }
- void ins (int after, data X) { W "INSERT after " << after << " " << X << endl;
- assert(0 <= after && after <= IND);
- int ind = after * K;
- if (arr[ind + K - 1].second != EMPTY) norm();
- for (int dx(1); dx < K; ++dx)
- {
- if (arr[ind + dx].second == EMPTY)
- {
- int next( (ind + K) % (IND*K + K) );
- arr[ind + dx] = {X, arr[next].second};
- arr[next].second = ind + dx;
- W "INSERTED TO " << ind + dx << endl;
- }
- } ++INS;
- }
- void del (int index) {
- }
- };
- int main ()
- { // Add resize
- Lazy<int> L(0);
- char c; int a, b;
- while (cin >> c)
- {
- switch(c)
- {
- case 'p': L.print(); break;
- case 's': L.inside(); break;
- case 'i': cin >> a >> b; L.ins(a, b); break;
- case 'n': L.norm();
- }
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment