Submission #886531

#	Time	Username	Problem	Language	Result	Execution time	Memory
886531		vjudge1	Gym Badges (NOI22_gymbadges)	C++17	100 / 100	991 ms	59644 KiB

Main

#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){
		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]);
		if (l[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];
			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: 15 / 15
• Subtask 2: 9 / 9
• Subtask 3: 27 / 27
• Subtask 4: 49 / 49