oj.uz

Submission #626119

# Submission time Handle Problem Language Result Execution time Memory
626119 2022-08-11T08:40:33 Z nigus Radio Towers (IOI22_towers) C++17
44 / 100
 4000 ms 39884 KB 
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

const ll big = 1000000007;
const int MAXN = 100001;
int n;
vi H2;

struct Segtree {
	Segtree *l = 0, *r = 0;
	int lo, hi, ma = -big, mi = big, ab = 0, ba = 0;
    vi V = {};
	Segtree(vi& v, int lo, int hi) : lo(lo), hi(hi) {
		if (lo + 1 < hi) {
			int mid = lo + (hi - lo)/2;
			l = new Segtree(v, lo, mid); r = new Segtree(v, mid, hi);
			ma = max(l->ma, r->ma);
            mi = min(l->mi, r->mi);
            ab = max(l->ab, r->ab);
            ab = max(ab, (r->ma) - (l->mi));
            ba = max(l->ba, r->ba);
            ba = max(ba, (l->ma) - (r->mi));
		}
		else{
            ma = v[lo];
            mi = v[lo];
        }
	}
    void setup(vi &v){
        if(lo + 1 < hi){
            l->setup(v);
            r->setup(v);
            int x = 0;
            int y = 0;
            while(x < sz(l->V) || y < sz(r->V)){
                if(y == sz(r->V) || (x < sz(l->V) && l->V[x] >= r->V[y])){
                    V.push_back(l->V[x]);
                    x++;
                }
                else{
                    V.push_back(r->V[y]);
                    y++;
                }
            }

        }
        else{
            if(v[lo] > 0){V = {v[lo]};}
        }
    }
	int get_max(int L, int R) {
		if (R <= lo || hi <= L) return -big;
		if (L <= lo && hi <= R) return ma;
		return max(l->get_max(L, R), r->get_max(L, R));
	}
    int get_min(int L, int R) {
		if (R <= lo || hi <= L) return big;
		if (L <= lo && hi <= R) return mi;
		return min(l->get_min(L, R), r->get_min(L, R));
	}
    int get_ab(int L, int R){
        if (R <= lo || hi <= L) return 0;
		if (L <= lo && hi <= R) return ab;

        int x = l->get_min(L,R);
        int y = r->get_max(L,R);
        int res = y-x;

        if(res < r->ab){
            res = max(res, r->get_ab(L, R));
        }
        if(res < l->ab){
            res = max(res, l->get_ab(L, R));
        }

        return res;
    }
    int get_ba(int L, int R){
        if (R <= lo || hi <= L) return 0;
		if (L <= lo && hi <= R) return ba;

        int x = r->get_min(L,R);
        int y = l->get_max(L,R);
        int res = y-x;

        if(res < r->ba){
            res = max(res, r->get_ba(L, R));
        }
        if(res < l->ba){
            res = max(res, l->get_ba(L, R));
        }

        return res;
    }
    int geq(int L, int R, int D){
        if (R <= lo || hi <= L) return 0;
        if (L <= lo && hi <= R){
            int lo = 0;
            int hi = sz(V);
            if(sz(V) == 0)return 0;
            if(V[0] < D)return 0;
            while(lo < hi-1){
                int mid = (lo + hi) / 2;
                if(V[mid] < D){
                    hi = mid;
                }
                else{
                    lo = mid;
                }
            }
            return hi;
        }
        return (l->geq(L, R, D)) + (r->geq(L, R, D));
    }
};

Segtree *ST;

map<int,int> HI;

vi delta;

vi ind;

void get_ct(int L, int R){
    if(L >= R)return;
    if(L == R-1){
        delta[L] = 0;
        return;
    }
    int i = HI[ST->get_max(L, R)];
    int x = ST->get_min(L,i);
    int y = ST->get_min(i+1,R);
    delta[i] = H2[i]-max(x, y);
    delta[i] = max(delta[i], 0);
    get_ct(L, i);
    get_ct(i+1,R);
}

bool comp(int i, int j){
    return delta[i] > delta[j];
}

void init(int N, vi H){
    n = N;
    rep(c1,0,n){
        H2.push_back(H[c1]);
        HI[H[c1]] = c1;
        ind.push_back(c1);
        delta.push_back(0);
    }
    ST = new Segtree(H2, 0, n);
    get_ct(0, n);
    sort(all(ind), comp);
    ST->setup(delta);
}

