oj.uz

Submission #1082244

# Submission time Handle Problem Language Result Execution time Memory
1082244 2024-08-31T01:10:52 Z s_tree Radio Towers (IOI22_towers) C++17
0 / 100
 4000 ms 6980 KB 
#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int root = 0;
int par[N];
int L[N], R[N], mn[N];

struct ST {
	vector<pair<int,int>> t;
	int n;
	ST(){}
	ST(vector<int>&h) {
		n  = h.size();
		t.resize(2*n);
		for(int i = 0;i<n;i++)t[i+n] = {h[i], i};
		for(int i = n-1;i>0;i--)t[i] = max(t[2*i], t[2*i+1]);
	}
	int query(int l, int r) {
		l+=n,r+=n+1;
		pair<int,int> ans = {-1, -1};	
		for(;l<r;l>>=1,r>>=1) {
			if(l&1)ans = max(ans, t[l++]);
			if(r&1)ans = max(ans, t[--r]);
		}
		return ans.second;
	}
};
struct ST2 {
	vector<int> t;
	int n;
	ST2(){}
	ST2(vector<int>&h) {
		n  = h.size();
		t.resize(2*n);
		for(int i = 0;i<n;i++)t[i+n] = h[i];
		for(int i = n-1;i>0;i--)t[i] = min(t[2*i], t[2*i+1]);
	}
	int query(int l, int r) {
		l+=n,r+=n+1;
		int ans = 2e9;
		for(;l<r;l>>=1,r>>=1) {
			if(l&1)ans = min(ans, t[l++]);
			if(r&1)ans = min(ans, t[--r]);
		}
		return ans;
	}
};
vector<int> H;
ST st;
ST2 st2;
int pref[N+1];
int build(int l, int r) {
	if(r < l)return -1;
	int p = st.query(l, r);
	L[p] = build(l, p-1);
	R[p] = build(p+1, r);
	mn[p] = H[p];
	if(L[p]!=-1)mn[p] = min(mn[p], mn[L[p]]);
	if(R[p]!=-1)mn[p] = min(mn[p], mn[R[p]]);
	return p;
}
void init(int n, std::vector<int> h) {
	st = ST(h);
	st2 = ST2(h);
	H = h;
	root = build(0, n-1);
	for(int i = 0;i<n;i++) {
		if(i)pref[i] += pref[i-1];
		if(L[i] == -1 and R[i] == -1) {
			pref[i]++;
		}
	}
}


int query(int v, int l, int r, int MX, int D) {
	if(l > r)return 0;
	if(v == -1)return 0;
	if(v > r) {
		return query(L[v], l, r, MX, D);
	}
	if(v < l)
		return query(R[v], l, r, MX, D);
	int ans = 0;	
	if(st2.query(l, r) <= MX)ans=1;
	ans = max(ans, query(L[v], l, v-1, H[v]-D, D)+query(R[v], v+1, r, H[v]-D, D));
	return ans;
}
int max_towers(int l, int r, int D) {
	if(D == 1) return pref[r] - (l?pref[l-1]:0);
  return query(root, l, r, 2e9, D);
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '2', found: '0'
13 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '2', found: '0'
13 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 444 ms 5456 KB 1st lines differ - on the 1st token, expected: '11903', found: '11902'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

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

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '2', found: '0'
13 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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