ソースコード 拡げる

Copy
```#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 {
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
};

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;
}
```

提出情報

提出日時 2020-01-21 03:20:25+0900 B - カッコつけ rickytheta C++14 (GCC 5.4.1) 100 9284 Byte AC 298 ms 13280 KB

コンパイルエラー

```./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;
^
```

ジャッジ結果

セット名 Sample All

 AC × 38
セット名 テストケース
Sample
ケース名 結果 実行時間 メモリ
subtask1_01.txt AC 5 ms 512 KB
subtask1_02.txt AC 4 ms 512 KB
subtask1_03.txt AC 5 ms 384 KB
subtask1_04.txt AC 4 ms 640 KB
subtask1_05.txt AC 6 ms 512 KB
subtask1_06.txt AC 5 ms 640 KB
subtask1_07.txt AC 3 ms 384 KB
subtask1_08.txt AC 3 ms 640 KB
subtask1_09.txt AC 4 ms 384 KB
subtask1_10.txt AC 3 ms 384 KB
subtask1_11.txt AC 3 ms 384 KB
subtask1_12.txt AC 6 ms 512 KB
subtask1_13.txt AC 4 ms 640 KB
subtask1_14.txt AC 4 ms 384 KB
subtask1_15.txt AC 7 ms 640 KB
subtask1_16.txt AC 7 ms 640 KB
subtask1_17.txt AC 7 ms 640 KB
subtask1_18.txt AC 7 ms 640 KB
subtask1_19.txt AC 7 ms 640 KB
subtask2_01.txt AC 134 ms 12368 KB
subtask2_02.txt AC 116 ms 2176 KB
subtask2_03.txt AC 196 ms 10240 KB
subtask2_04.txt AC 130 ms 7456 KB
subtask2_05.txt AC 27 ms 6992 KB
subtask2_06.txt AC 66 ms 1408 KB
subtask2_07.txt AC 56 ms 5512 KB
subtask2_08.txt AC 39 ms 10192 KB
subtask2_09.txt AC 155 ms 4416 KB
subtask2_10.txt AC 131 ms 11904 KB
subtask2_11.txt AC 183 ms 7904 KB
subtask2_12.txt AC 265 ms 8328 KB
subtask2_13.txt AC 65 ms 5420 KB
subtask2_14.txt AC 233 ms 6456 KB
subtask2_15.txt AC 293 ms 13280 KB
subtask2_16.txt AC 294 ms 13280 KB
subtask2_17.txt AC 298 ms 13280 KB
subtask2_18.txt AC 295 ms 13280 KB
subtask2_19.txt AC 297 ms 13280 KB