Submission #826522

#	Time	Username	Problem	Language	Result	Execution time	Memory
826522		caganyanmaz	Wiring (IOI17_wiring)	C++17	100 / 100	95 ms	18352 KiB

wiring

#include <bits/stdc++.h>
#define pb push_back
#define int int64_t
using namespace std;
#include "wiring.h"

#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif


constexpr static int MXN = 1e5;
#ifdef DEBUGGING
constexpr static int MXG = 10;
#else
constexpr static int MXG = 205;
#endif
constexpr static int INF = 1e16;


struct SegTree
{
	vector<int> data;
	vector<int> lazy;
	int n;
	SegTree(int _n) : n(_n), data(_n<<2, INF), lazy(_n<<2) {}
	void push(int l, int r, int index)
	{
		data[index] += lazy[index];
		if (data[index] > INF)
			data[index] = INF;
		if (r - l > 1)
		{
			lazy[index<<1] += lazy[index];
			lazy[(index<<1)|1] += lazy[index];
		}
		lazy[index] = 0;
	}
	void updater(int l, int r, int index, int ss, int ee, int val)
	{
		push(l, r, index);
		if (ss >= r || l >= ee)
			return;
		if (ee >= r && l >= ss)
		{
			lazy[index] += val;
			push(l, r, index);
			return;
		}
		int m = l+r>>1;
		updater(l, m, index<<1, ss, ee, val);
		updater(m, r, (index<<1)|1, ss, ee, val);
		data[index] = min(data[index<<1], data[(index<<1)|1]);
	}
	void updatep(int l, int r, int index, int i, int val)
	{
		push(l, r, index);
		if (i >= r || l > i)
			return;
		if (r - l == 1)
		{
			data[index] = min(data[index], val);
			return;
		}
		int m = l+r>>1;
		updatep(l, m, index<<1, i, val);
		updatep(m, r, (index<<1)|1, i, val);
		data[index] = min(data[index<<1], data[(index<<1)|1]);
	}
	int query(int l, int r, int index, int ss, int ee)
	{
		push(l, r, index);
		if (l >= ee || ss >= r)
			return INF;
		if (ee >= r && l >= ss)
			return data[index];
		int m = l+r>>1;
		int lval = query(l, m, index<<1, ss, ee);
		int rval = query(m, r, (index<<1)|1, ss, ee);
		return min(lval, rval);
	}
	void clear() { lazy.clear(); data.clear(); }
	void updater(int ss, int ee, int val) { updater(0, n, 1, ss, ee, val); }
	void updatep(int i, int val) { updatep(0, n, 1, i, val); } 
	int query(int ss, int ee) { return query(0, n, 1, ss, ee); }
};
deque<int> r, b;



long long subtask2()
{
	int m = r.back();
	int sum = 0;
	for (int i : r)
		sum += m - i;
	for (int i : b)
		sum += i - m;
	if (r.size() > b.size())
		sum += (b[0] - m) * (r.size() - b.size());
	return sum;
}


long long min_total_length(vector<int32_t> rr, vector<int32_t> bb) 
{
	for (int i : rr)
		r.push_back(i);
	for (int i : bb)
		b.push_back(i);
	if (r.back() < b[0])
		return subtask2();
	int g = 200;
	if (rr.size() > 200 || bb.size() > 200)
		g = 9;
	int current = 0;
	//fill(dp.begin(), dp.begin() + g, INF);
	//dp[0] = 0;
	if (r[0] > b[0])
		swap(r, b);
	int mnr = -INF;
	SegTree st(1);
	SegTree st2(1);
	st.updatep(0, 0);
	debug(r, b);
	while (r.size() || b.size())
	{
		vector<int> v;
		assert(v.size() < g);
		while (r.size() && (b.empty() || r[0] < b[0])) 
		{
			v.pb(r[0]);
			r.pop_front();
		}
		st2.clear();
		st2 = SegTree(v.size()+1);
		int rb = b[0], lb = v[0];
		int lsum = 0, rsum = 0;
		for (int j = 0; j < v.size(); j++)
			rsum += rb - v[j];
		for (int i = v.size(); i >= 0; i--) // How many we're putting to right
		{
		//j	for (int j = v.size()-i; j < v.size(); j++)
		//		rsum += rb - v[j];
			debug(i, st.query(0, st.n), lsum, rsum);
			st2.updatep(i, st.query(0, st.n) + lsum + rsum);
			st.updater(0, v.size()-i+1, lb - mnr);
			if (i > 0)
			{
				lsum += v[v.size()-i] - lb;
				rsum -= rb- v[v.size()-i];
			}
			//for (int j = g-1; j >= 0; j--) // How many is coming from right
			//{
			//	if (j < v.size()-i) // We need to take more
			//		dp2[i] = min<int>(dp2[i], dp[j] + (v.size()-i-j) * (lb - mnr) + lsum + rsum);
			//	else
			//		dp2[i] = min<int>(dp2[i], dp[j] + lsum + rsum);
				// We might need to give more as well (but it has 0 contribution so it doesn't matter)
			//}

		}
		mnr = v.back();
		swap(r, b);
		swap(st, st2);
		debug(r, b);
	}
	return st.query(0, 1);
}

Compilation message (stderr)

wiring.cpp: In constructor 'SegTree::SegTree(int64_t)':
wiring.cpp:27:6: warning: 'SegTree::n' will be initialized after [-Wreorder]
   27 |  int n;
      |      ^
wiring.cpp:25:14: warning:   'std::vector<long int> SegTree::data' [-Wreorder]
   25 |  vector<int> data;
      |              ^~~~
wiring.cpp:28:2: warning:   when initialized here [-Wreorder]
   28 |  SegTree(int _n) : n(_n), data(_n<<2, INF), lazy(_n<<2) {}
      |  ^~~~~~~
wiring.cpp: In member function 'void SegTree::updater(int64_t, int64_t, int64_t, int64_t, int64_t, int64_t)':
wiring.cpp:52:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |   int m = l+r>>1;
      |           ~^~
wiring.cpp: In member function 'void SegTree::updatep(int64_t, int64_t, int64_t, int64_t, int64_t)':
wiring.cpp:67:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |   int m = l+r>>1;
      |           ~^~
wiring.cpp: In member function 'int64_t SegTree::query(int64_t, int64_t, int64_t, int64_t, int64_t)':
wiring.cpp:79:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |   int m = l+r>>1;
      |           ~^~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from wiring.cpp:1:
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:131:19: warning: comparison of integer expressions of different signedness: 'std::vector<long int>::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
  131 |   assert(v.size() < g);
      |          ~~~~~~~~~^~~
wiring.cpp:141:21: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |   for (int j = 0; j < v.size(); j++)
      |                   ~~^~~~~~~~~~
wiring.cpp:118:6: warning: unused variable 'current' [-Wunused-variable]
  118 |  int current = 0;
      |      ^~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 45 / 45