提出 #9654701

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define DEBUG(x) cerr << #x << ": " << (x) << endl

namespace Tree234 {
    // no function
    using T = char;
    const T e = '\0';
    T f(T a, T b){
        return b;
    }

    // template begin
    struct Node;
    // using Ptr = Node*;
    using Ptr = shared_ptr<Node>;
    struct Node {
        int rank, size, cnt;
        Ptr ch[4];
        bool isLeaf() const {return cnt == 0;}
        bool is4Node() const {return cnt == 4;}
        T val;
        Node(T v=e):rank(0),size(1),ch{nullptr,nullptr,nullptr,nullptr},cnt(0),val(v){}
        Node(Ptr that){
            rank = that->rank; size = that->size; cnt = that->cnt;
            REP(i,cnt)ch[i] = that->ch[i];
            val = that->val;
        }
    };
    // const int HIST_LIM = 8'000'000;
    // const int HIST_REST = 50'000;
    // Node pool[HIST_LIM + HIST_REST];
    // int pool_tail = 0;
    Ptr newNode(T v=e){
        // Ptr ret = &pool[pool_tail++];
        // *ret = Node(v);
        // return ret;
        return make_shared<Node>(v);
    }
    Ptr newNode(Ptr node){
        // Ptr ret = &pool[pool_tail++];
        // *ret = Node(node);
        // return ret;
        return make_shared<Node>(node);
    }
    Ptr update(Ptr node){   // ephemeral
        if(node == nullptr)return nullptr;
        if(node->isLeaf())return node;
        node->rank = node->ch[0]->rank + 1;
        node->size = 0;
        node->val = e;
        REP(i,node->cnt){
            node->size += node->ch[i]->size;
            node->val = f(node->val, node->ch[i]->val);
        }
        return node;
    }
    void debug(Ptr node){
        if(node == nullptr){
            cerr << "-";
        }else if(node->isLeaf()){
            cerr << node->val;
        }else{
            cerr << "[" << node->val << "]";
            cerr << "(";
            REP(i,node->cnt){
                debug(node->ch[i]);
                cerr << ",";
            }
            cerr << ")";
        }
    }

    Ptr splitRoot(Ptr root){
        assert(root != nullptr && root->is4Node());
        Ptr ret = newNode(root);
        Ptr lft = newNode(), rgt = newNode();
        lft->cnt = rgt->cnt = 2;
        lft->ch[0] = ret->ch[0]; lft->ch[1] = ret->ch[1];
        rgt->ch[0] = ret->ch[2]; rgt->ch[1] = ret->ch[3];
        lft = update(lft); rgt = update(rgt);
        ret->cnt = 2;
        ret->ch[0] = lft; ret->ch[1] = rgt;
        return update(ret);
    }
    Ptr splitNode(Ptr node, int k){
        assert(node != nullptr && !node->is4Node() && k < node->cnt && node->ch[k] != nullptr && node->ch[k]->is4Node());
        node = newNode(node);
        Ptr lft = newNode(node->ch[k]);
        Ptr rgt = newNode();
        lft->cnt = rgt->cnt = 2;
        lft->ch[0] = lft->ch[0]; lft->ch[1] = lft->ch[1];
        rgt->ch[0] = lft->ch[2]; rgt->ch[1] = lft->ch[3];
        move_backward(node->ch + k+1, node->ch + node->cnt, node->ch + node->cnt + 1);
        node->cnt += 1;
        node->ch[k] = update(lft); node->ch[k+1] = update(rgt);
        return update(node);
    }
    Ptr _merge(Ptr lft, Ptr rgt, bool rev){
        assert(lft->rank > rgt->rank && !lft->is4Node());
        lft = newNode(lft);
        if(lft->rank == rgt->rank + 1){
            if(rev)move_backward(lft->ch, lft->ch + lft->cnt, lft->ch + lft->cnt + 1);
            lft->ch[!rev ? lft->cnt : 0] = rgt;
            lft->cnt += 1;
            return update(lft);
        }else{
            int k = !rev ? lft->cnt-1 : 0;
            if(lft->ch[k]->is4Node()){
                lft = splitNode(lft, k);
                k = !rev ? lft->cnt-1 : 0;
            }
            lft->ch[k] = _merge(lft->ch[k], rgt, rev);
            return update(lft);
        }
    }
    Ptr merge(Ptr lft, Ptr rgt){
        if(lft == nullptr)return rgt;
        if(rgt == nullptr)return lft;
        if(lft->rank == rgt->rank){
            Ptr ret = newNode();
            ret->cnt = 2;
            ret->ch[0] = lft; ret->ch[1] = rgt;
            return update(ret);
        }else{
            if(lft->rank > rgt->rank){
                if(lft->is4Node()){
                    lft = splitRoot(lft);
                }
                return _merge(lft, rgt, false);
            }else{
                if(rgt->is4Node()){
                    rgt = splitRoot(rgt);
                }
                return _merge(rgt, lft, true);
            }
        }
    }
    pair<Ptr,Ptr> split(Ptr node, int k){
        if(node == nullptr)return make_pair((Ptr)nullptr, (Ptr)nullptr);
        assert(k <= node->size);
        if(k==0){
            return make_pair((Ptr)nullptr, node);
        }else if(k == node->size){
            return make_pair(node, (Ptr)nullptr);
        }
        assert(!node->isLeaf());
        Ptr leftside = nullptr;
        Ptr rightside = nullptr;
        REP(to, node->cnt){
            int sz = node->ch[to]->size;
            if(k <= sz){
                pair<Ptr,Ptr> rec = split(node->ch[to], k);
                leftside = merge(leftside, rec.first);
                rightside = merge(rightside, rec.second);
                while(++to < node->cnt){
                    rightside = merge(rightside, node->ch[to]);
                }
                // free(node);
                return make_pair(leftside, rightside);
            }else{
                leftside = merge(leftside, node->ch[to]);
                k -= sz;
            }
        }
        assert(false);
    }
    Ptr insert(Ptr node, int k, T x){
        pair<Ptr,Ptr> P = split(node, k);
        Ptr nw = newNode(x);
        return merge(merge(P.first, nw), P.second);
    }
    Ptr erase(Ptr node, int k){
        pair<Ptr,Ptr> P1, P2;
        P1 = split(node, k);
        P2 = split(P1.second, 1);
        // free(P2.first);
        return merge(P1.first, P2.second);
    }
    T rangeGet(Ptr node, int l, int r){
        if(node == nullptr)return e;
        assert(0<=l && l<=r && r<=node->size);
        if(r-l == 0)return e;
        if(r-l == node->size)return node->val;
        assert(!node->isLeaf());
        T ret = e;
        REP(to, node->cnt){
            int sz = node->ch[to]->size;
            if(l<sz && r-l != 0){
                T chval;
                chval = rangeGet(node->ch[to], l, min(r, sz));
                ret = f(ret, chval);
            }
            l = max(0, l - sz); r = max(0, r - sz);
        }
        return ret;
    }
    T kth(Ptr node, int k){
        return rangeGet(node, k, k+1);
    }
    Ptr construct(T *arr, int n){
        vector<Ptr> v(n, nullptr);
        REP(i,n)v[i] = Tree234::newNode(arr[i]);
        while(v.size() > 1){
            if(v.size()%2 == 1)v.push_back(nullptr);
            int m = v.size();
            vector<Ptr> w(m/2, nullptr);
            REP(i,m/2){
                w[i] = Tree234::merge(v[2*i+0], v[2*i+1]);
            }
            swap(v, w);
        }
        return v[0];
    }
    // template end
};