unordered_map<ll,int> M;

int first_ab(ll L, ll R, ll D){

    ll h = 2*(L*big + D);
    if(M.find(h) != M.end())return M[h];

    int lo = L;
    int hi = R;
    while(lo < hi-1){
        int mid = (lo+hi)/2;
        if(ST->get_ab(L, mid+1) < D){
            lo = mid;
        }
        else{
            hi = mid;
        }
    }
    M[h] = hi;

    return hi;
}

int last_ba(ll L, ll R, ll D){

    ll h = 2*(R*big + D) + 1;
    if(M.find(h) != M.end())return M[h];

    int lo = L;
    int hi = R;
    while(lo < hi-1){
        int mid = (lo+hi)/2;
        if(ST->get_ba(mid, R) >= D){
            lo = mid;
        }
        else{
            hi = mid;
        }
    }
    M[h] = lo;

    return lo;
}

int max_towers(int L, int R, int D){
    R++;

    if(ST->get_ab(L, R) < D || ST->get_ba(L, R) < D)return 1;
    int i = first_ab(L, R, D);
    int j = last_ba(L, R, D)+1;
    return (ST->geq(i,j,D))+1;
}


/*
int main() {

    int N;
    N = 7;
    vi H = {1,4,2,9,3,6,5};
    init(N,H);

    cout << max_towers(0, 6, 1) << "\n";
    cout << max_towers(0, 6, 2) << "\n";
    cout << max_towers(0, 6, 3) << "\n";
    cout << max_towers(0, 6, 10) << "\n";


    return 0;
}
*/

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 794 ms 18380 KB Output is correct
2 Correct 1534 ms 31396 KB Output is correct
3 Correct 1462 ms 31516 KB Output is correct
4 Correct 1226 ms 32000 KB Output is correct
5 Correct 1043 ms 22576 KB Output is correct
6 Correct 1250 ms 31860 KB Output is correct
7 Correct 991 ms 22612 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 3 ms 720 KB Output is correct
10 Correct 2 ms 720 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 720 KB Output is correct
3 Correct 2 ms 720 KB Output is correct
4 Correct 2 ms 848 KB Output is correct
5 Correct 2 ms 848 KB Output is correct
6 Correct 2 ms 848 KB Output is correct
7 Correct 2 ms 848 KB Output is correct
8 Correct 2 ms 848 KB Output is correct
9 Correct 2 ms 720 KB Output is correct
10 Correct 2 ms 848 KB Output is correct
11 Correct 2 ms 720 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 2 ms 720 KB Output is correct
14 Correct 1 ms 720 KB Output is correct
15 Correct 2 ms 720 KB Output is correct
16 Correct 2 ms 848 KB Output is correct
17 Correct 4 ms 848 KB Output is correct
18 Correct 2 ms 720 KB Output is correct
19 Correct 2 ms 848 KB Output is correct
20 Correct 2 ms 720 KB Output is correct
21 Correct 2 ms 848 KB Output is correct
22 Correct 2 ms 848 KB Output is correct
23 Correct 2 ms 720 KB Output is correct
24 Correct 2 ms 848 KB Output is correct
25 Correct 1 ms 464 KB Output is correct
26 Correct 2 ms 720 KB Output is correct
27 Correct 2 ms 720 KB Output is correct
28 Correct 2 ms 848 KB Output is correct
29 Correct 2 ms 848 KB Output is correct
30 Correct 2 ms 848 KB Output is correct
31 Correct 2 ms 848 KB Output is correct
32 Correct 2 ms 848 KB Output is correct
33 Correct 2 ms 720 KB Output is correct
34 Correct 2 ms 848 KB Output is correct
35 Correct 1 ms 752 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 720 KB Output is correct
3 Correct 2 ms 720 KB Output is correct
4 Correct 2 ms 848 KB Output is correct
5 Correct 2 ms 848 KB Output is correct
6 Correct 2 ms 848 KB Output is correct
7 Correct 2 ms 848 KB Output is correct
8 Correct 2 ms 848 KB Output is correct
9 Correct 2 ms 720 KB Output is correct
10 Correct 2 ms 848 KB Output is correct
11 Correct 2 ms 720 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 2 ms 720 KB Output is correct
14 Correct 1 ms 720 KB Output is correct
15 Correct 2 ms 720 KB Output is correct
16 Correct 2 ms 848 KB Output is correct
17 Correct 4 ms 848 KB Output is correct
18 Correct 2 ms 720 KB Output is correct
19 Correct 2 ms 848 KB Output is correct
20 Correct 2 ms 720 KB Output is correct
21 Correct 2 ms 848 KB Output is correct
22 Correct 2 ms 848 KB Output is correct
23 Correct 2 ms 720 KB Output is correct
24 Correct 2 ms 848 KB Output is correct
25 Correct 1 ms 464 KB Output is correct
26 Correct 2 ms 720 KB Output is correct
27 Correct 2 ms 720 KB Output is correct
28 Correct 2 ms 848 KB Output is correct
29 Correct 2 ms 848 KB Output is correct
30 Correct 2 ms 848 KB Output is correct
31 Correct 2 ms 848 KB Output is correct
32 Correct 2 ms 848 KB Output is correct
33 Correct 2 ms 720 KB Output is correct
34 Correct 2 ms 848 KB Output is correct
35 Correct 1 ms 752 KB Output is correct
36 Correct 83 ms 18688 KB Output is correct
37 Correct 141 ms 28888 KB Output is correct
38 Correct 133 ms 28836 KB Output is correct
39 Correct 118 ms 30664 KB Output is correct
40 Correct 124 ms 30796 KB Output is correct
41 Correct 125 ms 30644 KB Output is correct
42 Correct 128 ms 30640 KB Output is correct
43 Correct 81 ms 31940 KB Output is correct
44 Correct 85 ms 22540 KB Output is correct
45 Correct 90 ms 29312 KB Output is correct
46 Correct 85 ms 22528 KB Output is correct
47 Correct 133 ms 28816 KB Output is correct
48 Correct 120 ms 30592 KB Output is correct
49 Correct 144 ms 30644 KB Output is correct
50 Correct 78 ms 22608 KB Output is correct
51 Correct 90 ms 31720 KB Output is correct
52 Correct 122 ms 28840 KB Output is correct
53 Correct 126 ms 30644 KB Output is correct
54 Correct 146 ms 30692 KB Output is correct
55 Correct 78 ms 22608 KB Output is correct
56 Correct 99 ms 31104 KB Output is correct
57 Correct 131 ms 27324 KB Output is correct
58 Correct 119 ms 28884 KB Output is correct
59 Correct 130 ms 28932 KB Output is correct
60 Correct 124 ms 30604 KB Output is correct
61 Correct 116 ms 30596 KB Output is correct
62 Correct 115 ms 30680 KB Output is correct
63 Correct 122 ms 30676 KB Output is correct
64 Correct 84 ms 31876 KB Output is correct
65 Correct 87 ms 22496 KB Output is correct
66 Correct 97 ms 28304 KB Output is correct
67 Correct 87 ms 22536 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4024 ms 32868 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 786 ms 9412 KB Output is correct
2 Correct 2857 ms 37844 KB Output is correct
3 Correct 2937 ms 37748 KB Output is correct
4 Correct 2875 ms 39480 KB Output is correct
5 Correct 2749 ms 39884 KB Output is correct
6 Correct 2806 ms 39836 KB Output is correct
7 Correct 2929 ms 39604 KB Output is correct
8 Correct 954 ms 31896 KB Output is correct
9 Correct 965 ms 22540 KB Output is correct
10 Correct 2033 ms 33560 KB Output is correct
11 Correct 1844 ms 28764 KB Output is correct
12 Correct 126 ms 28848 KB Output is correct
13 Correct 116 ms 30584 KB Output is correct
14 Correct 114 ms 30576 KB Output is correct
15 Correct 80 ms 22612 KB Output is correct
16 Correct 90 ms 31084 KB Output is correct
17 Correct 112 ms 27240 KB Output is correct
18 Correct 133 ms 28888 KB Output is correct
19 Correct 123 ms 28852 KB Output is correct
20 Correct 118 ms 30624 KB Output is correct
21 Correct 118 ms 30600 KB Output is correct
22 Correct 130 ms 30652 KB Output is correct
23 Correct 128 ms 30660 KB Output is correct
24 Correct 84 ms 32028 KB Output is correct
25 Correct 76 ms 22576 KB Output is correct
26 Correct 87 ms 28328 KB Output is correct
27 Correct 76 ms 22556 KB Output is correct
28 Correct 2 ms 720 KB Output is correct
29 Correct 2 ms 848 KB Output is correct
30 Correct 2 ms 848 KB Output is correct
31 Correct 2 ms 720 KB Output is correct
32 Correct 2 ms 848 KB Output is correct
33 Correct 1 ms 464 KB Output is correct
34 Correct 2 ms 720 KB Output is correct
35 Correct 2 ms 720 KB Output is correct
36 Correct 2 ms 848 KB Output is correct
37 Correct 2 ms 848 KB Output is correct
38 Correct 2 ms 848 KB Output is correct
39 Correct 2 ms 848 KB Output is correct
40 Correct 1 ms 848 KB Output is correct
41 Correct 2 ms 720 KB Output is correct
42 Correct 1 ms 848 KB Output is correct
43 Correct 2 ms 720 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 720 KB Output is correct
3 Correct 2 ms 720 KB Output is correct
4 Correct 2 ms 848 KB Output is correct
5 Correct 2 ms 848 KB Output is correct
6 Correct 2 ms 848 KB Output is correct
7 Correct 2 ms 848 KB Output is correct
8 Correct 2 ms 848 KB Output is correct
9 Correct 2 ms 720 KB Output is correct
10 Correct 2 ms 848 KB Output is correct
11 Correct 2 ms 720 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 2 ms 720 KB Output is correct
14 Correct 1 ms 720 KB Output is correct
15 Correct 2 ms 720 KB Output is correct
16 Correct 2 ms 848 KB Output is correct
17 Correct 4 ms 848 KB Output is correct
18 Correct 2 ms 720 KB Output is correct
19 Correct 2 ms 848 KB Output is correct
20 Correct 2 ms 720 KB Output is correct
21 Correct 2 ms 848 KB Output is correct
22 Correct 2 ms 848 KB Output is correct
23 Correct 2 ms 720 KB Output is correct
24 Correct 2 ms 848 KB Output is correct
25 Correct 1 ms 464 KB Output is correct
26 Correct 2 ms 720 KB Output is correct
27 Correct 2 ms 720 KB Output is correct
28 Correct 2 ms 848 KB Output is correct
29 Correct 2 ms 848 KB Output is correct
30 Correct 2 ms 848 KB Output is correct
31 Correct 2 ms 848 KB Output is correct
32 Correct 2 ms 848 KB Output is correct
33 Correct 2 ms 720 KB Output is correct
34 Correct 2 ms 848 KB Output is correct
35 Correct 1 ms 752 KB Output is correct
36 Correct 83 ms 18688 KB Output is correct
37 Correct 141 ms 28888 KB Output is correct
38 Correct 133 ms 28836 KB Output is correct
39 Correct 118 ms 30664 KB Output is correct
40 Correct 124 ms 30796 KB Output is correct
41 Correct 125 ms 30644 KB Output is correct
42 Correct 128 ms 30640 KB Output is correct
43 Correct 81 ms 31940 KB Output is correct
44 Correct 85 ms 22540 KB Output is correct
45 Correct 90 ms 29312 KB Output is correct
46 Correct 85 ms 22528 KB Output is correct
47 Correct 133 ms 28816 KB Output is correct
48 Correct 120 ms 30592 KB Output is correct
49 Correct 144 ms 30644 KB Output is correct
50 Correct 78 ms 22608 KB Output is correct
51 Correct 90 ms 31720 KB Output is correct
52 Correct 122 ms 28840 KB Output is correct
53 Correct 126 ms 30644 KB Output is correct
54 Correct 146 ms 30692 KB Output is correct
55 Correct 78 ms 22608 KB Output is correct
56 Correct 99 ms 31104 KB Output is correct
57 Correct 131 ms 27324 KB Output is correct
58 Correct 119 ms 28884 KB Output is correct
59 Correct 130 ms 28932 KB Output is correct
60 Correct 124 ms 30604 KB Output is correct
61 Correct 116 ms 30596 KB Output is correct
62 Correct 115 ms 30680 KB Output is correct
63 Correct 122 ms 30676 KB Output is correct
64 Correct 84 ms 31876 KB Output is correct
65 Correct 87 ms 22496 KB Output is correct
66 Correct 97 ms 28304 KB Output is correct
67 Correct 87 ms 22536 KB Output is correct
68 Execution timed out 4024 ms 32868 KB Time limit exceeded
69 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 794 ms 18380 KB Output is correct
2 Correct 1534 ms 31396 KB Output is correct
3 Correct 1462 ms 31516 KB Output is correct
4 Correct 1226 ms 32000 KB Output is correct
5 Correct 1043 ms 22576 KB Output is correct
6 Correct 1250 ms 31860 KB Output is correct
7 Correct 991 ms 22612 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 3 ms 720 KB Output is correct
10 Correct 2 ms 720 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 2 ms 720 KB Output is correct
13 Correct 2 ms 720 KB Output is correct
14 Correct 2 ms 848 KB Output is correct
15 Correct 2 ms 848 KB Output is correct
16 Correct 2 ms 848 KB Output is correct
17 Correct 2 ms 848 KB Output is correct
18 Correct 2 ms 848 KB Output is correct
19 Correct 2 ms 720 KB Output is correct
20 Correct 2 ms 848 KB Output is correct
21 Correct 2 ms 720 KB Output is correct
22 Correct 0 ms 208 KB Output is correct
23 Correct 2 ms 720 KB Output is correct
24 Correct 1 ms 720 KB Output is correct
25 Correct 2 ms 720 KB Output is correct
26 Correct 2 ms 848 KB Output is correct
27 Correct 4 ms 848 KB Output is correct
28 Correct 2 ms 720 KB Output is correct
29 Correct 2 ms 848 KB Output is correct
30 Correct 2 ms 720 KB Output is correct
31 Correct 2 ms 848 KB Output is correct
32 Correct 2 ms 848 KB Output is correct
33 Correct 2 ms 720 KB Output is correct
34 Correct 2 ms 848 KB Output is correct
35 Correct 1 ms 464 KB Output is correct
36 Correct 2 ms 720 KB Output is correct
37 Correct 2 ms 720 KB Output is correct
38 Correct 2 ms 848 KB Output is correct
39 Correct 2 ms 848 KB Output is correct
40 Correct 2 ms 848 KB Output is correct
41 Correct 2 ms 848 KB Output is correct
42 Correct 2 ms 848 KB Output is correct
43 Correct 2 ms 720 KB Output is correct
44 Correct 2 ms 848 KB Output is correct
45 Correct 1 ms 752 KB Output is correct
46 Correct 83 ms 18688 KB Output is correct
47 Correct 141 ms 28888 KB Output is correct
48 Correct 133 ms 28836 KB Output is correct
49 Correct 118 ms 30664 KB Output is correct
50 Correct 124 ms 30796 KB Output is correct
51 Correct 125 ms 30644 KB Output is correct
52 Correct 128 ms 30640 KB Output is correct
53 Correct 81 ms 31940 KB Output is correct
54 Correct 85 ms 22540 KB Output is correct
55 Correct 90 ms 29312 KB Output is correct
56 Correct 85 ms 22528 KB Output is correct
57 Correct 133 ms 28816 KB Output is correct
58 Correct 120 ms 30592 KB Output is correct
59 Correct 144 ms 30644 KB Output is correct
60 Correct 78 ms 22608 KB Output is correct
61 Correct 90 ms 31720 KB Output is correct
62 Correct 122 ms 28840 KB Output is correct
63 Correct 126 ms 30644 KB Output is correct
64 Correct 146 ms 30692 KB Output is correct
65 Correct 78 ms 22608 KB Output is correct
66 Correct 99 ms 31104 KB Output is correct
67 Correct 131 ms 27324 KB Output is correct
68 Correct 119 ms 28884 KB Output is correct
69 Correct 130 ms 28932 KB Output is correct
70 Correct 124 ms 30604 KB Output is correct
71 Correct 116 ms 30596 KB Output is correct
72 Correct 115 ms 30680 KB Output is correct
73 Correct 122 ms 30676 KB Output is correct
74 Correct 84 ms 31876 KB Output is correct
75 Correct 87 ms 22496 KB Output is correct
76 Correct 97 ms 28304 KB Output is correct
77 Correct 87 ms 22536 KB Output is correct
78 Execution timed out 4024 ms 32868 KB Time limit exceeded
79 Halted 0 ms 0 KB -