回答編集履歴
1
補足
answer
CHANGED
|
@@ -23,4 +23,28 @@
|
|
|
23
23
|
```
|
|
24
24
|
ここがO(M)になるので時間制限上厳しいでしょう。
|
|
25
25
|
|
|
26
|
-
そのほかにも配列の範囲外へのアクセスがあるのと、M回を超えて握手する可能性があります(done > M)。テストケースによってはWAになるでしょう。
|
|
26
|
+
そのほかにも配列の範囲外へのアクセスがあるのと、M回を超えて握手する可能性があります(done > M)。テストケースによってはWAになるでしょう。
|
|
27
|
+
|
|
28
|
+
---
|
|
29
|
+
参考コードとの比較
|
|
30
|
+
```C++
|
|
31
|
+
int itr=0;
|
|
32
|
+
for(int i=N-1;i>=0;i--){
|
|
33
|
+
while(itr<N&&A[i]+A[itr]>=lim){
|
|
34
|
+
itr++;
|
|
35
|
+
}
|
|
36
|
+
res+=itr;
|
|
37
|
+
}
|
|
38
|
+
```
|
|
39
|
+
こちらのコードの場合、itrの初期化位置がforループの外なので、次のiの計算でも前のitrがそのまま残った状態です。itrは増える一方で、最大Nまでインクリメントされるだけなので、whileループの中は高々N回しか呼ばれません。結果計算量はO(N)になります。
|
|
40
|
+
|
|
41
|
+
```C++
|
|
42
|
+
ll itr=0;
|
|
43
|
+
ll num=0;
|
|
44
|
+
for(int i=N-1;i>=0;i--){
|
|
45
|
+
while(itr<N && A[i]+A[itr]>=ok) itr++;
|
|
46
|
+
ans+=A[i]*itr+sum[itr];
|
|
47
|
+
num+=itr;
|
|
48
|
+
}
|
|
49
|
+
```
|
|
50
|
+
こちらも同様にitrがインクリメントされるのは高々N回なのでO(N)です。
|