提出 #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});
#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 | ||||
結果 |
|
|
セット名 | テストケース |
---|---|
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 |