#include <bits/stdc++.h>
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n")
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int inf = 2e09; ll infll = 2e18;
int base = 1;
struct seg{
vector<int> t;
void init(int n){
while(base < n) base <<= 1;
t.resize(base<<1);
}
void update(int i, int val){
for(i += base-1, t[i] = val, i >>= 1; i; i >>= 1) t[i] = max(t[i<<1], t[i<<1|1]);
}
int query(int i, int s, int e, int x, int y){
if(x <= s && e <= y) return t[i];
int mid = (s+e)>>1, ret = 0;
if(x <= mid) ret = max(ret, query(i<<1, s, mid, x, y));
if(mid < y) ret = max(ret, query(i<<1|1, mid+1, e, x, y));
return ret;
}
int qr(int x, int y){
if(x <= y) return query(1, 1, base, max(1, x), min(base, y));
return 0;
}
};
void answer(){
int n, d; scanf("%d%d", &n, &d);
set<int> sc;
vector<int> t(n+1);
for(int i = 1; i <= n; ++i) scanf("%d", &t[i]), sc.emplace(t[i]);
unordered_map<int, int> mp; int it = 0;
for(int u : sc) mp[u] = ++it;
for(int i = 1; i <= n; ++i) t[i] = mp[t[i]];
seg seg; seg.init(n+1);
for(int i = 1; i < n; ++i) seg.update(t[i], seg.qr(1, t[i]-1)+1);
printf("%d\n", max(seg.qr(1, t[n]-1)+1, seg.qr(t[n], base)));
}
int main(){
int T = 1;
for(++T; --T; ) answer();
return 0;
}
Compilation message
Main.cpp: In function 'void answer()':
Main.cpp:34:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | int n, d; scanf("%d%d", &n, &d);
| ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:37:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
37 | for(int i = 1; i <= n; ++i) scanf("%d", &t[i]), sc.emplace(t[i]);
| ~~~~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
71 ms |
8532 KB |
Output is correct |
2 |
Correct |
80 ms |
8272 KB |
Output is correct |
3 |
Incorrect |
99 ms |
8624 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
8924 KB |
Output is correct |
2 |
Correct |
95 ms |
8528 KB |
Output is correct |
3 |
Correct |
102 ms |
8932 KB |
Output is correct |
4 |
Correct |
314 ms |
34748 KB |
Output is correct |
5 |
Correct |
324 ms |
34844 KB |
Output is correct |
6 |
Correct |
387 ms |
34848 KB |
Output is correct |
7 |
Correct |
166 ms |
34620 KB |
Output is correct |
8 |
Correct |
151 ms |
34784 KB |
Output is correct |
9 |
Correct |
197 ms |
34508 KB |
Output is correct |
10 |
Correct |
263 ms |
34756 KB |
Output is correct |
11 |
Correct |
311 ms |
34600 KB |
Output is correct |
12 |
Correct |
328 ms |
34664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |