サンプルコードは正解するのに提出したら実行時エラーと表示される。

Question

##問題
長さ L メートルの直線状の木材があります。
x=1,2,…,L−1 に対して、木材の左端から x メートルの地点には目印として線 x が引かれています。
Q 個のクエリが与えられます。 i 番目のクエリは数の組 (c i,x i ) によって表されます。
以下の説明に従ってクエリを i の昇順に処理してください。
c i=1 のとき : 線 x iがある地点で木材を 2 つに切る。
c i=2 のとき : 線 x iを含む木材を選び、その長さを出力する。
ただし c i=1,2 の両方に対して、線 x iはクエリを処理する時点で切られていないことが保証されます。
問題の詳細はhttps://atcoder.jp/contests/abc217/tasks/abc217_dを参照してください。
###回答の考え方
長さL+1の配列を用意して0,1,・・・,Lとし(はじを0,Lとする)各配列に自分を含む木材の左端と右端を記録させて最終的に右端ー左端で長さを出しています。
###問題点
この問題で以下のコードを作成したのですが、サンプル問題は正解したもののいざ提出してみると実行時エラーと表示されました。自分なりに調べても、今回0で割ったりとかはしていないのでほんとに理由がわかりません。
事実上ののデバック依頼みたいな形で本当に申しわけないのですが、ぜひよろしくお願いいたします。
###code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	int L, Q;
	cin >> L >> Q;
	vector<int> c(Q), x(Q);
	vector<pair<int, int>> ans(L+1,make_pair(0,L));
	for (int i = 0;i < Q;i++) {
		cin >> c.at(i) >> x.at(i);
	}
	for (int i = 0;i < Q;i++) {
		if (c.at(i) == 1) {
			for (int j = 0;j < x.at(i);j++) {
				ans.at(j).second = min(ans.at(j).second, x.at(i));
			}
			for (int j = x.at(i)+1;j < L + 1;j++) {
				ans.at(j).first = max(ans.at(j).first, x.at(i));
			}
		}
		else {
			cout << ans.at(x.at(i)).second - ans.at(x.at(i)).first << endl;
		}
	}
}

Comments

[Orlofsky]

URLは https://teratail.com/help/question-tips#questionTips3-7 の [リンク] で [リンク先の説明](http...) に修正してください。

Answer 1

make_pair が内部的にどういうメモリ確保をしているか存じ上げませんが、
少なくとも、

ans.at(j).first で 4byte(int)
ans.at(j).second で 4byte(int)

1要素で少なくとも8byteは使っていて、j は 0 から L-1 までの L個ということですので、
L=10^9 のとき、

8 [Byte] × 10^9 / 1024[Byte/KByte] / 1024[KByte/MByte] / 1024[MByte/GByte] ≒ 7.45GB > 1GB

（ん、合ってる？）
でメモリが足りていないと思います。

切っていないのに、1m 毎に要素を持つ、というデータの持ち方では、
解けない問題なんだろうと思います。

Comments

[IkeuchiKenyu]

ありがとうございます。これからも精進していきます。

Answer 2

Lは最大 10^9、Qは最大 2×10^5 という非常に大きな数字が想定されています。
int 型で表せる範囲を超えています。ビット数が足りません。

提出後、このような大きな入力データでもチェックされますので、
通らなかったと思われます。

Comments

[actorbug]

たいていの環境では、int は 32bit で最大 2147483647 までの数を表現できるので、10^9 なら一応 int で表現できるはずです。

[ak.n]

失礼しました。短絡的に回答してすみません。ビット数は足りていました・・・
L に 10^9 を与えると

vector<pair<int, int>> ans(L+1,make_pair(0,L));

で実行時エラー（paiza.ioで試行）

入力
1000000000 1
2 1

[ak.n]

1000000000 = 10^9 NG
100000000 = 10^8 OK
actorbug さんが正しく、L, Q のビット数の問題ではなく、
メモリ確保の問題かと思います。メモリの制限は幾つでしたかね。

[IkeuchiKenyu]

問題では1024 MBでした。