Submission #1256468

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256468		penguin133	Nile (IOI24_nile)	C++20	100 / 100	569 ms	66908 KiB

nile

#include <bits/stdc++.h>
using namespace std;
#include "nile.h"
//#define int long long
typedef long long ll;
#define pi pair<ll, ll>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

struct node{
	ll s, e, m, val;
	node *l, *r;
	node (int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1;
		if(s != e)l = new node(s, m), r = new node(m+1, e);
		val = 0;
	}
	
	void upd(int p, ll v){
		if(s == e)val = v;
		else{
			if(p <= m)l->upd(p, v);
			else r->upd(p, v);
			val = min(l->val, r->val);
		}
	}
	
	ll qry(int a, int b){
		if(a > b)return 1e18;
		if(a == s && b == e)return val;
		if(b <= m)return l->qry(a, b);
		if(a > m)return r->qry(a, b);
		return min(l->qry(a, m), r->qry(m+1, b));
	}
}*odd, *even, *ext1, *ext2;

ll cst(int l, int r){
	if((r - l + 1) % 2 == 0)return 0;
	ll tmp = 1e18;
	if(l % 2)tmp = min(odd->qry(l, r), ext2->qry(l + 1, r - 1));
	else tmp = min(even->qry(l, r), ext1->qry(l+1, r - 1));
	return tmp;
}

std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E){
	 vector <pi> v;
	 int n = (int)W.size(), q = (int)E.size();
	 for(int i = 0; i < n; i++)v.push_back({W[i], i});
	 set <pi> s;
	 s.insert({0, n - 1});
	 sort(v.begin(), v.end());
	 odd = new node(0, n - 1);
	 even = new node(0, n - 1);
	 ext1 = new node(0, n - 1);
	 ext2 = new node(0, n - 1);
	 for(int i = 0; i < n; i++){
		 odd->upd(i, 1e18);
		 even->upd(i, 1e18);
		 ext1->upd(i, 1e18);
		 ext2->upd(i, 1e18);
	 }
	 for(int i = 0; i < n; i+=2){
		even->upd(i, A[v[i].se] - B[v[i].se]);
		if(i && i != n - 1)ext2->upd(i, A[v[i].se] - B[v[i].se]);
	 }
	 for(int i = 1; i < n; i += 2){
		odd->upd(i, A[v[i].se] - B[v[i].se]);
		if(i && i != n - 1)ext1->upd(i, A[v[i].se] - B[v[i].se]);
	 }
	 vector <pi> Q;
	 vector <ll> ans; ans.resize(q);
	 for(int i = 0; i < q; i++)Q.push_back({E[i], i});
	 sort(Q.begin(), Q.end(), greater<>());
	 vector <pi> dff, dff2;
	 for(int i = 1; i < n; i++)dff.push_back({v[i].fi - v[i - 1].fi, i});
	 for(int i = 2; i < n; i++)dff2.push_back({v[i].fi - v[i - 2].fi, i});
	 sort(dff.begin(), dff.end(), greater<>());
	 sort(dff2.begin(), dff2.end(), greater<>());
	 ll cur = 0;
	 for(auto i : B)cur += i;
	 cur += cst(0, n - 1);
	 int ptr = 0, ptr2 = 0;
	// cerr << "ok?\n";
	 for(auto [i, j] : Q){
		 while(ptr < n - 1 && dff[ptr].fi > i){
			 ll tmp = dff[ptr].se;
			 pi brr = {tmp, 0};
			 auto it = s.lower_bound(brr);
			 assert(it != s.begin());
			 it--;
			 pi w = *it;
			 int l = w.fi, r = w.se;
			 cur -= cst(l, r);
			 //cerr << tmp << '\n';
			 if(tmp % 2){
				 ext1->upd(tmp, 1e18);
				 ext2->upd(tmp - 1, 1e18);
			 }
			 else{
				 ext1->upd(tmp - 1, 1e18);
				 ext2->upd(tmp, 1e18);
			 }
			 s.erase({l, r});
			 cur += cst(l, tmp - 1) + cst(tmp, r);
			 s.insert({l, tmp - 1});
			 s.insert({tmp, r});
			 ptr++;
		 }
		 //cerr << 1 << '\n';
		 while(ptr2 < n - 2 && dff2[ptr2].fi > i){
			 int tmp = dff2[ptr2].se;
			 pi brr = {tmp, 1e18};
			 auto it = s.lower_bound(brr);
			 assert(it != s.begin());
			 it--;
			 pi w = *it;
			 int l = w.fi, r = w.se;
			 if(l <= tmp - 2 && r >= tmp){
				 cur -= cst(l, r);
				 if((tmp - 1) % 2)ext1->upd(tmp - 1, 1e18);
				 else ext2->upd(tmp - 1, 1e18);
				 cur += cst(l, r);
			 }
			 else {
				 if((tmp - 1) % 2)ext1->upd(tmp - 1, 1e18);
				 else ext2->upd(tmp - 1, 1e18);
			 }
			 ptr2++;
		 }
		 //cerr << 2 << '\n';
		 ans[j] = cur;
	 }
	 return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15
• Subtask 7: 18 / 18