답안 #907022

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
907022 2024-01-15T06:08:41 Z ibm2006 Road Construction (JOI21_road_construction) C++17
27 / 100
3421 ms 2097152 KB
#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

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);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1035 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 968 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1944 ms 71260 KB Output is correct
2 Correct 1898 ms 71104 KB Output is correct
3 Correct 55 ms 59988 KB Output is correct
4 Correct 341 ms 69072 KB Output is correct
5 Correct 1115 ms 71524 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1944 ms 71260 KB Output is correct
2 Correct 1898 ms 71104 KB Output is correct
3 Correct 55 ms 59988 KB Output is correct
4 Correct 341 ms 69072 KB Output is correct
5 Correct 1115 ms 71524 KB Output is correct
6 Correct 3421 ms 179880 KB Output is correct
7 Correct 3375 ms 179840 KB Output is correct
8 Correct 120 ms 125768 KB Output is correct
9 Correct 113 ms 125652 KB Output is correct
10 Correct 3338 ms 174852 KB Output is correct
11 Correct 523 ms 134848 KB Output is correct
12 Correct 1524 ms 137408 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1035 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1035 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -