oj.uz

Submission #1041044

# Submission time Handle Problem Language Result Execution time Memory
1041044 2024-08-01T14:13:30 Z alexdd Road Construction (JOI21_road_construction) C++17
12 / 100
 3935 ms 7684 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++)
        for(auto it = s.begin();it!=s.end();it++)
        {
            if((*it).first < p[i].second-lim || (*it).first > p[i].second+lim)
                continue;
            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);
    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 79 ms 5164 KB Output is correct
2 Correct 78 ms 5052 KB Output is correct
3 Correct 59 ms 5076 KB Output is correct
4 Correct 57 ms 5076 KB Output is correct
5 Correct 61 ms 4036 KB Output is correct
6 Correct 5 ms 348 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 199 ms 7684 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 132 ms 4188 KB Output is correct
2 Correct 179 ms 4176 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 83 ms 4348 KB Output is correct
5 Correct 1158 ms 4384 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 4188 KB Output is correct
2 Correct 179 ms 4176 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 83 ms 4348 KB Output is correct
5 Correct 1158 ms 4384 KB Output is correct
6 Correct 286 ms 4212 KB Output is correct
7 Correct 255 ms 4260 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 194 ms 4356 KB Output is correct
11 Correct 67 ms 4188 KB Output is correct
12 Incorrect 1596 ms 4348 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 5164 KB Output is correct
2 Correct 78 ms 5052 KB Output is correct
3 Correct 59 ms 5076 KB Output is correct
4 Correct 57 ms 5076 KB Output is correct
5 Correct 61 ms 4036 KB Output is correct
6 Correct 5 ms 348 KB Output is correct
7 Correct 3848 ms 6676 KB Output is correct
8 Correct 3935 ms 6660 KB Output is correct
9 Correct 57 ms 5080 KB Output is correct
10 Incorrect 477 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 79 ms 5164 KB Output is correct
2 Correct 78 ms 5052 KB Output is correct
3 Correct 59 ms 5076 KB Output is correct
4 Correct 57 ms 5076 KB Output is correct
5 Correct 61 ms 4036 KB Output is correct
6 Correct 5 ms 348 KB Output is correct
7 Incorrect 199 ms 7684 KB Output isn't correct
8 Halted 0 ms 0 KB -