ABC127-C Prison
https://gyazo.com/5746561965ac0d1bd53c9e0b136518ad
解法
基本的にはM個のゲート分のL. Rの重複分をカウントすればok
ただ、これをそのまま愚直にvectorとして扱ってループをかけると制約的にTLEを食らう のでちょっと工夫が必要
ゲートごとに許容されるID番号の最小値、最大値がセットされてるので、これらをヒントにM回ループを回す
その中で最小値l, 最大値rを更新
更新しきれなかったら$ 0
更新しきれたら$ r - l + 1
と出せばok
時間計算量$ O(M)
空間計算量$ O(1)
解くのにかかった時間
30分程度
コーナーケースでwaに引っかかり消耗してた
code:solution.cpp
using namespace std;
void solve(long long N, long long M, std::vector<long long> L, std::vector<long long> R){
long long l = L0, r = R0; for (int i=1; i<M; i++) {
cout << 0 << endl;
return;
}
if (r < l) {
cout << 0 << endl;
return;
}
}
cout << r - l + 1 << endl;
}
int main(){
long long N;
scanf("%lld",&N);
long long M;
scanf("%lld",&M);
std::vector<long long> L(M);
std::vector<long long> R(M);
for(int i = 0 ; i < M ; i++){
}
solve(N, M, std::move(L), std::move(R));
return 0;
}