Submission #835003

#	Time	Username	Problem	Language	Result	Execution time	Memory
835003		CSQ31	Sightseeing in Kyoto (JOI22_kyoto)	C++17	30 / 100	484 ms	23968 KiB

kyoto

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
int a[100001],b[100001];
struct pt{
	ll x,y;
	int id;
	pt(ll _x,ll _y,int _id): x(_x),y(_y),id(_id){}
	bool operator<(const pt &t) const {
		if(x * t.y == y * t.x)return id > t.id;
		return (x * t.y) < (y * t.x); 
		
	}
	//bool operator==(const pt &t) const {return x==t.x && y==t.y && id==t.id;}
};
int main()
{ 
	owo
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<m;i++)cin>>b[i];
	
	set<pt>h,w;
	set<int>row,col;
	
	for(int i=0;i<n;i++)row.insert(i);
	for(int i=1;i<n;i++)h.insert(pt(a[i]-a[i-1],1,i));
		
	for(int i=0;i<m;i++)col.insert(i);
	for(int i=1;i<m;i++)w.insert(pt(b[i]-b[i-1],1,i));
	ll ans = 0;
	int cx = n-1,cy = m-1;
	
	while(cx && cy){
		auto ith = h.end();
		auto itw = w.end();
		ith--;
		itw--;
		//cout<<ith->x<<" "<<ith->y<<" "<<ith->id<<" "<<ans<<'\n';
		//cout<<itw->x<<" "<<itw->y<<" "<<itw->id<<" "<<ans<<'\n';
		if(*itw < *ith){
			pt v = *ith;	
			h.erase(ith);
			auto it = row.lb(v.id);
			int lf = -1,mid,rg = -1;
			
			mid = *it;
			if(it != row.begin()){
				it--;
				lf = *it;
				it++;
			}
			it++;
			if(it != row.end())rg = *it;
			if(lf != -1)h.erase(pt(a[mid] - a[lf],mid-lf,mid));
			if(rg != -1)h.erase(pt(a[rg] - a[mid],rg-mid,rg));
			if(lf != -1 && rg != -1)h.insert(pt(a[rg] - a[lf],rg-lf,rg));
			
			row.erase(mid);
			if(cx == mid){
				auto i = row.end();
				i--;
				ans+=(cx - *i)  * 1LL * b[cy];
				cx = *i;
			}
		
		}else{
			pt v = *itw;
			w.erase(itw);
			auto it = col.lb(v.id);
			int lf = -1,mid,rg = -1;
			
			mid = *it;
			if(it != col.begin()){
				it--;
				lf = *it;
				it++;
			}
			it++;
			if(it != col.end())rg = *it;
			if(lf != -1)w.erase(pt(b[mid] - b[lf],mid-lf,mid));
			if(rg != -1)w.erase(pt(b[rg] - b[mid],rg-mid,rg));
			if(lf != -1 && rg != -1)w.insert(pt(b[rg] - b[lf],rg-lf,rg));
			
			col.erase(mid);
			if(cy == mid){
				auto i = col.end();
				i--;
				ans+=(cy - *i)  * 1LL * a[cx];
				cy = *i;
			}
			//cout<<v.x<<" "<<v.y<<" "<<v.id<<" "<<ans<<'\n';
			//cout<<cx<<" "<<cy<<'\n';
		}
	}
	ans+=cy*a[0];
	ans+=cx*b[0];
	cout<<ans;
}

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