Atcoder ABC 217(今日の問題) のＤ問題

Question

今日のAtcoderコンテストでD問題がAＣできませんでした、、。初めてＤ問題まで来たので悔しいです。条件通りの変数データ保持量になってるんですが、ＴＬＥになってしまいます。ですが、ＴＬＥ以外はＡＣしています。
https://atcoder.jp/contests/abc217/tasks/abc217_d
どなたかわかる方がいたらご教授お願いします。

#include<stdio.h>
int main(void){
	long long int q,c[20000000],x[20000000],min=0,min2=0,dai,tiisai,i,j;
	long long int l;
	scanf("%lld",&l);
	scanf("%lld",&q);
	for(i=1;i<=q;i++){
		scanf("%lld",&c[i]);
		scanf("%lld",&x[i]);
	}
        min=l;
        min2=l;
	x[0]=l;
	for(i=1;i<=q;i++){
		if(c[i]==2){
		for(j=0;j<i;j++){
			if(x[i]<x[j]&&min>x[j]-x[i]){
				min=x[j]-x[i];
				dai=x[j];
			}
			if(x[i]>x[j]&&min2>x[i]-x[j]){
				min2=x[i]-x[j];
				tiisai=x[j];
			}
		}
		printf("%lld\n",dai-tiisai);
		min=l;
		min2=l;
		x[i]=0;
           　　 dai=0;
         　　　 tiisai=0;
		}
		
	}
	return 0;
}

Comments

[actorbug]

何が知りたいのでしょうか。
TLEになる理由でしょうか。それとも、TLEを修正する方法でしょうか。
TLEになる理由は計算量がO(Q^2)だからですし、TLEを修正する方法は公式解説を見ればわかるでしょう。

[schoolstudent]

知りたいのはTLEを修正する方法ですね、、。公式解説のアドバイスありがとうございます！ですが、公式解説はC++で行われているためよくわからないと言いますか、私の知識不足で申し訳ないです、、。良ければCでの解決方法を教えていただけますか？

[jimbe]

それまでのxを保存し、次のxに最も近い前後の位置を"高速に"取り出せる機能が必要だ、と当たり前のことを言っている解説に思います。
C++なら使えるモノがあるのでこう書けるというだけです。
無ければ「平衡二分探索木やB-Tree」と呼ばれるものがお勧めという感じでしょうか。

[actorbug]

正直、「平衡二分探索木やB-Tree」をC言語で実装するのは大変ですし、
検索してもすぐに使える実装は見当たらないので、こちらの方針での解決は難しいと思います。
他の人のC言語での回答を見るという手はありますが、私では解説できそうにありません。
https://atcoder.jp/contests/abc217/submissions?f.Task=abc217_d&f.LanguageName=C&f.Status=AC&f.User=

[actorbug]

上記リンク先の一番下のソースは、「座標圧縮」と「セグメント木」が理解できれば、読めると思います。

[actorbug]

試しにB-Treeで実装したところ、そこまで大変ではありませんでした(90行)。
「平衡二分探索木やB-Tree」について調べて、実装してみてはいかがでしょうか。
上記リンク先に、私のB-Treeによる作例や、他の方の平衡二分探索木による作例が追加されてるので、必要であれば参照してみてください。

[schoolstudent]

大変、時間が空いてしまい申し訳ありませんでした、、。jimbeさん、actorbugさん回答ありがとうございます。actorbugさん、わざわざコードを書いてくださり、ありがとうございます。まだまだプログラミング能力は未熟だと身に沁みました。平衡二分探索木について全く知らなかったので、コードを確認しながら理解するとともに、身に付けていきたいと思います。
ぜひ、actorbugさんをベストアンサーにしたいのですが、ここに書いてくださったと同様に、URLを添付して回答していただけないでしょうか？お手数おかけします。

Answer 1

TLEを修正する方法については、公式解説を参照してください。

また、C言語でACとなった回答については、以下のリンク先で確認することができます。

https://atcoder.jp/contests/abc217/submissions?f.Task=abc217_d&f.LanguageName=C&f.Status=AC&f.User=

上記リンク先に、私のB-Treeによる作例や、他の方の平衡二分探索木による作例が追加されているので、必要であれば参照してみてください。

Answer 2

C で書いてみました。単純なコードなので、時間制限に引っかかるかもしれません。

#include <stdio.h>  // scanf, printf

int search(int v[], int n, int x)
{
	int a = 0, b = n - 1;
	while (a <= b) {
		int m = (a + b) / 2;
		if (x < v[m]) b = m - 1;
		else a = m + 1;
	}
	return a;
}

int main(void)
{
	static int v[200002];
	v[0] = 0;
	int q, c, x, n = 2;
	scanf("%d%d", &v[1], &q);
	while (--q >= 0) {
		scanf("%d%d", &c, &x);
		int i = search(v, n, x);
		if (c == 1) {
			for (int j = n++; j > i; j--) v[j] = v[j-1];
			v[i] = x;
		}
		else printf("%d\n", v[i] - v[i-1]);
	}
}

これのどこが分からないのかをコメントしてください。

Comments

[actorbug]

残念ながら、同様のコードで時間制限に引っ掛かった事例があります。
https://atcoder.jp/contests/abc217/submissions/25615574