oj.uz

Submission #1041050

# Submission time Handle Problem Language Result Execution time Memory
1041050 2024-08-01T14:19:03 Z alexdd Road Construction (JOI21_road_construction) C++17
12 / 100
 854 ms 7516 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({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 134 ms 5076 KB Output is correct
2 Correct 136 ms 4960 KB Output is correct
3 Correct 89 ms 5248 KB Output is correct
4 Correct 112 ms 5252 KB Output is correct
5 Correct 121 ms 4032 KB Output is correct
6 Correct 3 ms 348 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 239 ms 7516 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 142 ms 4364 KB Output is correct
2 Correct 185 ms 4352 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 90 ms 4304 KB Output is correct
5 Correct 366 ms 4180 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 4364 KB Output is correct
2 Correct 185 ms 4352 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 90 ms 4304 KB Output is correct
5 Correct 366 ms 4180 KB Output is correct
6 Correct 289 ms 4344 KB Output is correct
7 Correct 250 ms 4188 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 209 ms 4364 KB Output is correct
11 Correct 74 ms 4188 KB Output is correct
12 Incorrect 510 ms 4224 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 5076 KB Output is correct
2 Correct 136 ms 4960 KB Output is correct
3 Correct 89 ms 5248 KB Output is correct
4 Correct 112 ms 5252 KB Output is correct
5 Correct 121 ms 4032 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 854 ms 6676 KB Output is correct
8 Correct 841 ms 6588 KB Output is correct
9 Correct 93 ms 5076 KB Output is correct
10 Incorrect 357 ms 5892 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 5076 KB Output is correct
2 Correct 136 ms 4960 KB Output is correct
3 Correct 89 ms 5248 KB Output is correct
4 Correct 112 ms 5252 KB Output is correct
5 Correct 121 ms 4032 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Incorrect 239 ms 7516 KB Output isn't correct
8 Halted 0 ms 0 KB -