Submission #605375

#	Time	Username	Problem	Language	Result	Execution time	Memory
605375		Red_Inside	Sightseeing in Kyoto (JOI22_kyoto)	C++17	100 / 100	663 ms	28948 KiB

kyoto

//
#include <bits/stdc++.h>

#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define o cout<<"BUG"<<endl;
#define FOR(i, j, n) for(int j = i; j < n; ++j)
#define forn(i, j, n) for(int j = i; j <= n; ++j)
#define nfor(i, j, n) for(int j = n; j >= i; --j)
#define all(v) v.begin(), v.end()
#define ld long double
#define ull unsigned long long

using namespace std;
const int maxn=1e6+100,LOG=17,mod=1e9+7;
int block = 226, timer = 0;
const ld EPS = 1e-18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define bt(i) (1 << (i))
#define int ll
const int inf=2e9;
#define y1 yy
#define prev pre
#define pii pair <int, int>

int n, m, a[maxn], b[maxn];
set <pair <double, pair <pii, int> > > st;
set <int> s[3];
pii pos;

main()
{
	IOS
	cin >> n >> m;
	forn(1, i, n)
	{
		cin >> a[i];
	}
	forn(1, j, m)
	{
		cin >> b[j];
	}
	forn(1, i, n - 1)
	{
		st.insert({(a[i + 1] - a[i]), {{i, i + 1}, 1}});
	}
	forn(1, i, n) s[1].insert(i);
	forn(1, j, m) s[2].insert(j);
	forn(1, i, m - 1)
	{
		st.insert({(b[i + 1] - b[i]), {{i, i + 1}, 2}});
	}
	int ans = 0;
	pos.f = n;
	pos.s = m;
	while(st.size())
	{
		auto it = *st.find(*st.rbegin());
//		cout << "DELETE " << it.s.f.s << " " << it.s.s << " " << it.f << endl;
		st.erase(it);
		if(it.s.s == 1)
		{
			s[1].erase(it.s.f.s);
			auto it2 = s[1].lower_bound(it.s.f.s);
			if(it2 != s[1].end())
			{
				st.erase({1.0 * (a[*it2] - a[it.s.f.s]) / (*it2 - it.s.f.s), 
				{{it.s.f.s, *it2}, 1}});
				st.insert({1.0 * (a[*it2] - a[it.s.f.f]) / (*it2 - it.s.f.f), 
				{{it.s.f.f, *it2}, 1}});
			}
			else
			{
//				cout << "PLUS!!!!!!     " << (pos.s - *s[2].rbegin()) * a[it.s.f.s] << endl;
				ans += (pos.s - *s[2].rbegin()) * a[it.s.f.s];
				pos.s = *s[2].rbegin();
			}
		}
		else
		{
			s[2].erase(it.s.f.s);
			auto it2 = s[2].lower_bound(it.s.f.s);
			if(it2 != s[2].end())
			{
				st.erase({1.0 * (b[*it2] - b[it.s.f.s]) / (*it2 - it.s.f.s), 
				{{it.s.f.s, *it2}, 2}});
				st.insert({1.0 * (b[*it2] - b[it.s.f.f]) / (*it2 - it.s.f.f), 
				{{it.s.f.f, *it2}, 2}});
			}
			else
			{
//				cout << "PLUS!!!!!!   " << (pos.f - *s[1].rbegin()) * b[it.s.f.s] << endl;
				ans += (pos.f - *s[1].rbegin()) * b[it.s.f.s];
				pos.f = *s[1].rbegin();
			}
		}
	}
	if(pos.f != 1) ans += b[1] * (pos.f-1);
	else ans += a[1] * (pos.s-1);
	cout << ans;
}

Compilation message (stderr)

kyoto.cpp:36:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   36 | main()
      | ^~~~

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60