Submission #930452

#	Time	Username	Problem	Language	Result	Execution time	Memory
930452		asdf1234coding	Sightseeing in Kyoto (JOI22_kyoto)	C++14	100 / 100	346 ms	21332 KiB

kyoto

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define vi vector<int>
#define pb push_back
 
 
struct uwu {
	int l,r,sz,v;
	bool operator<(const uwu &oth) const {
		// compare v/sz
		// v/sz > oth.v/oth.sz
		// v * oth.sz > oth.v * sz
		if(v*oth.sz != oth.v*sz) {
			return v*oth.sz>oth.v*sz;
		}
		// this makes high values first so i want l values increasing
		return l>oth.l;
	}
};
void db(uwu x) {
	cout<<x.l<<' '<<x.r<<' '<<x.sz<<' '<<x.v<<endl;
}
 
int32_t main() {
	int h,w; cin>>h>>w;
	vi a(h+1); vi b(w+1);
	for(int i=1; i<=h; i++) {
		cin>>a[i];
	}
	for(int i=1; i<=w; i++) {
		cin>>b[i];
	}
	set<uwu> A, B;
	for(int i=1; i<h; i++) {
		A.insert({i, i+1, 1, a[i+1]-a[i]});
	}
	for(int i=1; i<w; i++) {
		B.insert({i, i+1, 1, b[i+1]-b[i]});
	}
	int ret=0;
	vi toA(h+1), toB(w+1);
	for(int i=0; i<=h; i++) {
		toA[i]=i+1;
	}
	for(int i=0; i<=w; i++) {
		toB[i]=i+1;
	}
	A.insert({0, 1, 1, (int)-1e9});
	B.insert({0, 1, 1, (int)-1e9});
	while(A.size()>1 || B.size()>1) {
		// cout<<"A, B: ";
		// db(*(A.begin())); db(*(B.begin()));
		if(*A.begin() < *B.begin()) {
			// cout<<"A bigger"<<endl;
			uwu rm = *A.begin(); A.erase(A.begin());
			if(toA[rm.l]==(int)a.size()-1) {
				for(int _=0; _<rm.sz; _++) {
					ret+=*(--b.end()); a.pop_back();
				}
				continue;
			}
			int nxt1=toA[rm.l]; int nxt2=toA[nxt1];
			A.erase({nxt1, nxt2, nxt2-nxt1, a[nxt2]-a[nxt1]});
			toA[rm.l]=nxt2;
			// cout<<"resetA "<<rm.l<<' '<<nxt2<<endl;
			if(rm.l<=nxt2) A.insert({rm.l, nxt2, nxt2- rm.l, a[nxt2]-a[rm.l]});
			// cout<<"insert "<<rm.l<<' '<<nxt2<<' '<<nxt2-rm.l<<' '<<a[nxt2]-a[rm.l]<<endl;
		} else {
			// cout<<"B bigger"<<endl;
			// remove from B
			uwu rm = *B.begin(); B.erase(B.begin());
			if(toB[rm.l]==(int)b.size()-1) {
				// add to answer since we're forced (?)
				for(int _=0; _<rm.sz; _++) {
					ret+=*(--a.end()); b.pop_back();
				}
				continue;
			}
			int nxt1=toB[rm.l]; int nxt2=toB[nxt1];
			B.erase({nxt1, nxt2, nxt2-nxt1, b[nxt2]-b[nxt1]}); // erase the next segment
			toB[rm.l]=nxt2; // update range
			// cout<<"resetB "<<rm.l<<' '<<nxt2<<endl;
			if(rm.l<=nxt2) B.insert({rm.l, nxt2, nxt2-rm.l, b[nxt2]-b[rm.l]}); // add the new segment
			// cout<<"insert "<<rm.l<<' '<<nxt2<<' '<<nxt2-rm.l<<' '<<b[nxt2]-b[rm.l]<<endl;
		}
	}
	cout<<ret<<endl;
}



/*
1 2 1 10
4 5 1 43
popb 55
1 2 1 10
2 3 1 32
resetB 2 4
insert 2 4 2 -29
1 2 1 10
2 4 2 -29
resetA 1 3
insert 1 3 2 -65
1 3 2 -65
2 4 2 -29
popb 12popb 73
1 3 2 -65
1 2 1 -42
popa 7popa 820 1 1 -1000000000
1 2 1 -42
popb 41
175
*/

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