Submission #9651701

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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 {
    // range add, range min
    using T = int;
    using F = int;
    const T e = INT32_MAX;
    const F fe = 0;
    T f(T a, T b){
        return min(a,b);
    }
    T g(F a, T b){
        return a + b;
    }
    F h(F a, F b){
        return a + b;
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#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 {
    // range add, range min
    using T = int;
    using F = int;
    const T e = INT32_MAX;
    const F fe = 0;
    T f(T a, T b){
        return min(a,b);
    }
    T g(F a, T b){
        return a + b;
    }
    F h(F a, F b){
        return a + b;
    }

    // template begin
    struct Node {
        int rank, size, cnt;
        Node *ch[4];
        bool isLeaf() const {return cnt == 0;}
        bool is4Node() const {return cnt == 4;}
        T val;
        F func;
        Node(T v,F f):rank(0),size(1),ch{nullptr,nullptr,nullptr,nullptr},cnt(0),val(v),func(f) {}
        Node():Node(e,fe){}
        Node(T v):Node(v,fe){}
    };
    Node *applyFunc(Node *node, F func){
        if(node == nullptr)return nullptr;
        node->val = g(func, node->val);
        node->func = h(func, node->func);
        return node;
    }
    Node *update(Node *node){
        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;
    }
    Node *push(Node *node){
        if(node == nullptr)return nullptr;
        if(node->func == fe)return node;
        if(!node->isLeaf())REP(i,node->cnt){
            node->ch[i] = applyFunc(node->ch[i], node->func);
        }
        node->func = fe;
        return node;
    }
    void debug(Node *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 << ")";
        }
    }

    Node *splitRoot(Node *root){
        assert(root != nullptr && root->is4Node());
        root = push(root);
        Node *lft = new Node(), *rgt = new Node();
        lft->cnt = rgt->cnt = 2;
        lft->ch[0] = root->ch[0]; lft->ch[1] = root->ch[1];
        rgt->ch[0] = root->ch[2]; rgt->ch[1] = root->ch[3];
        lft = update(lft); rgt = update(rgt);
        root->cnt = 2;
        root->ch[0] = lft; root->ch[1] = rgt;
        return update(root);
    }
    Node *splitNode(Node *node, int k){
        assert(node != nullptr && !node->is4Node() && k < node->cnt && node->ch[k] != nullptr && node->ch[k]->is4Node());
        node = push(node);
        Node *lft = push(node->ch[k]);
        Node *rgt = new Node();
        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);
    }
    Node *_merge(Node *lft, Node *rgt, bool rev){
        assert(lft->rank > rgt->rank && !lft->is4Node());
        lft = push(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);
        }
    }
    Node *merge(Node *lft, Node *rgt){
        if(lft == nullptr)return rgt;
        if(rgt == nullptr)return lft;
        if(lft->rank == rgt->rank){
            Node *ret = new Node();
            ret->cnt = 2;
            ret->ch[0] = lft; ret->ch[1] = rgt;
            return update(ret);
        }else{
            lft = push(lft); rgt = push(rgt);
            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<Node*,Node*> split(Node *node, int k){
        if(node == nullptr)return make_pair((Node*)nullptr, (Node*)nullptr);
        assert(k <= node->size);
        if(k==0){
            return make_pair((Node*)nullptr, node);
        }else if(k == node->size){
            return make_pair(node, (Node*)nullptr);
        }
        assert(!node->isLeaf());
        Node *leftside = nullptr;
        Node *rightside = nullptr;
        REP(to, node->cnt){
            int sz = node->ch[to]->size;
            if(k <= sz){
                pair<Node*,Node*> 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);
    }
    Node *insert(Node *node, int k, T x){
        pair<Node*,Node*> P = split(node, k);
        Node *nw = new Node(x);
        return merge(merge(P.first, nw), P.second);
    }
    Node *erase(Node *node, int k){
        pair<Node*,Node*> P1, P2;
        P1 = split(node, k);
        P2 = split(P1.second, 1);
        free(P2.first);
        return merge(P1.first, P2.second);
    }
    pair<Node*, T> rangeGet(Node *node, int l, int r){
        if(node == nullptr)return make_pair(node, e);
        node = push(node);
        assert(0<=l && l<=r && r<=node->size);
        if(r-l == 0)return make_pair(node, e);
        if(r-l == node->size)return make_pair(node, 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;
                tie(node->ch[to], chval) = rangeGet(node->ch[to], l, min(r, sz));
                ret = f(ret, chval);
            }
            l = max(0, l - sz); r = max(0, r - sz);
        }
        return make_pair(node, ret);
    }
    pair<Node*, T> kth(Node *node, int k){
        return rangeGet(node, k, k+1);
    }
    Node *rangeApply(Node *node, int l, int r, F func){
        if(node == nullptr)return node;
        node = push(node);
        assert(0<=l && l<=r && r<=node->size);
        if(r-l == 0)return node;
        if(r-l == node->size)return applyFunc(node, func);
        assert(!node->isLeaf());
        REP(to, node->cnt){
            int sz = node->ch[to]->size;
            if(l<sz && r-l != 0){
                node->ch[to] = rangeApply(node->ch[to], l, min(r, sz), func);
            }
            l = max(0, l - sz); r = max(0, r - sz);
        }
        return update(node);
    }
    // template end
};

// https://atcoder.jp/contests/code-festival-2014-exhibition/tasks/code_festival_exhibition_b
int q;
char s[125252];
int a[125252];
int main(){
    scanf("%d%s",&q,s);
    int n = strlen(s);
    // initialize
    REP(i,n)a[i+1] = a[i] + (s[i]=='(' ? +1 : -1);
    using Node = Tree234::Node;
    vector<Node*> v(n+1, nullptr);
    REP(i,n+1)v[i] = new Node(a[i]);
    while(v.size() > 1){
        if(v.size()%2 == 1)v.push_back(nullptr);
        int m = v.size();
        vector<Node*> w(m/2, nullptr);
        REP(i,m/2){
            w[i] = Tree234::merge(v[2*i+0], v[2*i+1]);
        }
        swap(v, w);
    }
    Node *root = v[0];
    // query
    while(q--){
        char buf[4]; int y, z;
        scanf("%s%d%d",buf,&y,&z); --y;
        if(buf[0] == '(' || buf[0] == ')'){
            // insert
            int bef;
            tie(root, bef) = Tree234::kth(root, y);
            int diff = buf[0] == '(' ? +1 : -1;
            root = Tree234::insert(root, y+1, bef);
            root = Tree234::rangeApply(root, y+1, root->size, diff);
        }else if(buf[0] == 'D'){
            // erase
            int bef, aft;
            tie(root, bef) = Tree234::kth(root, y);
            tie(root, aft) = Tree234::kth(root, y+1);
            int diff = aft - bef;
            root = Tree234::erase(root, y+1);
            root = Tree234::rangeApply(root, y+1, root->size, -diff);
        }else{
            // query
            int minval, lft, rgt;
            tie(root, minval) = Tree234::rangeGet(root, y, z+1);
            tie(root, lft) = Tree234::kth(root, y);
            tie(root, rgt) = Tree234::kth(root, z);
            int ans = lft + rgt - 2 * minval;
            printf("%d\n",ans);
        }
    }
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:226:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%s",&q,s);
                       ^
./Main.cpp:246:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s%d%d",buf,&y,&z); --y;
                                  ^

Judge Result