oj.uz

Submission #1007848

# Submission time Handle Problem Language Result Execution time Memory
1007848 2024-06-25T14:58:11 Z modwwe Road Construction (JOI21_road_construction) C++17
100 / 100
 7568 ms 34396 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];
                       while(!s.empty()) s.pop();

           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);
               while(!s.empty()) s.pop();

        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=m-v.size();i>=0;--i)
        v.pb(f);
    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:218:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  218 |         int mid=l+r>>1;
      |                 ~^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 681 ms 11208 KB Output is correct
2 Correct 675 ms 11212 KB Output is correct
3 Correct 504 ms 11332 KB Output is correct
4 Correct 486 ms 11336 KB Output is correct
5 Correct 530 ms 10060 KB Output is correct
6 Correct 12 ms 6492 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4779 ms 28500 KB Output is correct
2 Correct 4863 ms 31532 KB Output is correct
3 Correct 532 ms 11120 KB Output is correct
4 Correct 3813 ms 31268 KB Output is correct
5 Correct 4414 ms 31424 KB Output is correct
6 Correct 4256 ms 31520 KB Output is correct
7 Correct 4192 ms 30916 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2119 ms 25308 KB Output is correct
2 Correct 1048 ms 25304 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 1069 ms 25288 KB Output is correct
5 Correct 1337 ms 25304 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2119 ms 25308 KB Output is correct
2 Correct 1048 ms 25304 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 1069 ms 25288 KB Output is correct
5 Correct 1337 ms 25304 KB Output is correct
6 Correct 2077 ms 25184 KB Output is correct
7 Correct 1888 ms 25528 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1660 ms 25312 KB Output is correct
11 Correct 883 ms 25180 KB Output is correct
12 Correct 1176 ms 25168 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 681 ms 11208 KB Output is correct
2 Correct 675 ms 11212 KB Output is correct
3 Correct 504 ms 11332 KB Output is correct
4 Correct 486 ms 11336 KB Output is correct
5 Correct 530 ms 10060 KB Output is correct
6 Correct 12 ms 6492 KB Output is correct
7 Correct 3536 ms 20956 KB Output is correct
8 Correct 3301 ms 20936 KB Output is correct
9 Correct 467 ms 11200 KB Output is correct
10 Correct 2190 ms 20196 KB Output is correct
11 Correct 2566 ms 22468 KB Output is correct
12 Correct 2362 ms 22988 KB Output is correct
13 Correct 3205 ms 21708 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 681 ms 11208 KB Output is correct
2 Correct 675 ms 11212 KB Output is correct
3 Correct 504 ms 11332 KB Output is correct
4 Correct 486 ms 11336 KB Output is correct
5 Correct 530 ms 10060 KB Output is correct
6 Correct 12 ms 6492 KB Output is correct
7 Correct 4779 ms 28500 KB Output is correct
8 Correct 4863 ms 31532 KB Output is correct
9 Correct 532 ms 11120 KB Output is correct
10 Correct 3813 ms 31268 KB Output is correct
11 Correct 4414 ms 31424 KB Output is correct
12 Correct 4256 ms 31520 KB Output is correct
13 Correct 4192 ms 30916 KB Output is correct
14 Correct 2119 ms 25308 KB Output is correct
15 Correct 1048 ms 25304 KB Output is correct
16 Correct 1 ms 6488 KB Output is correct
17 Correct 1069 ms 25288 KB Output is correct
18 Correct 1337 ms 25304 KB Output is correct
19 Correct 2077 ms 25184 KB Output is correct
20 Correct 1888 ms 25528 KB Output is correct
21 Correct 1 ms 6492 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct
23 Correct 1660 ms 25312 KB Output is correct
24 Correct 883 ms 25180 KB Output is correct
25 Correct 1176 ms 25168 KB Output is correct
26 Correct 3536 ms 20956 KB Output is correct
27 Correct 3301 ms 20936 KB Output is correct
28 Correct 467 ms 11200 KB Output is correct
29 Correct 2190 ms 20196 KB Output is correct
30 Correct 2566 ms 22468 KB Output is correct
31 Correct 2362 ms 22988 KB Output is correct
32 Correct 3205 ms 21708 KB Output is correct
33 Correct 5804 ms 34248 KB Output is correct
34 Correct 7568 ms 34348 KB Output is correct
35 Correct 4243 ms 33708 KB Output is correct
36 Correct 3495 ms 34396 KB Output is correct
37 Correct 3566 ms 34356 KB Output is correct
38 Correct 4438 ms 33064 KB Output is correct