Submission #835003

#TimeUsernameProblemLanguageResultExecution timeMemory
835003CSQ31Sightseeing in Kyoto (JOI22_kyoto)C++17
30 / 100
484 ms23968 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...