Submission #907022

#	Time	Username	Problem	Language	Result	Execution time	Memory
907022		ibm2006	Road Construction (JOI21_road_construction)	C++17	27 / 100	3421 ms	2097152 KiB

road_construction

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll inf=1e18;
ll n,i,j,k,l,r,x,y,z,w,s,t,a[1100000];
pair<ll,ll> p[1100000];
vector<ll> seg1[550000],seg2[550000];
vector<ll> tmp,ans,v,u;
void add()
{
    ll i;
    tmp.clear();
    tmp.resize(22);
    fill(tmp.begin(),tmp.end(),inf);
   // printf("!");
    merge(ans.begin(),ans.end(),v.begin(),v.end(),tmp.begin());
   // printf("?");
    for(i=0;i<k;i++)
    {
        ans[i]=tmp[i];
    }
}
void f1(ll x)
{
    tmp.clear();
    tmp.resize(22);
    fill(tmp.begin(),tmp.end(),inf);
    merge(seg1[x*2].begin(),seg1[x*2].end(),seg1[x*2+1].begin(),seg1[x*2+1].end(),tmp.begin());
    ll i;
    for(i=0;i<k;i++)
    {
        seg1[x][i]=tmp[i];
    }
    if(x==1)
        return;
    f1(x/2);
}
void f2(ll x)
{
    tmp.clear();
    tmp.resize(22);
    fill(tmp.begin(),tmp.end(),inf);
    merge(seg2[x*2].begin(),seg2[x*2].end(),seg2[x*2+1].begin(),seg2[x*2+1].end(),tmp.begin());
    ll i;
    for(i=0;i<k;i++)
    {
        seg2[x][i]=tmp[i];
    }
    if(x==1)
        return;
    f2(x/2);
}
vector<ll> g1(ll x,ll y,ll z)
{
    vector<ll> cur;
    cur.resize(k);
    fill(cur.begin(),cur.end(),inf);
    if(y<l||x>r)
        return cur;
    if(l<=x&&y<=r)
        return seg1[z];
    vector<ll> v1,v2;
    v1=g1(x,(x+y)/2,z*2);
    v2=g1((x+y)/2+1,y,z*2+1);
    tmp.clear();
    tmp.resize(22);
    fill(tmp.begin(),tmp.end(),inf);
    merge(v1.begin(),v1.end(),v2.begin(),v2.end(),tmp.begin());
    ll u,i;
    for(i=0;i<k;i++)
    {
        cur[i]=tmp[i];
    }
    return cur;
}
vector<ll> g2(ll x,ll y,ll z)
{
    vector<ll> cur;
    cur.resize(k);
    fill(cur.begin(),cur.end(),inf);
    if(y<l||x>r)
        return cur;
    if(l<=x&&y<=r)
        return seg2[z];
    vector<ll> v1,v2;
    v1=g2(x,(x+y)/2,z*2);
    v2=g2((x+y)/2+1,y,z*2+1);
    tmp.clear();
    tmp.resize(22);
    fill(tmp.begin(),tmp.end(),inf);
    merge(v1.begin(),v1.end(),v2.begin(),v2.end(),tmp.begin());
    ll u,i;
    for(i=0;i<k;i++)
    {
        cur[i]=tmp[i];
    }
    return cur;
}
ll tr(ll x)
{
    return lower_bound(u.begin(),u.end(),x)-u.begin()+1;
}
int main()
{
    scanf("%lld %lld",&n,&k);
    ans.resize(k);
    fill(ans.begin(),ans.end(),inf);
    for(i=1;i<=n;i++)
    {
        scanf("%lld %lld",&x,&y);
        p[i]={x,y};
        u.push_back(y);
    }
    sort(u.begin(),u.end());
    u.erase(unique(u.begin(),u.end()),u.end());
    sort(p+1,p+n+1);
   // printf("!");
    for(i=1;i<=524288;i++)
    {
        seg1[i].resize(k);
        seg2[i].resize(k);
        fill(seg1[i].begin(),seg1[i].end(),inf);
        fill(seg2[i].begin(),seg2[i].end(),inf);
    }
    for(i=1;i<=n;i++)
    {
       // printf("%lld\n",i);
        x=p[i].first;
        y=p[i].second;
        z=tr(y);
        l=z;
        r=262144;
        v=g1(1,262144,1);
        for(j=0;j<v.size();j++)
        {
            v[j]+=x-y;
        }
       // printf("?");
        add();
       // printf("!");
        l=1;
        r=z-1;
        v=g2(1,262144,1);
        for(j=0;j<v.size();j++)
        {
            v[j]+=x+y;
        }
        //printf("@");
        add();
        seg1[z+262143].push_back(y-x);
        seg2[z+262143].push_back(-y-x);
        sort(seg1[z+262143].begin(),seg1[z+262143].end());
        seg1[z+262143].erase(--seg1[z+262143].end());
        sort(seg2[z+262143].begin(),seg2[z+262143].end());
        seg2[z+262143].erase(--seg2[z+262143].end());
        f1((z+262143)/2);
        f2((z+262143)/2);
    }
    //printf("\n\n\n\n%lld\n",ans.size());
    for(i=0;i<k;i++)
    {
      //  printf("!");
        printf("%lld\n",ans[i]);
    }
}

Compilation message (stderr)

road_construction.cpp: In function 'std::vector<long long int> g1(ll, ll, ll)':
road_construction.cpp:69:8: warning: unused variable 'u' [-Wunused-variable]
   69 |     ll u,i;
      |        ^
road_construction.cpp: In function 'std::vector<long long int> g2(ll, ll, ll)':
road_construction.cpp:92:8: warning: unused variable 'u' [-Wunused-variable]
   92 |     ll u,i;
      |        ^
road_construction.cpp: In function 'int main()':
road_construction.cpp:134:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |         for(j=0;j<v.size();j++)
      |                 ~^~~~~~~~~
road_construction.cpp:144:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |         for(j=0;j<v.size();j++)
      |                 ~^~~~~~~~~
road_construction.cpp:105:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |     scanf("%lld %lld",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
road_construction.cpp:110:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         scanf("%lld %lld",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 0 / 27
• Subtask 6: 0 / 35