oj.uz

답안 #1041047

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1041047 2024-08-01T14:15:18 Z alexdd Road Construction (JOI21_road_construction) C++17
12 / 100
 3966 ms 7696 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)
            if(max(abs(p[i].first-(*it).second),abs(p[i].second-(*it).first)) > 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

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 5076 KB Output is correct
2 Correct 81 ms 4980 KB Output is correct
3 Correct 59 ms 5076 KB Output is correct
4 Correct 58 ms 5256 KB Output is correct
5 Correct 62 ms 3940 KB Output is correct
6 Correct 4 ms 348 KB Output is correct

Subtask #2
0 / 6.0

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

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 134 ms 4188 KB Output is correct
2 Correct 177 ms 4176 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 82 ms 4352 KB Output is correct
5 Correct 1192 ms 4204 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 134 ms 4188 KB Output is correct
2 Correct 177 ms 4176 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 82 ms 4352 KB Output is correct
5 Correct 1192 ms 4204 KB Output is correct
6 Correct 261 ms 4440 KB Output is correct
7 Correct 265 ms 4224 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 188 ms 4192 KB Output is correct
11 Correct 65 ms 4188 KB Output is correct
12 Incorrect 1676 ms 4344 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 5076 KB Output is correct
2 Correct 81 ms 4980 KB Output is correct
3 Correct 59 ms 5076 KB Output is correct
4 Correct 58 ms 5256 KB Output is correct
5 Correct 62 ms 3940 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 3917 ms 6680 KB Output is correct
8 Correct 3966 ms 6684 KB Output is correct
9 Correct 58 ms 5080 KB Output is correct
10 Incorrect 468 ms 5892 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 5076 KB Output is correct
2 Correct 81 ms 4980 KB Output is correct
3 Correct 59 ms 5076 KB Output is correct
4 Correct 58 ms 5256 KB Output is correct
5 Correct 62 ms 3940 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Incorrect 195 ms 7696 KB Output isn't correct
8 Halted 0 ms 0 KB -