Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- struct SegmTree {
- vi t;
- int sz;
- SegmTree(int n = 0) {
- sz = 1;
- while (sz < n) sz *= 2;
- t.assign(sz * 2, 0);
- }
- void put(int pos, int val) {
- int v = sz + pos;
- t[v] = max(t[v], val);
- v >>= 1;
- while (v) {
- t[v] = max(t[v * 2], t[v * 2 + 1]);
- v >>= 1;
- }
- }
- int get_max(int l, int r) {
- l += sz;
- r += sz;
- int res = 0;
- while (l <= r) {
- res = max(res, t[l]);
- res = max(res, t[r]);
- l = (l + 1) >> 1;
- r = (r - 1) >> 1;
- }
- return res;
- }
- };
- int n;
- vi a;
- bool read() {
- if (scanf("%d", &n) < 1) {
- return 0;
- }
- a.resize(n);
- forn(i, n) {
- scanf("%d", &a[i]);
- }
- return 1;
- }
- const int MAXN = 1e5 + 10;
- int solve() {
- SegmTree dp1(MAXN);
- SegmTree dp2(MAXN);
- forn(i, n) {
- int d1 = dp2.get_max(0, a[i] - 1) + 1;
- dp1.put(a[i], d1);
- int d2 = dp1.get_max(a[i] + 1, MAXN - 1) + 1;
- dp2.put(a[i], d2);
- }
- return max(dp1.get_max(0, MAXN - 1), dp2.get_max(0, MAXN - 1));
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement