結果

問題 No.2650 [Cherry 6th Tune *] セイジャク
コンテスト
ユーザー abap34
提出日時 2024-02-23 22:52:13
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 1,747 bytes
コンパイル時間 4,311 ms
コンパイル使用メモリ 180,096 KB
実行使用メモリ 22,316 KB
最終ジャッジ日時 2024-09-29 08:04:43
合計ジャッジ時間 26,410 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other WA * 29 RE * 2
権限があれば一括ダウンロードができます

ソースコード

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])
        {
            current.erase(t);
        }

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

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