// https://atcoder.jp/contests/joisc2012/tasks/joisc2012_copypaste
int m, q;
char s[1'252'830];
int main(){
    scanf("%d%s%d",&m,s,&q);
    int n = strlen(s);
    // initialize
    using Node = Tree234::Node;
    using Ptr = Tree234::Ptr;
    Ptr root = Tree234::construct(s, n);
    // query
    while(q--){
        int l,r,x;
        scanf("%d%d%d",&l,&r,&x);
        Ptr substr = Tree234::split(Tree234::split(root, r).first, l).second;
        pair<Ptr,Ptr> splitted = Tree234::split(root, x);
        root = Tree234::merge(Tree234::merge(splitted.first, substr), splitted.second);
        if(root->size > m){
            root = Tree234::split(root, m).first;
        }
    }
    int sz = root->size;
    REP(i,sz)putchar(Tree234::kth(root, i));
    puts("");
    return 0;
}

提出情報

提出日時
問題 copypaste - コピー＆ペースト
ユーザ rickytheta
言語 C++14 (GCC 5.4.1)
得点 90
コード長 7988 Byte
結果 TLE
実行時間 17855 ms
メモリ 222060 KiB

コンパイルエラー

./Main.cpp: In function ‘int main()’:
./Main.cpp:223:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%s%d",&m,s,&q);
                            ^
./Main.cpp:232:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&l,&r,&x);
                                 ^

ジャッジ結果

セット名 Set01 Set02 Set03 Set04 Set05 Set06 Set07 Set08 Set09 Set10
得点 / 配点 10 / 10 10 / 10 10 / 10 10 / 10 10 / 10 10 / 10 10 / 10 10 / 10 10 / 10 0 / 10
結果
AC × 4
AC × 3
AC × 3
AC × 2
AC × 2
AC × 2
AC × 2
AC × 2
AC × 2
AC × 1
TLE × 3
セット名 テストケース
Set01 01-01, 01-02, 01-03, 01-04
Set02 02-01, 02-02, 02-03
Set03 03-01, 03-02, 03-03
Set04 04-01, 04-02
Set05 05-01, 05-02
Set06 06-01, 06-02
Set07 07-01, 07-02
Set08 08-01, 08-02
Set09 09-01, 09-02
Set10 10-01, 10-02, 10-03, 10-04
ケース名 結果 実行時間 メモリ
01-01 AC 1503 ms 640 KiB
01-02 AC 1408 ms 22356 KiB
01-03 AC 36 ms 1792 KiB
01-04 AC 1 ms 256 KiB
02-01 AC 3203 ms 640 KiB
02-02 AC 3028 ms 44332 KiB
02-03 AC 3143 ms 640 KiB
03-01 AC 4980 ms 896 KiB
03-02 AC 4641 ms 68252 KiB
03-03 AC 4927 ms 768 KiB
04-01 AC 6820 ms 896 KiB
04-02 AC 6475 ms 88540 KiB
05-01 AC 8720 ms 1024 KiB
05-02 AC 8247 ms 110644 KiB
06-01 AC 10570 ms 1152 KiB
06-02 AC 10063 ms 134160 KiB
07-01 AC 12519 ms 1280 KiB
07-02 AC 11970 ms 154724 KiB
08-01 AC 14470 ms 1408 KiB
08-02 AC 13746 ms 176828 KiB
09-01 AC 16587 ms 1536 KiB
09-02 AC 15790 ms 200088 KiB
10-01 TLE 17855 ms 640 KiB
10-02 TLE 17538 ms 222060 KiB
10-03 TLE 17855 ms 640 KiB
10-04 AC 12215 ms 222060 KiB