oj.uz

Submission #132959

# Submission time Handle Problem Language Result Execution time Memory
132959 2019-07-20T02:49:30 Z silxikys Global Warming (CEOI18_glo) C++14
100 / 100
 923 ms 256608 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 2e5+5;
int n, x;

struct SegDyn
{
	int s, e, m; //represents range [s,e]
	SegDyn *l, *r;
    int maxi;
	SegDyn(int _s, int _e) {
		s = _s;
		e = _e;
		m = (s+e)/2;
		l = NULL;
		r = NULL;
        maxi = 0;
	}

	void prepareL() { if (l == NULL) l = new SegDyn(s,m); }
	void prepareR() { if (r == NULL) r = new SegDyn(m+1,e); }

	void pull() {
        maxi = 0;
        if (l) maxi = max(maxi,l->maxi);
        if (r) maxi = max(maxi,r->maxi);
	}

	void add(int idx, int del) { //a[idx] += del
		//cout << s << ' ' << e << '\n';
		if (s == e && s == idx) {
			//at the node, stop
            maxi = max(maxi,del);
			return;
		}
		if (idx <= m) {
			prepareL();
			l->add(idx,del);
		}
		else {
			prepareR();
			r->add(idx,del);
		}
		pull(); //updates current node based on the children
	}

    int getmaxi(int se, int en) {
		if (se <= s && e <= en) return maxi;
		int res = 0;
		if (l && se <= m) res = max(res,l->getmaxi(se,en));
		if (r && en > m) res = max(res,r->getmaxi(se,en));
		return res;	
	}
};

int a[maxn];
int f[maxn], b[maxn];

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> x;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    SegDyn *fwd = new SegDyn(0,1e9+1);
    SegDyn *bck = new SegDyn(0,1e9+1);
    for (int i = 1; i <= n; i++) {
        int m = fwd->getmaxi(0,a[i]-1) + 1;    
        f[i] = m;
        fwd->add(a[i],m);
    }
    int ans = 0;
    for (int i = n; i >= 1; i--) {
        int curr = f[i];
        int added = bck->getmaxi(max(1,a[i]+1-x),1e9+1);
        ans = max(ans,curr+added);
        //cout << i << ": " << curr << ' ' << added << '\n';
        int m = bck->getmaxi(a[i]+1,1e9+1) + 1;
        b[i] = m;
        bck->add(a[i],m);
    }
    cout << ans << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 372 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 372 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 380 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 372 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 380 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 6 ms 2424 KB Output is correct
20 Correct 6 ms 2424 KB Output is correct
21 Correct 6 ms 2296 KB Output is correct
22 Correct 6 ms 2296 KB Output is correct
23 Correct 5 ms 1404 KB Output is correct
24 Correct 5 ms 1400 KB Output is correct
25 Correct 3 ms 504 KB Output is correct
26 Correct 4 ms 504 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 902 ms 256396 KB Output is correct
2 Correct 894 ms 256532 KB Output is correct
3 Correct 906 ms 256504 KB Output is correct
4 Correct 903 ms 256608 KB Output is correct
5 Correct 419 ms 139200 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 73764 KB Output is correct
2 Correct 210 ms 73728 KB Output is correct
3 Correct 233 ms 73756 KB Output is correct
4 Correct 112 ms 39772 KB Output is correct
5 Correct 2 ms 424 KB Output is correct
6 Correct 82 ms 8312 KB Output is correct
7 Correct 153 ms 52856 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 137892 KB Output is correct
2 Correct 442 ms 137860 KB Output is correct
3 Correct 923 ms 256568 KB Output is correct
4 Correct 427 ms 139152 KB Output is correct
5 Correct 155 ms 20856 KB Output is correct
6 Correct 309 ms 39436 KB Output is correct
7 Correct 249 ms 40292 KB Output is correct
8 Correct 305 ms 99164 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 372 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 380 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 6 ms 2424 KB Output is correct
20 Correct 6 ms 2424 KB Output is correct
21 Correct 6 ms 2296 KB Output is correct
22 Correct 6 ms 2296 KB Output is correct
23 Correct 5 ms 1404 KB Output is correct
24 Correct 5 ms 1400 KB Output is correct
25 Correct 3 ms 504 KB Output is correct
26 Correct 4 ms 504 KB Output is correct
27 Correct 902 ms 256396 KB Output is correct
28 Correct 894 ms 256532 KB Output is correct
29 Correct 906 ms 256504 KB Output is correct
30 Correct 903 ms 256608 KB Output is correct
31 Correct 419 ms 139200 KB Output is correct
32 Correct 212 ms 73764 KB Output is correct
33 Correct 210 ms 73728 KB Output is correct
34 Correct 233 ms 73756 KB Output is correct
35 Correct 112 ms 39772 KB Output is correct
36 Correct 2 ms 424 KB Output is correct
37 Correct 82 ms 8312 KB Output is correct
38 Correct 153 ms 52856 KB Output is correct
39 Correct 444 ms 137892 KB Output is correct
40 Correct 442 ms 137860 KB Output is correct
41 Correct 923 ms 256568 KB Output is correct
42 Correct 427 ms 139152 KB Output is correct
43 Correct 155 ms 20856 KB Output is correct
44 Correct 309 ms 39436 KB Output is correct
45 Correct 249 ms 40292 KB Output is correct
46 Correct 305 ms 99164 KB Output is correct
47 Correct 455 ms 137800 KB Output is correct
48 Correct 426 ms 137848 KB Output is correct
49 Correct 910 ms 256452 KB Output is correct
50 Correct 425 ms 139132 KB Output is correct
51 Correct 225 ms 21752 KB Output is correct
52 Correct 339 ms 41620 KB Output is correct
53 Correct 328 ms 41664 KB Output is correct
54 Correct 260 ms 42232 KB Output is correct
55 Correct 652 ms 185324 KB Output is correct