oj.uz

Submission #886518

# Submission time Handle Problem Language Result Execution time Memory
886518 2023-12-12T09:18:13 Z vjudge1 Gym Badges (NOI22_gymbadges) C++17
9 / 100
 507 ms 53416 KB 
#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second 
#define N 500005
#define int long long
#define L(node) node * 2
#define R(node) node * 2 + 1


const int INF = 1e9 + 7;

int x[N], l[N], lazy[4 * N],  tree[4 * N], ind[N];
int mini[4 * N];

void push(int node, int l, int r){
	mini[node] += lazy[node];
	if (l != r){
		lazy[L(node)] += lazy[node];
		lazy[R(node)] += lazy[node];
	}
	lazy[node] = 0;
}

void sett(int node, int l, int r, int sl, pii val){
	push(node, l, r);
	if (l > sl || r < sl) return;
	if (l == r){
		if (l == sl){
			tree[node] = val.nd;
			mini[node] = val.st;	
		}
		return;
	}
	int mid = (l + r) / 2;
	sett(L(node), l, mid, sl, val);
	sett(R(node), mid + 1, r, sl, val);
	tree[node] = tree[L(node)] + tree[R(node)];
	mini[node] = min(mini[L(node)], mini[R(node)]);
}

void update(int node, int l, int r, int sl, int sr, int val){
	push(node, l, r);
	if (l > r || l > sr || r < sl) return;
	if (l >= sl && r <= sr){
		lazy[node] += val;
		push(node, l, r);
		return;
	}

	int mid = (l + r) / 2;
	update(L(node), l, mid, sl, sr, val);
	update(R(node), mid + 1, r, sl, sr, val);
	mini[node] = min(mini[L(node)], mini[R(node)]);
}

int pos_query(int node, int l, int r, int val){
	push(node, l, r);
	if (l == r){
		//cout<<"compare : "<<l<<sp<<mini[node]<<sp<<val<<endl;
		if (mini[node] >= val) return l;
		return INF;
	}
	int mid = (l + r) / 2;
	push(L(node), l, mid);
	push(R(node), mid + 1, r);
	if (mini[R(node)] < val) return pos_query(R(node), mid + 1, r, val);
	return min(pos_query(L(node), l, mid, val), mid + 1);
}

int query(int node, int l, int r, int sl, int sr){
	push(node, l, r);
	if (l > r ||l > sr || r < sl) return 0;
	if (l >= sl && r <= sr) return tree[node];
	int mid = (l + r) / 2;
	return query(L(node), l, mid, sl, sr) + query(R(node), mid + 1, r, sl, sr);
}

int min_query(int node, int l, int r, int sl, int sr){
	push(node, l, r);
	if (l > r ||l > sr || r < sl) return INF;
	if (l >= sl && r <= sr) {
		return mini[node];
	}
	int mid = (l + r) / 2;
	int ans =  min(min_query(L(node), l, mid, sl, sr), min_query(R(node), mid + 1, r, sl, sr));
	return ans;
}

void build(int node, int l, int r){
	mini[node] = INF;
	tree[node] = 0;
	if (l == r) return;
	int mid = (l + r) / 2;
	build(L(node), l, mid);
	build(R(node), mid + 1, r);
}

int32_t main(){
	//fileio();
	fastio();


	int n;
	cin>>n;
	build(1, 1, n);
	for (int i = 1; i <= n; i++){
		cin>>x[i];
	}
	for (int i = 1; i <= n; i++){
		cin>>l[i];
	}

	vector<int> v(n, 0), g(n , 0);
	iota(v.begin(), v.end(), 1);
	iota(g.begin(), g.end(), 1);
	sort(v.begin(), v.end(), [&](int a, int b){
		if (x[a] == x[b]) return l[a] < l[b];
		return x[a] < x[b];
	});

	sort(g.begin(), g.end(), [&](int a, int b){
		if (x[a] + l[a] == x[b] + l[b]) return x[a] < x[b];
		return x[a] + l[a] < x[b] + l[b];
	});

	for (int i = 0; i < n; i++){
		ind[g[i]] = i + 1;
	}
	int sum = 0;
	int ans = 0;
	for (auto i : v){
		//check
		int pos = pos_query(1, 1, n, sum + x[i]);
		//cout<<i<<sp<<sum + x[i]<<sp<<pos<<endl;
		if (x[i] >= sum - query(1, 1, n, pos, n)){
			int first = x[i] + l[i] + query(1, 1, n, ind[i] + 1, n);
			int second = x[i];
			//cout<<"add: "<<i<<sp<<ind[i]<<sp<<first<<sp<<second<<endl;
			sett(1, 1, n, ind[i], {first, second});
			update(1, 1, n, 1, ind[i] - 1, second);
			ans++;
			sum += x[i];
		}
		
	}
	//cout<<endl;
	cout<<ans<<endl;
	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 8536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 44372 KB Output is correct
2 Correct 339 ms 51616 KB Output is correct
3 Correct 321 ms 51876 KB Output is correct
4 Correct 324 ms 51856 KB Output is correct
5 Correct 316 ms 51792 KB Output is correct
6 Correct 362 ms 51192 KB Output is correct
7 Correct 307 ms 50512 KB Output is correct
8 Correct 336 ms 50928 KB Output is correct
9 Correct 330 ms 51024 KB Output is correct
10 Correct 340 ms 51324 KB Output is correct
11 Correct 497 ms 51112 KB Output is correct
12 Correct 457 ms 53328 KB Output is correct
13 Correct 466 ms 53416 KB Output is correct
14 Correct 461 ms 53300 KB Output is correct
15 Correct 507 ms 53340 KB Output is correct
16 Correct 383 ms 50876 KB Output is correct
17 Correct 367 ms 50900 KB Output is correct
18 Correct 398 ms 51332 KB Output is correct
19 Correct 357 ms 50836 KB Output is correct
20 Correct 337 ms 50720 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 8536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 8536 KB Output isn't correct
2 Halted 0 ms 0 KB -