Submission #698717

#	Time	Username	Problem	Language	Result	Execution time	Memory
698717		vjudge1	Circle selection (APIO18_circle_selection)	C++17	0 / 100	3120 ms	1048576 KiB

circle_selection

#include <bits/stdc++.h>
#define endl '\n'
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define int ll
#define all(vec) vec.begin(), vec.end()
typedef long long ll;
using namespace std;
const int N = 3e5 + 10, mod = 1e9 + 7;
unordered_map<int, vector<int> > st, en;
vector<pair<int, pair<int, int> > > v;
int n, ans[N];
signed main()
{
    FAST;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int x, y, r;
        cin >> x >> y >> r;
        st[x - r].push_back(i);
        en[x + r].push_back(i);
        v.push_back({2 * r, {x - r, i}});
    }
    sort(all(v));
    reverse(all(v));
    for(auto it : v) {
        for(int i = it.second.first; i <= it.second.first + it.first; i++) {
            for(auto j : st[i]) if(!ans[j]) ans[j] = it.second.second;
            st[i].clear();
            for(auto j : en[i]) if(!ans[j]) ans[j] = it.second.second;
            en[i].clear();
        }
        if(!ans[it.second.second]) ans[it.second.second] = it.second.second;
    }
    for(int i = 1; i <= n; i++) cout << ans[i] << ' ';
    cout << endl;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13