Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- int N, v[100005], P[100005], Q[100005], cnt;
- int main(void)
- {
- int i, l, r, m, x;
- freopen("sclm2.in", "r", stdin);
- freopen("sclm2.out", "w", stdout);
- scanf("%d", &N);
- for (i = 1; i <= N; ++i)
- scanf("%d", &v[i]);
- for (i = 1; i <= N; ++i)
- {
- if (v[i] >= P[cnt])
- P[++cnt] = v[i], Q[i] = cnt;
- else
- {
- for (l = 1, r = cnt, x = cnt; l <= r; )
- {
- m = (l + r) / 2;
- if (P[m] <= v[i]) l=m+1;
- else x = m, r=m-1;
- }
- P[x] = v[i]; Q[i] = x;
- }
- }
- printf("%d\n", cnt);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement