結果

問題 No.2650 [Cherry 6th Tune *] セイジャク
ユーザー abap34abap34
提出日時 2024-02-23 22:53:09
言語 C++17(clang)
(17.0.6 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 1,813 bytes
コンパイル時間 3,879 ms
コンパイル使用メモリ 177,596 KB
実行使用メモリ 22,340 KB
最終ジャッジ日時 2024-02-23 22:53:39
合計ジャッジ時間 25,791 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge16
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,548 KB
testcase_01 AC 2 ms
6,548 KB
testcase_02 RE -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(a) (a).begin(), (a).end()

int searchsortedfirst(const std::vector<int> &vec, int value)
{
    int low = 0;
    int high = vec.size() - 1;
    int pos = 0;

    while (low <= high)
    {
        int mid = low + (high - low) / 2;

        if (vec[mid] == value)
        {
            return mid;
        }
        else if (vec[mid] < value)
        {
            pos = mid + 1;
            low = mid + 1;
        }
        else
        {
            pos = mid;
            high = mid - 1;
        }
    }

    return pos;
}


int main()
{
    int N, A, T;
    cin >> N >> A;

    vector<int> X(N);

    rep(i, N) cin >> X[i];

    sort(ALL(X));

    cin >> T;

    vector<vector<int>> pusht(T + 1);
    vector<vector<int>> popt(T + 1);

    vector<int> L(T);
    vector<int> R(T);

    rep(i, N) cin >> L[i] >> R[i];


    rep(t, T)
    {
        int l = L[t];
        int r = R[t];

        // Xへの挿入位置を二分探索
        int lpos = searchsortedfirst(X, l);
        int rpos = searchsortedfirst(X, r);


        assert(lpos <= rpos);
        assert(lpos >= 0);
        assert(rpos <= pusht.size());

        pusht[lpos].push_back(t + 1);
        popt[rpos].push_back(t + 1);
    }

    set<int> current;

    rep(i, N)
    {
        for (auto t : popt[i])
        {
            if (current.count(t))
            {
                current.erase(t);
            }
        }

        for (auto t : pusht[i])
        {
            current.insert(t);
        }

        if (current.size() > 0)
        {
            cout << *current.rbegin() << endl;
        }
        else
        {
            cout << -1 << endl;
        }
    }
}
0