提出 #62801799


ソースコード 拡げる

Copy
#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
#define pii array<int,2>
#define endl "\n"
void solve() {
int n,q;
cin >> n >> q;
vector<int> a(n+9);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
vector<array<int,3>> Q;
for (int i = 1; i <= q; i++) {
int r,x;
cin >> r >> x;
Q.push_back({r,x,i});
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#include <bits/stdc++.h>
using namespace std;

#define ull unsigned long long
#define ll long long
#define pii array<int,2>
#define endl "\n"

void solve() {
    int n,q;
    cin >> n >> q;
    vector<int> a(n+9);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    vector<array<int,3>> Q;
    for (int i = 1; i <= q; i++) {
        int r,x;
        cin >> r >> x;
        Q.push_back({r,x,i});
    }

    sort(Q.begin(),Q.end());
    vector<int> ans(q+9);
    vector<int> stk;
    int i = 0;
    for (auto [r,x,id] : Q) {
        while (i < r) {
            i++;
            auto it = lower_bound(stk.begin(),stk.end(),a[i]);
            if (it == stk.end()) stk.push_back(a[i]);
            else *it = a[i];
        }
        ans[id] = upper_bound(stk.begin(),stk.end(),x)-stk.begin();
    }
    for (int i = 1; i <= q; i++) cout << ans[i] << endl;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    for (int i = 0; i < t; i++) {
        solve();
    }
    return 0;
}

提出情報

提出日時
問題 F - Prefix LIS Query
ユーザ CirnoNine
言語 C++ 23 (gcc 12.2)
得点 500
コード長 1082 Byte
結果 AC
実行時間 78 ms
メモリ 8912 KB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 500 / 500
結果
AC × 2
AC × 37
セット名 テストケース
Sample 00_sample_00.txt, 00_sample_01.txt
All 00_sample_00.txt, 00_sample_01.txt, 01_random_00.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 02_random2_00.txt, 02_random2_01.txt, 02_random2_02.txt, 02_random2_03.txt, 02_random2_04.txt, 03_random3_00.txt, 03_random3_01.txt, 03_random3_02.txt, 03_random3_03.txt, 03_random3_04.txt, 03_random3_05.txt, 03_random3_06.txt, 03_random3_07.txt, 03_random3_08.txt, 03_random3_09.txt, 04_handmade_00.txt, 04_handmade_01.txt, 04_handmade_02.txt, 04_handmade_03.txt, 04_handmade_04.txt
ケース名 結果 実行時間 メモリ
00_sample_00.txt AC 1 ms 3456 KB
00_sample_01.txt AC 1 ms 3532 KB
01_random_00.txt AC 1 ms 3540 KB
01_random_01.txt AC 43 ms 6264 KB
01_random_02.txt AC 12 ms 3852 KB
01_random_03.txt AC 18 ms 4268 KB
01_random_04.txt AC 34 ms 5152 KB
01_random_05.txt AC 44 ms 6380 KB
01_random_06.txt AC 75 ms 7100 KB
01_random_07.txt AC 75 ms 7044 KB
01_random_08.txt AC 75 ms 7180 KB
01_random_09.txt AC 75 ms 7016 KB
01_random_10.txt AC 75 ms 7044 KB
01_random_11.txt AC 78 ms 6984 KB
01_random_12.txt AC 75 ms 6936 KB
01_random_13.txt AC 76 ms 7008 KB
01_random_14.txt AC 77 ms 7012 KB
02_random2_00.txt AC 63 ms 6984 KB
02_random2_01.txt AC 66 ms 7048 KB
02_random2_02.txt AC 70 ms 6968 KB
02_random2_03.txt AC 70 ms 7008 KB
02_random2_04.txt AC 73 ms 6964 KB
03_random3_00.txt AC 74 ms 8792 KB
03_random3_01.txt AC 58 ms 7084 KB
03_random3_02.txt AC 74 ms 8824 KB
03_random3_03.txt AC 59 ms 7076 KB
03_random3_04.txt AC 74 ms 8868 KB
03_random3_05.txt AC 62 ms 7000 KB
03_random3_06.txt AC 75 ms 8912 KB
03_random3_07.txt AC 64 ms 7056 KB
03_random3_08.txt AC 74 ms 8752 KB
03_random3_09.txt AC 67 ms 6932 KB
04_handmade_00.txt AC 58 ms 7048 KB
04_handmade_01.txt AC 60 ms 8792 KB
04_handmade_02.txt AC 54 ms 7004 KB
04_handmade_03.txt AC 44 ms 7008 KB
04_handmade_04.txt AC 60 ms 8904 KB


2025-03-15 (土)
04:32:59 +00:00