oj.uz

Submission #698717

# Submission time Handle Problem Language Result Execution time Memory
698717 2023-02-14T08:38:15 Z vjudge1 Circle selection (APIO18_circle_selection) C++17
0 / 100
 3000 ms 1048576 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 1375 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3110 ms 1048576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1394 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3120 ms 777364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1375 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1375 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -