-1

問題11402- UVa Online JudgeのAhoy Piratesを解決しようとしています。このコードは、指定された情報に基づいてセグメント ツリーを構築し、更新またはクエリ操作を実行することになっています。私の C++ コードは私のシステムで正常に動作します。しかし、送信時に実行時エラーが発生します。私の配列サイズは最大 3000000 要素になる可能性があるため、そのような大きなサイズの配列が実行時エラーを引き起こす可能性があるのではないかと心配しています。何か案は？

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

using namespace std;
typedef long long ll;

struct Node{
    char upd;
    // 0 - Buccaneer pirates
    // 1 - Barbary pirates
    int p[2];
    Node(){
        p[0] = 0;
    p[1] = 0;
        upd = ' ';
    }
    void update(char cmd){
        if (cmd == 'I'){
            switch(upd){
                case ' ': upd = 'I';break;
                case 'I': upd = ' ';break;
                case 'E': upd = 'F';break;
                case 'F': upd = 'E';break;
            }
        }
        else if (cmd != ' '){
            upd = cmd;
        }
    }
    void S(){
        int temp;
        switch(upd){
            case 'I': temp=p[0]; p[0]=p[1]; p[1]=temp; break;
            case 'E': p[1]+=p[0]; p[0]=0; break;
            case 'F': p[0]+=p[1]; p[1]=0; break;
        }
        upd = ' ';
    }
};

Node tree[4028000];
char pirates[1024010];

void buildTree(int index, int i, int j){
    if (i>j)
        return;
    if (i==j){
        if (pirates[i] == '0'){
            tree[index].p[1] = 1;
            tree[index].p[0] = 0;
        }
        else{
            tree[index].p[0] = 1;
            tree[index].p[1] = 0;
        }
        tree[index].upd = ' ';
        return;
    }
    int mid = (i+j)/2;
    buildTree(2*index+1,i,mid);
    buildTree(2*index+2,mid+1,j);
    tree[index].p[0] = tree[2*index+1].p[0] + tree[2*index+2].p[0];
    tree[index].p[1] = tree[2*index+1].p[1] + tree[2*index+2].p[1];
    tree[index].upd = ' ';
}

void update(int index,int i,int j,int l,int r,char c){
    if (i == l && j == r){
        tree[index].update(c);
    }
    tree[2*index+1].update(tree[index].upd);
    tree[2*index+2].update(tree[index].upd);
    tree[index].S();
    if (i == l && j ==r)
        return;
    if (l>j || r<i || l > r)
        return;
    int mid = (i+j)/2;
    update(2*index+1,i,mid,l,min(r,mid),c);
    update(2*index+2,mid+1,j,max(l,mid+1),r,c);
    tree[index].p[0] = tree[2*index+1].p[0] + tree[2*index+2].p[0];
    tree[index].p[1] = tree[2*index+1].p[1] + tree[2*index+2].p[1];
}

int query(int index,int i,int j,int l,int r){
    if (l>j || r<i)
        return 0;
    tree[2*index+1].update(tree[index].upd);
    tree[2*index+2].update(tree[index].upd);
    tree[index].S();
    if (i == l && j == r){
        return tree[index].p[0];
    }
    int mid = (i+j)/2;
    int b1 = query(2*index+1,i,mid,l,min(mid,r));
    int b2 = query(2*index+2,mid+1,j,max(mid+1,l),r);
    return b1+b2;
}

int main(void){
    int t;
    scanf("%d",&t);
    for(int z=0; z<t; z++){
        int m,len=0,T,q,querycnt=1;
        char str[64];
        scanf("%d",&m);
        for(int i=0; i<m; i++){
            scanf("%d %s",&T,str);
            for(int j=0; j<T; j++){
                int length = strlen(str);
                for(int k=0; k<length; k++){
                    pirates[len] = str[k];
                    len++;
                }
            }
        }
        buildTree(0,0,len-1);
    scanf("%d",&q);
        printf("Case %d:\n",z+1);
        for(int i=0; i<q; i++){
            char cmd;
            int l,r;
        scanf(" %c %d %d", &cmd, &l, &r);
            if (cmd == 'S'){
                int ans = query(0,0,len-1,l,r);
                printf("Q%d: %d\n",querycnt++,ans);
            }
            else{
                update(0,0,len-1,l,r,cmd);
            }
        }
    }
    return 0;
}
4

1 に答える 1

1

ソリューションの問題は、次の 2 つのステートメントにあります。

tree[2*index+1].update(tree[index].upd);
tree[2*index+2].update(tree[index].upd);

上記の両方のステートメントで、配列ツリーのインデックスは最大 2*(2*N+1) (オーバーフロー操作) に達する可能性があります。ここで、N は入力の最大サイズです。上記の質問では、N = 1024000 です。配列ツリーのサイズは 4*N 未満であるため、巨大な入力の場合、プログラムはセグメンテーション フォールトを生成します。上記の問題の解決策は、配列にアクセスする前にインデックスの境界をチェックするか、すべてのオーバーフロー更新操作を処理するのに十分な大きさの配列にすることです。

于 2012-09-30T16:02:06.287 に答える