oj.uz

Submission #1007844

# Submission time Handle Problem Language Result Execution time Memory
1007844 2024-06-25T14:51:00 Z modwwe Road Construction (JOI21_road_construction) C++17
12 / 100
 4613 ms 30632 KB 
//https://www.instagram.com/_modwwe/
#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2")
#include<bits/stdc++.h>
#define int long long
//#define ll long long
#define down cout<<'\n';
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
void phongbeo();
const int inf=1e18;
const int mod2=1e9+7;
const int  mod1=998244353;
struct icd
{
    int a,b;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    int a,b,c;
};
struct id
{
    int a,b,c,d;
};
struct ie
{
    int a,b,c, d,e,f;

};
int n,m,s1,s2,s4,s3,sf,k,r,mid,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,l;
int  i,s10,s12;
int el=29;
main()
{
#ifndef ONLINE_JUDGE
///     fin(task),fou(task);
#endif
    NHP;
    /// cin>>s1;
    // modwwe
    phongbeo(),down
}
int d[250001];
struct IT
{
    ib t[1000001];
    void build(int node,int l,int r)
    {
        t[node]= {inf,0};
        if(l==r) return;
        int mid=l+r>>1;
        build(node<<1,l,mid);
        build(node<<1|1,mid+1,r);
    }
    ib mer(ib a,ib b)
    {
        if(a.a<b.a) return a;
        return b;
    }
    void upd(int node,int l,int r,int l1,int x)
    {
        if(l==r)
        {
            t[node]= {x,l};
            return;
        }
        int mid=l+r>>1;
        if(l1<=mid)upd(node<<1,l,mid,l1,x);
        else  upd(node<<1|1,mid+1,r,l1,x);
        t[node]=mer(t[node<<1],t[node<<1|1]);
    }
    ib get(int node,int l,int r,int l1,int r1 )
    {
        if(l1>r1) return {inf,0};
        if(l>r1||r<l1) return {inf,0};
        if(l>=l1&&r<=r1)return t[node];
        int mid=l+r>>1;
        return mer(get(node<<1,l,mid,l1,r1),get(node<<1|1,mid+1,r,l1,r1));
    }
} st1,st2;
ib sx;
ib a[250001];
bool check(int f)
{
    dem=0;
    st1.build(1,1,n);
    st2.build(1,1,n);
    for(int i=n; i>=1; --i)
    {
        stack<ic> s;
        /// cot be hon
        sx=st1.get(1,1,n,1,a[i].b-1);
        s3=d[a[i].b];
           if(sx.a-a[i].a+s3<=f)
               s.push({1,a[i].b-1,sx.b}),dem++;
        while(!s.empty())
        {
            if(dem>=m) return 1;
            ic x=s.top();
            s.pop();
            sx=st1.get(1,1,n,x.a,x.c-1);
            if(sx.a-a[i].a+s3<=f)dem++,s.push({x.a,x.c-1,sx.b});
            sx=st1.get(1,1,n,x.c+1,x.b);
            if(sx.a-a[i].a+s3<=f)dem++,s.push({x.c+1,x.b,sx.b});
        }
        if(dem>=m) return 1;
        sx=st2.get(1,1,n,a[i].b+1,n);
        if(sx.a-a[i].a-s3<=f)
            s.push({a[i].b+1,n,sx.b}),dem++;
        while(!s.empty())
        {
            if(dem>=m) return 1;
            ic x=s.top();
            s.pop();
            sx=st2.get(1,1,n,x.a,x.c-1);
            if(sx.a-a[i].a-s3<=f) dem++,s.push({x.a,x.c-1,sx.b});
            sx=st2.get(1,1,n,x.c+1,x.b);
            if(sx.a-a[i].a-s3<=f)dem++,s.push({x.c+1,x.b,sx.b});
        }
        if(dem>=m) return 1;
        st1.upd(1,1,n,a[i].b,a[i].a-s3);
        st2.upd(1,1,n,a[i].b,a[i].a+s3);
    }
    if(dem>=m) return 1;
    return 0;
}
vector<int> v;
void answer(int f)
{
    dem=0;
    st1.build(1,1,n);
    st2.build(1,1,n);
    for(int i=n; i>=1; --i)
    {
        stack<ic> s;
        sx=st1.get(1,1,n,1,a[i].b-1);
        s3=d[a[i].b];
           if(sx.a-a[i].a+s3<=f){
               s.push({1,a[i].b-1,sx.b}),dem++,v.pb(sx.a-a[i].a+s3);
               }
        while(!s.empty())
        {
            if(dem>=m) break;
            ic x=s.top();
            s.pop();
            sx=st1.get(1,1,n,x.a,x.c-1);
            if(sx.a-a[i].a+s3<=f)dem++,s.push({x.a,x.c-1,sx.b}),v.pb(sx.a-a[i].a+s3);
            sx=st1.get(1,1,n,x.c+1,x.b);
            if(sx.a-a[i].a+s3<=f)dem++,s.push({x.c+1,x.b,sx.b}),v.pb(sx.a-a[i].a+s3);
            }
        if(dem>=m)break;
        sx=st2.get(1,1,n,a[i].b+1,n);

        if(sx.a-a[i].a-s3<=f){
            s.push({a[i].b+1,n,sx.b}),dem++,v.pb(sx.a-a[i].a-s3);
           // cout<<sx.a-a[i].a-s3<<" "<<i<<" "<<sx.a,down
            }
        while(!s.empty())
        {
            if(dem>=m) break;
            ic x=s.top();
            s.pop();
            sx=st2.get(1,1,n,x.a,x.c-1);
            if(sx.a-a[i].a-s3<=f) dem++,s.push({x.a,x.c-1,sx.b}),v.pb(sx.a-a[i].a-s3);
            sx=st2.get(1,1,n,x.c+1,x.b);
            if(sx.a-a[i].a-s3<=f)dem++,s.push({x.c+1,x.b,sx.b}),v.pb(sx.a-a[i].a-s3);
        }
        if(dem>=m) break;
        st1.upd(1,1,n,a[i].b,a[i].a-s3);
        st2.upd(1,1,n,a[i].b,a[i].a+s3);
    }
   sort(v.begin(),v.end());
    for(int i=0; i<m; i++)
        cout<<v[i],down
    }
    bool cmp2(ib x,ib y)
    {
        return x.b<y.b;
    }
    bool cmp(ib a,ib b)
    {
        return a.a<b.a;
    }
void phongbeo()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        cin>>a[i].a>>a[i].b;
    sort(a+1,a+1+n,cmp2);
    for(int i=1; i<=n; i++)
        d[i]=a[i].b,
             a[i].b=i;

    sort(a+1,a+1+n,cmp);
    l=0;
    r=4e9;
    while(l<=r)
    {
        int mid=l+r>>1;
        if(check(mid))
        {
            mx=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
   answer(mx);
}

Compilation message

road_construction.cpp:47:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   47 | main()
      | ^~~~
road_construction.cpp: In member function 'void IT::build(long long int, long long int, long long int)':
road_construction.cpp:65:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |         int mid=l+r>>1;
      |                 ~^~
road_construction.cpp: In member function 'void IT::upd(long long int, long long int, long long int, long long int, long long int)':
road_construction.cpp:81:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |         int mid=l+r>>1;
      |                 ~^~
road_construction.cpp: In member function 'ib IT::get(long long int, long long int, long long int, long long int, long long int)':
road_construction.cpp:91:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |         int mid=l+r>>1;
      |                 ~^~
road_construction.cpp: In function 'void phongbeo()':
road_construction.cpp:213:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  213 |         int mid=l+r>>1;
      |                 ~^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 670 ms 11204 KB Output is correct
2 Correct 670 ms 11200 KB Output is correct
3 Correct 473 ms 11208 KB Output is correct
4 Correct 478 ms 11200 KB Output is correct
5 Correct 500 ms 10056 KB Output is correct
6 Correct 13 ms 6492 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 4613 ms 28504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1931 ms 25308 KB Output is correct
2 Correct 865 ms 30292 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 949 ms 28244 KB Output is correct
5 Correct 1155 ms 30632 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1931 ms 25308 KB Output is correct
2 Correct 865 ms 30292 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 949 ms 28244 KB Output is correct
5 Correct 1155 ms 30632 KB Output is correct
6 Correct 2070 ms 30380 KB Output is correct
7 Correct 1912 ms 30240 KB Output is correct
8 Correct 1 ms 6488 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1642 ms 30520 KB Output is correct
11 Correct 796 ms 28240 KB Output is correct
12 Incorrect 1042 ms 30632 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 670 ms 11204 KB Output is correct
2 Correct 670 ms 11200 KB Output is correct
3 Correct 473 ms 11208 KB Output is correct
4 Correct 478 ms 11200 KB Output is correct
5 Correct 500 ms 10056 KB Output is correct
6 Correct 13 ms 6492 KB Output is correct
7 Correct 3253 ms 20960 KB Output is correct
8 Correct 3378 ms 20928 KB Output is correct
9 Correct 445 ms 11352 KB Output is correct
10 Incorrect 2217 ms 20164 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 670 ms 11204 KB Output is correct
2 Correct 670 ms 11200 KB Output is correct
3 Correct 473 ms 11208 KB Output is correct
4 Correct 478 ms 11200 KB Output is correct
5 Correct 500 ms 10056 KB Output is correct
6 Correct 13 ms 6492 KB Output is correct
7 Incorrect 4613 ms 28504 KB Output isn't correct
8 Halted 0 ms 0 KB -