https://www.spoj.com/problems/ADALIST/, C++ (gcc)

Language: Layout:

#include <bits/stdc++.h>

using namespace std;

#define pb push_back

struct node{
    int v;
    node* nxt, *prv;
    
    node(int v_, node* prv_, node* nxt_) : v(v_), prv(prv_), nxt(nxt_){}
};

struct lists{
    node* head, *tail;
    int sz;
    
    lists() : sz(0), head(NULL){}
    
    void insert(int x){
        sz++;
        if(head == NULL){
            head = tail = new node(x, NULL, NULL);
            return;
        }
        tail -> nxt = new node(x, tail, NULL);
        tail = tail -> nxt;
    }
    
    void insert_first(int x){
        sz++;
        if(head == NULL){
            head = tail = new node(x, NULL, NULL);
            return;
        }
        head -> prv = new node(x, NULL, head);
        head = head -> prv;
    }
    
    void insert_at(int pos, int val){
        if(pos == sz) return insert(val);
        if(pos == 0) return insert_first(val);
        node* cur = head;
        for(int j = 0; j < pos; j++) cur = cur -> nxt;
        cur -> prv -> nxt = new node(val, cur -> prv, cur);
        cur -> prv = cur -> prv -> nxt;
        sz++;
    }
    
    void erase(int pos){
        if(pos > sz) return;
        if(pos == 0){
            sz--;
            head = head -> nxt;
            if(!head) tail = NULL;
            else head -> prv = NULL;
            return;
        }
        if(pos == sz-1){
            sz--;
            tail = tail -> prv;
            if(!tail) head = NULL;
            else tail -> nxt = NULL;
            return;
        }
        sz--;
        node* cur = head;
        for(int i = 0; i < pos; i++) cur = cur -> nxt;
        cur -> prv -> nxt = cur -> nxt;
        cur -> nxt -> prv = cur -> prv;
    }
    
    int at(int pos){
        node* cur = head;
        for(int j = 0; j < pos; j++) cur = cur -> nxt;
        return cur -> v;
    }
    
    void print(){
        node* t = head;
        while(t) cout << t -> v << " ", t = t -> nxt;
        cout << endl;
    }
    
    int size(){
        return sz;
    }
};

struct blocks{
    lists v;
    int st, ed;
    const int mx_cap;
    
    blocks(const vector<int>& t, int s = -1, int mx = 400) : mx_cap(mx){
        for(int i = 0; i < t.size(); i++) v.insert(t[i]);
        
        st = s;
        ed = s +(int)t.size()-1;
    }
    
    int erase(int pos, const int prv){
        if(ed < pos) return -1;
        
        if(st > pos){
            int ret = v.at(0);
            v.erase(0);
            if(prv == -1) ed--;
            else v.insert(prv);
            return ret;
        }
        
        v.erase(pos-st);
        if(prv == -1) ed --;
        else v.insert(prv);
        return -1;
    }
    
    int insert(int pos, int val, int prv){
        if(st > pos){
            if(v.size() == mx_cap){
                int ret = v.at(ed - st);
                v.erase(ed - st);
                v.insert_first(prv);
                return ret;
            }
            ed++;
            v.insert_first(prv);
            return -1;
        }
        if(v.size() == mx_cap){
            int ret = v.at(ed - st);
            v.erase(ed - st);
            v.insert_at(pos - st, val);
            return ret;
        }
        ed++;
        v.insert_at(pos - st, val);
        return -1;
    }
    
    int at(int pos){
        return v.at(pos - st);
    }
    
    int size(){
        return v.sz;
    }
    
    void print(){
        cout << st << " " << ed << " : ";
        v.print();
    }
};

struct sqrt_{
    const int blk_sz, N;
    int blks, n;
    
    vector<blocks*> b;
    
    sqrt_(const vector<int>& v, int sz = 400) : blk_sz(sz), N(6e5 + 5){
        n = v.size();
        blks = n/blk_sz + 1;
        if(n % blk_sz == 0) blks--;
        int st = 0;
        
        for(int j = 0; j < blks; j++){
            vector<int> cur;
            if(st < n){
                int ed = min(n-1, st+sz-1);
                for(int j = st; j <= ed; j++) cur.pb(v[j]);
            }
            b.pb(new blocks(cur, (st < n)? st : -1, sz));
            st += blk_sz;
        }
    }
    
    void insert(int pos, int val){
        int blk = pos/blk_sz;
        if(n % blk_sz == 0){
            vector<int> cur;
            b.pb(new blocks(cur, n, blk_sz));
            blks++;
        }
        n++;
        int prv = -1;
        for(int j = blk; j < blks; j++){
            prv = b[j] -> insert(pos, val, prv);
            //print();
            if(prv == -1) return;
        }
    }
    
    void erase(int pos){
        int blk = pos/blk_sz;
        int prv = -1;
        for(int j = blks-1; j >= blk; j--){
            prv = b[j] -> erase(pos, prv);
        }
        if(b.back() -> size() == 0) b.pop_back(), blks--;
        n--;
    }
    
    int at(int pos){
        int blk = pos/blk_sz;
        return b[blk] -> at(pos);
    }
    
    void print(){
        cout << "number of blocks : " << blks << ", n : " << n << endl;
        for(int j = 0; j < blks; j++)
            b[j] -> print();
    }
};

int main(){
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    
    int n, q;
    scanf("%d %d",&n ,&q);
    vector<int> a(n);
    for(int j = 0; j < n; j++) scanf("%d",&a[j]);
    
    sqrt_ sq(a);
    //sq.print();
    
    while(q--){
        int typ;
        scanf("%d",&typ);
        if(typ == 1){
            int k, x;
            scanf("%d %d",&k ,&x);
            sq.insert(k-1, x);
            
            /*cout << typ << " " << k << " " << x << " : " << endl;
            sq.print();
            cout << endl;*/
        }
        else if(typ == 2){
            int k; scanf("%d",&k);
            sq.erase(k-1);
            
            /*cout << typ << " " << k << " : " << endl;
            sq.print();*/
        }
        else{
            int at;
            scanf("%d",&at);
            printf("%d\n",sq.at(at-1));
        }
    }
    return 0;
}

1000 12
11191825 39764528 24741827 95798530 69614460 21574491 49581914 97690797 37169513 45601750 50320064 56735071 61287466 64414323 9202523 36446067 88700672 17675950 64087508 594492 60438377 63409019 22031743 28717154 88232786 14499666 62005062 57408797 35040160 53479066 58941996 81853415 72455040 4332532 19451284 13806641 52295762 30631652 32392314 13742138 15407275 64149588 83780186 72963572 1890829 50053725 95677185 83217124 6659527 24945184 48351552 7639118 89483299 80763114 25202200 7366954 90764681 90274642 52302746 52451915 84999458 2987958 15458443 98144470 95970064 86210609 42567919 50545635 6100297 83479115 85058258 24626763 66063349 34938521 19755510 86519553 84421599 48378262 8544383 1255726 96501401 44234384 8367464 52242451 83870575 916630 34094572 31701314 18614668 75586021 41733843 4515731 15194711 80626083 90777572 21286865 62757040 49765449 92180392 68286691 12637150 4446777 64075867 38732270 87593860 49522466 78308714 35391334 43781181 28916410 91453927 12710859 11505375 47726465 63973183 54754544 96936699 23929380 1377759 77167270 27084888 81544332 12101590 92641979 47500010 28187694 16554705 15057481 56291606 18375979 78501112 16501885 67005672 79443270 89662991 19085224 43310762 73693697 27405613 38330982 13565690 27141836 4859900 51730023 19525542 285416 3240311 96778437 96991126 11770172 33903437 90467352 56025107 44385013 15310916 22855544 53099508 726946 34159670 48982128 93691275 5519151 53569469 51749908 2519309 408609 82363033 11026262 72437697 36815206 53670496 40062651 64565806 91125071 35996723 56312419 57410181 23373379 92593236 72390958 15165381 27914951 45819440 41820001 14681622 51710801 15310820 11777085 32944623 39596824 86033516 8109108 43048805 95291571 61817284 47174886 38780793 19194952 68498776 89935297 39507794 8872375 16569470 14751330 27332944 62667732 4330807 30906866 73437721 10834898 68274916 74486942 46775304 14880619 21968747 36644680 89719366 97864991 11191508 6593403 83364001 30732850 25897472 10159719 79232079 87074767 56818596 92260621 98590746 26025639 21786275 20705415 53562200 59204988 96958646 6962271 34100269 62073822 1218269 47020522 51194547 41342293 31662393 92302081 44104358 99169592 31224660 34387751 95961739 25659322 60852040 46957757 5203592 6318977 40968943 47755865 97755635 48574791 21522021 89154321 28678192 6296916 492172 42587968 29573851 5358154 61975364 44691145 20414916 793160 79834749 17762602 40047327 55084329 87009548 55029238 11362747 66176407 76807718 72068382 94526286 31263772 43653567 24046431 14815636 34964298 68966086 81088178 53967383 13137826 74173786 19011745 98383266 36648852 87625140 92944966 61551958 72935013 39802853 6913629 832161 66989544 31026425 27593347 83344524 62052246 12548083 34451995 42056124 92958339 38002775 44326070 86172847 17088341 97119369 26344628 95485371 94511215 6939917 64372730 70019286 99215221 58250156 76833596 34721535 62584316 19636181 15792425 10432994 73419541 43252537 51807634 32359299 12942916 73101910 1354959 94295325 33318503 59485177 78316965 64787082 20908875 31921087 68490634 71995345 88655630 68740205 42551632 34060445 59065093 30325561 47568967 90003429 25053713 13901419 38953453 25679405 51577639 6220651 43849278 82835231 30675375 72220596 50146217 33405091 96379057 61780386 46240371 32221707 16104583 15908459 69989079 2169701 1249220 19622310 92894899 24241941 64354531 14330766 9925204 39852916 72337115 80862823 64234163 37265724 72171559 89056323 39269280 65153706 84449744 73003288 57728230 44021217 60623366 15870694 95372256 80835546 86496872 8246594 68711281 15876731 8798128 32197053 26903947 65702889 31730808 84637924 44688228 25631578 79932228 34926886 50529404 30142786 10524852 97811425 48936537 7749291 66084501 40520045 54891409 71269290 92733212 32266923 62594217 98701113 798763 88612362 59661718 42736009 8575515 65338754 46932511 95133866 41951347 81488917 57064057 3688989 57190280 45571299 76676063 73273622 38154721 4728681 73480 61294055 13384220 61452130 24348638 69828373 73304479 54122883 97462445 52676466 88387717 52391517 63933932 4258744 15713052 17815762 33483001 95113705 12637220 30181485 68985586 7143984 42098794 34155190 3726352 67314385 57859041 54868315 2550828 41527047 73904336 8033552 16408657 5350331 61808420 72206773 37098050 49669652 62497538 5097404 45342172 5893624 29448880 29871442 21697521 35429754 39909730 33370293 92894109 29337226 66416690 16510877 29425991 57055367 82955903 26396974 15007356 48825969 85237386 68722443 9778405 96825738 295824 19597890 51538236 84969348 92376623 8338153 13776565 33604820 65616474 75361000 25230771 11572349 52756667 12684094 40706610 63569535 24122600 50879914 30428061 13655047 164790 70912856 98356101 64380183 63610397 2309248 83293499 88430412 69643355 11818287 40173908 70239024 43743688 34002616 75472742 36501894 5126703 32389545 63525983 84028544 17695805 24121516 21936027 31667826 55050877 29305967 19667329 2862409 82428952 561559 48395983 88350446 9770769 16920868 27344822 73483814 25200821 15543309 54698519 65104990 719229 64071168 98726228 14796233 44455114 37593503 89070746 8820450 32832807 13638088 85718760 34336360 32140532 80092258 4914761 65247755 9300742 99922096 18417534 69760937 88576037 71759514 96962678 80195215 89775426 81635038 62658591 11786915 61332868 77636976 18140598 30268289 77845240 38783380 70086584 19449675 68707723 50633606 19330820 21396713 66717018 31817208 56760870 79540532 73519950 74622363 60505582 80036647 82129014 19176329 71258490 93209812 61429917 53243288 18285954 40747202 59559223 93598781 31769365 78712019 80301263 1094079 33711426 44402341 89948811 38339925 71151225 96213827 3944669 371138 7920247 79584849 92112445 77387213 37876640 37152157 74564836 40400584 17065546 75449213 74015652 24833606 14084051 72420377 39864195 16432538 33309706 57774930 61490607 77457776 85898802 78203827 28898328 75594893 96583510 39581196 19792486 81139605 70710933 61977751 26645655 80265099 20389004 46219111 69454917 69520766 13452928 31447681 22814728 27443013 81866771 41321470 81294288 22925237 44544363 77977601 80313417 59525311 71376261 87609547 27192398 48425365 59801487 40444140 39697571 49364099 38402242 40888229 95753213 26119166 58711811 4277571 93165864 77691763 19829805 32447977 27835985 60083732 26027168 38664455 53616479 98490149 20217670 51298083 6198843 38132662 10500316 59018925 83251130 71612700 64904867 59659265 87480851 67664221 20683202 11324195 58996315 49481339 43167151 87719445 61230657 59131842 39506552 90000767 83475730 85681235 64047238 36989685 68011046 53877314 29708038 53616093 70640871 82889343 52557783 59196718 44027519 10281150 73680790 76051700 92531534 97247738 38375384 86047557 93410219 7032414 40344639 1200845 14882621 61456471 31281449 59990810 10152488 1337228 93586396 15987911 89046485 40497075 26502519 14636555 25683698 46447498 52293036 95241834 87054329 42989379 96899154 45863924 31904163 3688843 91867660 41285030 60080076 37859453 60241476 27599920 20301879 17777447 50630442 86026357 36053327 63435323 45769340 98543616 7593075 66220884 44888696 79997834 55720180 74795924 41552697 96441685 44390122 73833653 15968207 11031411 51240808 38275390 74733183 88085799 5349125 72210312 16593024 91451849 42216634 30745230 27330158 40103012 51194785 4179954 41982187 32091232 96093552 77608185 73331917 8076318 9352342 92131285 41478128 91530999 31355253 81657745 83970270 91853231 63727646 89209245 15455958 48207404 1812258 96549652 76749881 31217322 91106840 38526627 17551417 33691336 61399848 35698117 92535207 80426479 15440230 65916813 25659705 51598339 4608325 99512250 65999428 82454911 59305868 56183531 25344809 31896293 20721533 75464745 1477685 18712662 53006552 67710981 6724916 15254977 2673458 64924034 81261005 51221301 86038446 55249451 14070187 8416539 23279783 52307382 58961576 50232166 58524519 31275956 33889376 50798854 2120708 13700574 47882989 96676411 54474951 49505518 65429687 70842102 77829416 97830937 66726292 44689086 71792328 98637714 82638912 93644564 61560959 76885970 91721448 1499597 34039659 5505141 44719368 2009584 5750470 61849212 29974016 52458190 97304784 59219587 29430096 92823803 43433343 55832307 2599920 64175612 31531086 8880631 46828082 33707592 76913669 97488232 24448523 22967281 98901990 11163831 3421795 23393318 10950508 21550423 17143 55443198 97814422 19077252 10874046 10883643 55958808 98151273 86536113 46420169 15933745 19927472 50266374 71925042 71996812 43061419 38904110 57429131 13439974 39915533 22204091 97717815 74769174 37828669 42801552 64978569 39904475 14601460 44573471 40246242 78365798 86068164 90478462 26685598 17240165 30447692 56275889 1532020 34046878 43214296 42320203 42829450 15750503 54915728 59306900 36245880 28255150 5902046 42474611 78669108 88922177 58189419 89773262 96415300 54763659 6134596 27376623 8011336 14714774 325009 34145467 58705619 1037287 68577952 40490771 34863854 7627065 12754176 10912078
2 50
1 23 623 
3 60
3 41 
3 90
1 409 2032
2 263
3 256
3 102
3 120
1 401 1235
2 602

Show compiler warnings [ + ] Compiler args [ - ] Show input
Compilation time: 1.73 sec, absolute running time: 0.11 sec, cpu time: 0.05 sec, memory peak: 3 Mb, absolute service time: 1,85 sec