oj.uz

Submission #1041054

# Submission time Handle Problem Language Result Execution time Memory
1041054 2024-08-01T14:24:40 Z alexdd Road Construction (JOI21_road_construction) C++17
0 / 100
 279 ms 14520 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 4e9;
int n,k;
pair<int,int> p[250005];
vector<int> sol;
int afis(int lim, bool bl)
{
    int poz=1,cnt=0;
    set<pair<int,int>> s;
    for(int i=1;i<=n;i++)
    {
        while(p[i].first-p[poz].first>lim)
        {
            s.erase({p[poz].second,p[poz].first});
            poz++;
        }
        for(auto it = s.lower_bound({p[i].second-lim,-INF});it!=s.upper_bound({p[i].second+lim,INF});it++)
        {
            if(bl) sol.push_back(max(abs(p[i].first-(*it).second),abs(p[i].second-(*it).first)));
            else cnt++;
            if(cnt==k)
                return k;
        }
        s.insert({p[i].second,p[i].first});
    }
    return cnt;
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>p[i].first>>p[i].second;
        p[i] = {p[i].first+p[i].second, p[i].first-p[i].second};
    }
    sort(p+1,p+1+n);
    int st=1,dr=INF,ans=INF;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(afis(mij,0)>=k)
        {
            ans=mij;
            dr=mij-1;
        }
        else
            st=mij+1;
    }
    afis(ans,1);
    assert((int)sol.size()==k);
    sort(sol.begin(),sol.end());
    for(auto x:sol)
        cout<<x<<"\n";
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 5072 KB Output is correct
2 Correct 165 ms 4964 KB Output is correct
3 Correct 140 ms 5076 KB Output is correct
4 Correct 179 ms 5252 KB Output is correct
5 Correct 150 ms 3960 KB Output is correct
6 Runtime error 4 ms 612 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 279 ms 14520 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 7000 KB Output is correct
2 Correct 175 ms 7000 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Runtime error 95 ms 12680 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 7000 KB Output is correct
2 Correct 175 ms 7000 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Runtime error 95 ms 12680 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 5072 KB Output is correct
2 Correct 165 ms 4964 KB Output is correct
3 Correct 140 ms 5076 KB Output is correct
4 Correct 179 ms 5252 KB Output is correct
5 Correct 150 ms 3960 KB Output is correct
6 Runtime error 4 ms 612 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 5072 KB Output is correct
2 Correct 165 ms 4964 KB Output is correct
3 Correct 140 ms 5076 KB Output is correct
4 Correct 179 ms 5252 KB Output is correct
5 Correct 150 ms 3960 KB Output is correct
6 Runtime error 4 ms 612 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -