oj.uz

Submission #1041051

# Submission time Handle Problem Language Result Execution time Memory
1041051 2024-08-01T14:19:48 Z alexdd Road Construction (JOI21_road_construction) C++17
12 / 100
 847 ms 7692 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;
bool cmp(pair<int,int> x, pair<int,int> y)
{
    return x.first < y.first;
}
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(s.find({p[poz].second,p[poz].first}));
            poz++;
        }
        for(auto it = s.lower_bound({p[i].second-lim,-INF});it!=s.lower_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)));
            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, cmp);
    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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 5068 KB Output is correct
2 Correct 138 ms 4980 KB Output is correct
3 Correct 90 ms 5076 KB Output is correct
4 Correct 125 ms 5072 KB Output is correct
5 Correct 99 ms 4028 KB Output is correct
6 Correct 3 ms 492 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 217 ms 7692 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 135 ms 4180 KB Output is correct
2 Correct 180 ms 4184 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 89 ms 4224 KB Output is correct
5 Correct 357 ms 4376 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 4180 KB Output is correct
2 Correct 180 ms 4184 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 89 ms 4224 KB Output is correct
5 Correct 357 ms 4376 KB Output is correct
6 Correct 259 ms 4176 KB Output is correct
7 Correct 224 ms 4176 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 189 ms 4224 KB Output is correct
11 Correct 74 ms 4188 KB Output is correct
12 Incorrect 483 ms 4180 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 5068 KB Output is correct
2 Correct 138 ms 4980 KB Output is correct
3 Correct 90 ms 5076 KB Output is correct
4 Correct 125 ms 5072 KB Output is correct
5 Correct 99 ms 4028 KB Output is correct
6 Correct 3 ms 492 KB Output is correct
7 Correct 847 ms 6680 KB Output is correct
8 Correct 838 ms 6660 KB Output is correct
9 Correct 106 ms 5080 KB Output is correct
10 Incorrect 336 ms 6076 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 5068 KB Output is correct
2 Correct 138 ms 4980 KB Output is correct
3 Correct 90 ms 5076 KB Output is correct
4 Correct 125 ms 5072 KB Output is correct
5 Correct 99 ms 4028 KB Output is correct
6 Correct 3 ms 492 KB Output is correct
7 Incorrect 217 ms 7692 KB Output isn't correct
8 Halted 0 ms 0 KB -