oj.uz

답안 #1041035

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1041035 2024-08-01T14:06:36 Z alexdd Road Construction (JOI21_road_construction) C++17
12 / 100
 868 ms 7580 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);
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 153 ms 5072 KB Output is correct
2 Correct 144 ms 5056 KB Output is correct
3 Correct 87 ms 5076 KB Output is correct
4 Correct 110 ms 5076 KB Output is correct
5 Correct 95 ms 4036 KB Output is correct
6 Correct 2 ms 348 KB Output is correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 220 ms 7580 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 132 ms 4348 KB Output is correct
2 Correct 183 ms 4256 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 82 ms 4228 KB Output is correct
5 Correct 176 ms 4184 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 132 ms 4348 KB Output is correct
2 Correct 183 ms 4256 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 82 ms 4228 KB Output is correct
5 Correct 176 ms 4184 KB Output is correct
6 Correct 248 ms 4176 KB Output is correct
7 Correct 238 ms 4348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 187 ms 4184 KB Output is correct
11 Correct 67 ms 4188 KB Output is correct
12 Incorrect 234 ms 4376 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 153 ms 5072 KB Output is correct
2 Correct 144 ms 5056 KB Output is correct
3 Correct 87 ms 5076 KB Output is correct
4 Correct 110 ms 5076 KB Output is correct
5 Correct 95 ms 4036 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 851 ms 6856 KB Output is correct
8 Correct 868 ms 6592 KB Output is correct
9 Correct 103 ms 5080 KB Output is correct
10 Incorrect 343 ms 6080 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 153 ms 5072 KB Output is correct
2 Correct 144 ms 5056 KB Output is correct
3 Correct 87 ms 5076 KB Output is correct
4 Correct 110 ms 5076 KB Output is correct
5 Correct 95 ms 4036 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Incorrect 220 ms 7580 KB Output isn't correct
8 Halted 0 ms 0 KB -