Codeforces #1485B Replace and Keep Sorted

문제

https://codeforces.com/problemset/problem/1485/B

걸린 시간

- 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q, k;
    cin >> n >> q >> k;
    vector<int> a(n+2);
    for(int i = 1; i < n+1; i++){
        cin >> a[i];
    }
    a[0] = 1;
    a[n+1] = k;
    vector<ll> left(n+1), right(n+1);
    for(int i = 1; i < n+1; i++){
        left[i] = (a[i+1]-1)-1;
        right[i] = (k-a[i-1])-1;
    }
    vector<ll> m(n+1, 0);
    for(int i = 2; i <= n-1; i++){
        m[i] = (a[i+1]-a[i-1]-1)-1;
    }
    for(int i = 3; i <= n-1; i++){
        m[i] += m[i-1];
    }
    int l, r;
    for(int i = 0; i < q; i++){
        cin >> l >> r;
        if(l == r){
            cout << k-1 << "\n";
        }
        else if(l < r){
            int s = l+1;
            int e = r-1;
            cout << left[l] + right[r] + (m[e]-m[s-1]) << "\n";
        }
    }
    return 0;
}

l == r 인 경우의 처리를 해 주지 않아서 틀린 문제이다. 문제의 예제 입력에서는 연속된 3개의 a 중간값이었기 때문에 문제가 없었다. 출제자가 이 부분을 노린걸까?

디시 ps 갤러리에 질문글을 올려서 겨우 반례를 찾았다..

참고

• CF 701 B 번 문제풀이좀 도와주세요.. [늅]