| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 888265 |
2023-12-16T18:01:02 Z |
Macker |
Pairs (IOI07_pairs) |
C++17 |
|
4000 ms |
36936 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
class Seg{
vector<ll> st;
int len = 1;
public:
Seg(int n){
while(len < n) len *= 2;
st.resize(len * 2, 0);
}
void add(int idx, ll val, int i, int s, int e){
if(idx < s || idx >= e) return;
if(idx == s && s + 1 == e){
st[i] += val;
return;
}
add(idx, val, i * 2, s, (s + e) / 2);
add(idx, val, i * 2 + 1, (s + e) / 2, e);
st[i] = st[i * 2] + st[i * 2 + 1];
}
void add(int idx, ll val){
add(idx, val, 1, 0, len);
}
ll qry(int l, int r, int i, int s, int e){
if(l >= e || s >= r) return 0;
if(l <= s && e <= r) return st[i];
return qry(l, r, i * 2, s, (s + e) / 2) + qry(l, r, i * 2 + 1, (s + e) / 2, e);
}
ll qry(int l, int r){
return qry(l, r, 1, 0, len);
}
};
int d, m;
vector<int> coords;
int cmpr(int x){
return lower_bound(all(coords), x) - coords.begin();
}
tuple<int, int, int> cget(int x, int y){
x += m + d;
y += m + d;
if((x + y) % 2 == 1) return {1, (x + y + 1) / 2 + m + d, (x - y + 1) / 2 + m + d};
else return {0, (x + y) / 2 + m + d, (x - y) / 2 + m + d};
}
int dst(tuple<int, int, int> a, tuple<int, int, int> b){
return abs(get<0>(a) - get<0>(b))
+ abs(get<1>(a) - get<1>(b))
+ abs(get<2>(a) - get<2>(b));
}
int main()
{
int b, n; cin >> b >> n >> d >> m;
if(b == 1){
vector<pair<int, int>> q;
vector<int> ad;
for (int i = 0; i < n; i++) {
int a; cin >> a;
ad.push_back(a);
q.push_back({a - d, a + d});
coords.push_back(a);
coords.push_back(a - d);
coords.push_back(a + d);
}
sort(all(coords));
Seg st(coords.size() + 1);
for (auto &i : ad)
st.add(cmpr(i), 1);
ll res = 0;
for (auto &[f, t] : q)
res += st.qry(cmpr(f), cmpr(t) + 1) - 1;
cout << res / 2 << endl;
}
if(b == 2){
vector<array<int, 5>> evo; // t (0s, 1, 2e), y, x, xx, i
vector<array<int, 5>> eve; // t (0s, 1, 2e), y, x, xx, i
for (int i = 0; i < n; i++)
{
int sx, sy; cin >> sx >> sy;
int p, x, y; tie(p, x, y) = cget(sx, sy);
if(p == 0) eve.push_back({x, 1, y, -1, -1});
else evo.push_back({x, 1, y, -1, -1});
for (int j = 0; j < 2; j++)
{
pii up, ri, dw, lf;
up = {sx, sy + d - j};
ri = {sx + d - j, sy};
dw = {sx, sy - d + j};
lf = {sx - d + j, sy};
tie(p, up.first, up.second) = cget(up.first, up.second);
tie(p, ri.first, ri.second) = cget(ri.first, ri.second);
tie(p, dw.first, dw.second) = cget(dw.first, dw.second);
tie(p, lf.first, lf.second) = cget(lf.first, lf.second);
if(p == 0){
eve.push_back({up.first, 2, ri.second, up.second, i});
eve.push_back({dw.first, 0, dw.second, lf.second, i});
}
else{
evo.push_back({up.first, 2, ri.second, up.second, i});
evo.push_back({dw.first, 0, dw.second, lf.second, i});
}
}
}
ll res = 0;
for (auto &ev : vector<vector<array<int, 5>>>({eve, evo})) {
sort(all(ev));
Seg st(5 * m + 5 * d);
for (auto &e : ev) {
auto& [y, t, x, xx, i] = e;
if(t == 1){
st.add(x, 1);
}
if(t == 0){
res -= st.qry(xx, x + 1);
}
if(t == 2){
res += st.qry(xx, x + 1);
}
}
}
cout << (res - (ll)n) / 2LL << endl;
}
if(b == 3){
vector<tuple<int, int, int>> v(n);
for (auto &[x, y, w] : v) {
cin >> x >> y >> w;
}
ll res = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if(dst(v[i], v[j]) <= d) res++;
}
}
cout << res << endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
98 ms |
11336 KB |
Output is correct |
| 2 |
Correct |
103 ms |
11328 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
116 ms |
11480 KB |
Output is correct |
| 2 |
Correct |
124 ms |
11328 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
129 ms |
11580 KB |
Output is correct |
| 2 |
Correct |
125 ms |
11504 KB |
Output is correct |
| 3 |
Correct |
122 ms |
11496 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8796 KB |
Output is correct |
| 2 |
Correct |
5 ms |
8796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
144 ms |
29880 KB |
Output is correct |
| 2 |
Correct |
144 ms |
30196 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
160 ms |
29952 KB |
Output is correct |
| 2 |
Correct |
165 ms |
29988 KB |
Output is correct |
| 3 |
Correct |
149 ms |
29912 KB |
Output is correct |
| 4 |
Correct |
159 ms |
29948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
218 ms |
29960 KB |
Output is correct |
| 2 |
Correct |
237 ms |
36936 KB |
Output is correct |
| 3 |
Correct |
184 ms |
36316 KB |
Output is correct |
| 4 |
Correct |
182 ms |
36548 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
348 KB |
Output is correct |
| 2 |
Correct |
2 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4066 ms |
2092 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4058 ms |
2388 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4022 ms |
2216 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
