Submission #943594

#	Time	Username	Problem	Language	Result	Execution time	Memory
943594		andrei_boaca	Sightseeing in Kyoto (JOI22_kyoto)	C++17	100 / 100	1242 ms	35416 KiB

kyoto

#include <bits/stdc++.h>

using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
ll n,m;
ll A[100005],B[100005];
set<ll> lines,cols;
auto comp = [](vector<ll> a, vector<ll> b)
{
    if(a[0]*b[1]!=a[1]*b[0])
        return a[0]*b[1]<a[1]*b[0];
    if(a[0]!=b[0])
        return a[0]<b[0];
    if(a[1]!=b[1])
        return a[1]<b[1];
    if(a[2]!=b[2])
        return a[2]<b[2];
    return a[3]<b[3];
};
multiset<vector<ll>,decltype(comp)> setik(comp); /// 0 -> linie, 1 -> coloana
pll getval(ll a,ll b)
{
    //assert(b!=0);
    /*if(a==0)
        return {0,1};
    ll g=__gcd(a,b);
    a/=g;
    b/=g;*/
    return {a,b};
}
void elimlin(ll poz)
{
    auto it=lines.find(poz);
    ll st=0,dr=0;
    if(it!=lines.begin())
        st=*prev(it);
    it++;
    if(it!=lines.end())
    {
        dr=(*it);
        //assert(dr>poz);
    }
    lines.erase(poz);
    if(st!=0)
    {
        bool prost=0;
        if(st>=poz)
            prost=1;
        //assert(poz>st);
        pll val=getval(A[poz]-A[st],poz-st);
        setik.erase({val.first,val.second,poz,0});
    }
    if(dr!=0)
    {
        //assert(poz<dr);
        pll val=getval(A[dr]-A[poz],dr-poz);
        setik.erase({val.first,val.second,dr,0});
    }
    if(st!=0&&dr!=0)
    {
        //assert(st<dr);
        pll val=getval(A[dr]-A[st],dr-st);
        setik.insert({val.first,val.second,dr,0});
    }
}
void elimcol(ll poz)
{
    bool ok=0;
    if(poz==450)
    {
        //cout<<"a trecut pe aici\n";
        ok=1;
    }
    auto it=cols.find(poz);
    ll st=0,dr=0;
    if(it!=cols.begin())
        st=*prev(it);
    it++;
    if(it!=cols.end())
    {
        dr=(*it);
        //assert(dr>poz);
    }
    cols.erase(poz);
    if(st!=0)
    {
        bool prost=0;
        if(st>=poz)
            prost=1;
        //assert(st<poz);
        pll val=getval(B[poz]-B[st],poz-st);
        setik.erase({val.first,val.second,poz,1});
    }
    if(dr!=0)
    {
        //assert(dr>poz);
        pll val=getval(B[dr]-B[poz],dr-poz);
        setik.erase({val.first,val.second,dr,1});
    }
    if(st!=0&&dr!=0)
    {
        //assert(st<dr);
        pll val=getval(B[dr]-B[st],dr-st);
        setik.insert({val.first,val.second,dr,1});
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>A[i];
        lines.insert(i);
    }
    for(int i=1;i<=m;i++)
    {
        cin>>B[i];
        cols.insert(i);
    }
    ll cnt=2;
    ll x=n;
    ll y=m;
    for(int i=2;i<=n;i++)
    {
        bool ok=0;
        if(i==305)
            ok=1;
        vector<ll> v={A[i]-A[i-1],1,i,0};
        ll val=v[2];
        setik.insert({A[i]-A[i-1],1,i,0});
        //cout<<i<<": "<<setik.count({33,1,306,0})<<'\n';
    }
    //return 0;
    for(int i=2;i<=m;i++)
        setik.insert({B[i]-B[i-1],1,i,1});
    ll ans=0;
    while(lines.size()>=2||cols.size()>=2)
    {
        bool ok=0;
        int lg=(int)lines.size()+(int)cols.size()-2;
        int L=setik.size();
        if(setik.size()!=(int)lines.size()+(int)cols.size()-2)
            ok=1;
        assert(!setik.empty());
        auto it=prev(setik.end());
        if((*it)[3]==0) /// linie
        {
            ll poz=(*it)[2];
            if(poz==x)
                cnt--;
            if(cnt==0)
            {
                ll aux=*prev(cols.end());
                ans+=(y-aux)*A[poz];
                y=aux;
                cnt=1;
            }
            elimlin(poz);
        }
        else /// coloana
        {
            ll poz=(*it)[2];
            if(poz==y)
                cnt--;
            if(cnt==0)
            {
                ll aux=*prev(lines.end());
                ans+=(x-aux)*B[poz];
                x=aux;
                cnt=1;
            }
            elimcol(poz);
        }
    }
    ans+=(x-1)*B[1]+(y-1)*A[1];
    cout<<ans;
    return 0;
}

Compilation message (stderr)

kyoto.cpp: In function 'void elimlin(ll)':
kyoto.cpp:50:14: warning: variable 'prost' set but not used [-Wunused-but-set-variable]
   50 |         bool prost=0;
      |              ^~~~~
kyoto.cpp: In function 'void elimcol(ll)':
kyoto.cpp:91:14: warning: variable 'prost' set but not used [-Wunused-but-set-variable]
   91 |         bool prost=0;
      |              ^~~~~
kyoto.cpp:72:10: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   72 |     bool ok=0;
      |          ^~
kyoto.cpp: In function 'int main()':
kyoto.cpp:131:14: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
  131 |         bool ok=0;
      |              ^~
kyoto.cpp:135:12: warning: unused variable 'val' [-Wunused-variable]
  135 |         ll val=v[2];
      |            ^~~
kyoto.cpp:148:24: warning: comparison of integer expressions of different signedness: 'std::multiset<std::vector<long long int>, <lambda(std::vector<long long int>, std::vector<long long int>)> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  148 |         if(setik.size()!=(int)lines.size()+(int)cols.size()-2)
      |            ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
kyoto.cpp:145:14: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
  145 |         bool ok=0;
      |              ^~
kyoto.cpp:146:13: warning: unused variable 'lg' [-Wunused-variable]
  146 |         int lg=(int)lines.size()+(int)cols.size()-2;
      |             ^~
kyoto.cpp:147:13: warning: unused variable 'L' [-Wunused-variable]
  147 |         int L=setik.size();
      |             ^

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