oj.uz

답안 #1101851

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1101851 2024-10-17T03:39:37 Z Berryisbetter 나일강 (IOI24_nile) C++17
6 / 100
 124 ms 29064 KB 
#include <bits/stdc++.h>
#include "nile.h"
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vvll = vector<vll>;
const ll INF = 1e9;
vll EMPTY = {};
vll a, b, w;
struct Sum {
	ll n;
	vll sum;
	//Sum();
	Sum(vll a) :n(a.size()), sum(n + 1) {
		for (ll i = 0; i < n; i++) {
			sum[i + 1] = sum[i] + a[i];
		}
	}
	ll qu(ll l, ll r) {
		return sum[r] - sum[l];
	}
};
struct Seg {
	ll n;
	vll a;
	//Seg();
	Seg(vll& v) :n(v.size()), a(2 * n) {
		for (ll i = 0; i < n; i++) {
			a[i + n] = v[i];
		}
		for (ll i = n - 1; i > 0; i--) {
			a[i] = max(a[i * 2], a[i * 2 + 1]);
		}
	}
	void up(ll i, ll x) {
		i += n;
		a[i] = x;
		while (i > 1) {
			i /= 2;
			a[i] = max(a[i * 2], a[i * 2 + 1]);
		}
	}
	ll qu(ll l, ll r) {
		ll ans = -INF;
		for (l += n, r += n; l < r; l /= 2, r /= 2) {
			if (l % 2) {
				ans = max(ans,a[l++]);
			}
			if (r % 2) {
				ans = max(ans,a[--r]);
			}
		}
		return ans;
	}
};
Sum sumall(EMPTY);
Seg segall(EMPTY), segeven(EMPTY), segodd(EMPTY);
ll calc(ll l, ll r) {
	if ((r - l) % 2 == 0) {
		return sumall.qu(l, r);
	}
	if (l % 2 == 0) {
		return sumall.qu(l, r) - max(segall.qu(l, r), segeven.qu(l, r));
	}
	return sumall.qu(l, r) - max(segall.qu(l, r), segodd.qu(l, r));
}


std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E) {
	ll n = A.size(), q = E.size();
	vector<pair<ll, pll>> ord(n);
	for (ll i = 0; i < n; i++) {
		ord[i] = { W[i],{A[i],B[i]} };
	}
	sort(ord.begin(), ord.end());
	//a = A, b = B, w = W; in correct order:
	a = b = w = vll(n);
	for (ll i = 0; i < n; i++) {
		w[i] = ord[i].first;
		a[i] = ord[i].second.first;
		b[i] = ord[i].second.second;
	}

	//setup rmq rsq:
	sumall = Sum(b);
	vll temp = b, rem;
	for (ll i = 0; i < n; i++) {
		temp[i] -= a[i];
	}
	rem = temp;
	segall = Seg(temp);
	for (ll i = 0; i < n; i += 2) {
		temp[i] = -INF;
	}
	segodd = Seg(temp);
	temp = rem;
	for (ll i = 1; i < n; i += 2) {
		temp[i] = -INF;
	}
	segeven = Seg(temp);
	temp = rem;

	//setup ev:
	vector<pair<ll, pll>> ev;// {len,{type,inx}}. type: 0 - query,1 - next disconnect,2 - disconnect two steps
	for (ll i = 0; i < q; i++) {
		ev.push_back({ E[i],{0,i} });//?
	}
	for (ll i = 0; i < n - 1; i++) {
		ev.push_back({ w[i + 1] - w[i],{1,i} });//+1?
	}
	for (ll i = 0; i < n - 2; i++) {
		ev.push_back({ w[i + 2] - w[i],{2,i} });//+1?
	}
	sort(ev.begin(), ev.end());
	reverse(ev.begin(), ev.end());

	// solve:
	vll ans(q);
	ll sum = calc(0, n);
	set<pll> segs = { { 0ll,n } };
	for (auto k : ev) {
		ll type = k.second.first, inx = k.second.second;
		if (type == 0) {
			ans[inx] = sum;
		}
		if (type == 1) {
			auto p = segs.upper_bound({ inx,INF });
			p--;
			ll l = (*p).first, r = (*p).second;
			sum -= calc(l, r);
			segs.erase(p);
			segs.insert({ l, inx + 1 });
			segs.insert({inx + 1, r});
			sum += calc( l, inx + 1 );
			sum += calc( inx + 1, r );
		}
		if (type == 2) {
			auto p = segs.upper_bound({ inx,INF });
			p--;
			ll l = (*p).first, r = (*p).second;
			sum -= calc(l, r);
			segall.up(inx+1, -INF);//?+1
			sum += calc(l, r);
		}
	}
	return ans;
}

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1020 KB Output is correct
2 Correct 3 ms 848 KB Output is correct
3 Correct 3 ms 848 KB Output is correct
4 Correct 2 ms 848 KB Output is correct
5 Correct 2 ms 952 KB Output is correct
6 Correct 2 ms 848 KB Output is correct

Subtask #2
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 124 ms 29064 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 102 ms 26792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1020 KB Output is correct
2 Correct 3 ms 848 KB Output is correct
3 Correct 3 ms 848 KB Output is correct
4 Correct 2 ms 848 KB Output is correct
5 Correct 2 ms 952 KB Output is correct
6 Correct 2 ms 848 KB Output is correct
7 Incorrect 2 ms 848 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1020 KB Output is correct
2 Correct 3 ms 848 KB Output is correct
3 Correct 3 ms 848 KB Output is correct
4 Correct 2 ms 848 KB Output is correct
5 Correct 2 ms 952 KB Output is correct
6 Correct 2 ms 848 KB Output is correct
7 Incorrect 124 ms 29064 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 102 ms 26792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -