oj.uz

Submission #1041024

# Submission time Handle Problem Language Result Execution time Memory
1041024 2024-08-01T14:00:59 Z alexdd Road Construction (JOI21_road_construction) C++17
12 / 100
 887 ms 7608 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 4e9;
int n,cate,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.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);
    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);
    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 157 ms 5068 KB Output is correct
2 Correct 140 ms 5056 KB Output is correct
3 Correct 106 ms 5256 KB Output is correct
4 Correct 116 ms 5240 KB Output is correct
5 Correct 99 ms 3964 KB Output is correct
6 Correct 2 ms 344 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 225 ms 7608 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 129 ms 4184 KB Output is correct
2 Correct 176 ms 4348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 82 ms 4184 KB Output is correct
5 Correct 162 ms 4176 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 4184 KB Output is correct
2 Correct 176 ms 4348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 82 ms 4184 KB Output is correct
5 Correct 162 ms 4176 KB Output is correct
6 Correct 249 ms 4188 KB Output is correct
7 Correct 234 ms 4216 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 207 ms 4476 KB Output is correct
11 Correct 66 ms 4188 KB Output is correct
12 Incorrect 212 ms 4380 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 5068 KB Output is correct
2 Correct 140 ms 5056 KB Output is correct
3 Correct 106 ms 5256 KB Output is correct
4 Correct 116 ms 5240 KB Output is correct
5 Correct 99 ms 3964 KB Output is correct
6 Correct 2 ms 344 KB Output is correct
7 Correct 860 ms 6864 KB Output is correct
8 Correct 887 ms 6776 KB Output is correct
9 Correct 104 ms 5080 KB Output is correct
10 Incorrect 386 ms 6080 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 5068 KB Output is correct
2 Correct 140 ms 5056 KB Output is correct
3 Correct 106 ms 5256 KB Output is correct
4 Correct 116 ms 5240 KB Output is correct
5 Correct 99 ms 3964 KB Output is correct
6 Correct 2 ms 344 KB Output is correct
7 Incorrect 225 ms 7608 KB Output isn't correct
8 Halted 0 ms 0 KB -