oj.uz

Submission #45537

# Submission time Handle Problem Language Result Execution time Memory
45537 2018-04-15T08:18:44 Z dqhungdl Palembang Bridges (APIO15_bridge) C++17
22 / 100
 405 ms 31980 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair<int64_t,int64_t> ii;
int64_t k,n,Count=1;
ii tree1[200005],tree2[200005];
vector<int64_t> V,VV,mind,maxd,g[200005];
vector<ii> gg[200005];
map<int64_t,int64_t> F;

void Update1(int64_t idx,int64_t data)
{
    while(idx<=Count)
    {
        tree1[idx].first+=data;
        tree1[idx].second++;
        idx+=idx&-idx;
    }
}

ii Query1(int64_t idx)
{
    ii rs=ii(0,0);
    while(idx>0)
    {
        rs.first+=tree1[idx].first;
        rs.second+=tree1[idx].second;
        idx-=idx&-idx;
    }
    return rs;
}

void Update2(int64_t idx,int64_t data)
{
    while(idx>0)
    {
        tree2[idx].first+=data;
        tree2[idx].second++;
        idx-=idx&-idx;
    }
}

ii Query2(int64_t idx)
{
    ii rs=ii(0,0);
    while(idx<=Count)
    {
        rs.first+=tree2[idx].first;
        rs.second+=tree2[idx].second;
        idx+=idx&-idx;
    }
    return rs;
}

void Sub1()
{
    char c1,c2;
    int64_t t1,t2,sum=0;
    for(int64_t i=1;i<=n;i++)
    {
        cin>>c1>>t1>>c2>>t2;
        if(c1==c2)
            sum+=abs(t1-t2);
        else
        {
            V.push_back(t1);
            V.push_back(t2);
            mind.push_back(min(t1,t2));
            maxd.push_back(max(t1,t2));
            sum+=abs(t1-t2)+1;
        }
    }
    if(V.size()==0)
    {
        cout<<sum;
        return;
    }
    sort(V.begin(),V.end());
    F[V[0]]=1;
    for(int64_t i=1;i<V.size();i++)
        if(V[i]>V[i-1])
            F[V[i]]=++Count;
    for(int64_t i=0;i<mind.size();i++)
        Update2(F[mind[i]],mind[i]);
    for(int64_t i=0;i<maxd.size();i++)
        Update1(F[maxd[i]],maxd[i]);
    int64_t res=1e18;
    for(int64_t i=0;i<V.size();i++)
    {
        ii t1=Query1(F[V[i]]-1);
        ii t2=Query2(F[V[i]]+1);
        res=min(res,sum+2*(V[i]*t1.second-t1.first+t2.first-V[i]*t2.second));
    }
    cout<<res;
}

void Sub2()
{
    char c1,c2;
    int64_t t1,t2,sum=0;
    for(int64_t i=1;i<=n;i++)
    {
        cin>>c1>>t1>>c2>>t2;
        if(c1==c2)
            sum+=abs(t1-t2);
        else
        {
            V.push_back(t1);
            V.push_back(t2);
            mind.push_back(min(t1,t2));
            maxd.push_back(max(t1,t2));
            sum+=abs(t1-t2)+1;
        }
    }
    if(V.size()==0)
    {
        cout<<sum;
        return;
    }
    sort(V.begin(),V.end());
    F[V[0]]=1;
    VV.push_back(V[0]);
    for(int64_t i=1;i<V.size();i++)
        if(V[i]>V[i-1])
        {
            F[V[i]]=++Count;
            VV.push_back(V[i]);
        }
    V=VV;
    for(int64_t i=0;i<mind.size();i++)
        g[F[maxd[i]]].push_back(mind[i]);
    for(int64_t i=0;i<mind.size();i++)
        Update2(F[mind[i]],mind[i]);
    for(int64_t i=0;i<maxd.size();i++)
        Update1(F[maxd[i]],maxd[i]);
    int64_t res=1e18;
    for(int64_t i=0;i<V.size();i++)
    {
        ii t1=Query1(V[i]-1);
        for(int64_t j=i;j<V.size();j++)
            gg[j].clear();
        int64_t C=0,S1=0,S2=0;
        for(int64_t j=i;j<V.size();j++)
        {
            if(j>i)
                S1+=C*(V[j]-V[j-1]);
            int64_t jj=F[V[j]];
            for(int64_t t=0;t<g[jj].size();t++)
                if(g[jj][t]>=V[i])
                {
                    int64_t rs=-1,l=jj+1,r=V.size()-1;
                    while(l<=r)
                    {
                        int64_t mid=(l+r)/2;
                        if(g[jj][t]-V[i]<V[mid]-V[j])
                        {
                            rs=mid;
                            r=mid-1;
                        }
                        else
                            l=mid+1;
                    }
                    if(rs!=-1)
                        gg[rs].push_back(ii(g[jj][t],V[j]));
                    C++;
                }
            for(int64_t t=0;t<gg[jj].size();t++)
            {
                S1-=V[j]-gg[jj][t].second;
                C--;
                S2+=gg[jj][t].first-V[i];
            }
            ii t2=Query2(V[j]+1);
            res=min(res,sum+2*(V[i]*t1.second-t1.first+t2.first-V[i]*t2.second+S1+S2));
        }
    }
    cout<<res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("TEST.INP","r",stdin);
    cin>>k>>n;
    if(k==1)
        Sub1();
    else
        Sub2();
}

Compilation message

bridge.cpp: In function 'void Sub1()':
bridge.cpp:80:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int64_t i=1;i<V.size();i++)
                     ~^~~~~~~~~
bridge.cpp:83:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int64_t i=0;i<mind.size();i++)
                     ~^~~~~~~~~~~~
bridge.cpp:85:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int64_t i=0;i<maxd.size();i++)
                     ~^~~~~~~~~~~~
bridge.cpp:88:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int64_t i=0;i<V.size();i++)
                     ~^~~~~~~~~
bridge.cpp: In function 'void Sub2()':
bridge.cpp:123:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int64_t i=1;i<V.size();i++)
                     ~^~~~~~~~~
bridge.cpp:130:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int64_t i=0;i<mind.size();i++)
                     ~^~~~~~~~~~~~
bridge.cpp:132:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int64_t i=0;i<mind.size();i++)
                     ~^~~~~~~~~~~~
bridge.cpp:134:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int64_t i=0;i<maxd.size();i++)
                     ~^~~~~~~~~~~~
bridge.cpp:137:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int64_t i=0;i<V.size();i++)
                     ~^~~~~~~~~
bridge.cpp:140:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int64_t j=i;j<V.size();j++)
                         ~^~~~~~~~~
bridge.cpp:143:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int64_t j=i;j<V.size();j++)
                         ~^~~~~~~~~
bridge.cpp:148:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int64_t t=0;t<g[jj].size();t++)
                             ~^~~~~~~~~~~~~
bridge.cpp:167:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int64_t t=0;t<gg[jj].size();t++)
                             ~^~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9720 KB Output is correct
2 Correct 9 ms 9832 KB Output is correct
3 Correct 9 ms 9832 KB Output is correct
4 Correct 11 ms 10028 KB Output is correct
5 Correct 11 ms 10088 KB Output is correct
6 Correct 10 ms 10088 KB Output is correct
7 Correct 10 ms 10272 KB Output is correct
8 Correct 10 ms 10300 KB Output is correct
9 Correct 10 ms 10300 KB Output is correct
10 Correct 10 ms 10300 KB Output is correct
11 Correct 10 ms 10300 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10300 KB Output is correct
2 Correct 11 ms 10300 KB Output is correct
3 Correct 9 ms 10300 KB Output is correct
4 Correct 12 ms 10300 KB Output is correct
5 Correct 11 ms 10300 KB Output is correct
6 Correct 10 ms 10300 KB Output is correct
7 Correct 11 ms 10300 KB Output is correct
8 Correct 11 ms 10300 KB Output is correct
9 Correct 10 ms 10300 KB Output is correct
10 Correct 9 ms 10300 KB Output is correct
11 Correct 11 ms 10300 KB Output is correct
12 Correct 43 ms 14444 KB Output is correct
13 Correct 405 ms 31852 KB Output is correct
14 Correct 124 ms 31852 KB Output is correct
15 Correct 217 ms 31852 KB Output is correct
16 Correct 52 ms 31852 KB Output is correct
17 Correct 252 ms 31852 KB Output is correct
18 Correct 256 ms 31852 KB Output is correct
19 Correct 401 ms 31852 KB Output is correct
20 Correct 53 ms 31852 KB Output is correct
21 Correct 271 ms 31980 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31980 KB Output is correct
2 Correct 10 ms 31980 KB Output is correct
3 Correct 9 ms 31980 KB Output is correct
4 Runtime error 20 ms 31980 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 31980 KB Output is correct
2 Correct 9 ms 31980 KB Output is correct
3 Correct 9 ms 31980 KB Output is correct
4 Runtime error 19 ms 31980 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 31980 KB Output is correct
2 Correct 9 ms 31980 KB Output is correct
3 Correct 9 ms 31980 KB Output is correct
4 Runtime error 20 ms 31980 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -