| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 216100 |
2020-03-26T17:44:29 Z |
tatyam |
Pairs (IOI07_pairs) |
C++17 |
|
1068 ms |
175020 KB |
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using ll = long long;
#define all(a) begin(a), end(a)
#define each(i,a) for(auto&& i : a)
#define overload3(_1, _2, _3, name, ...) name
#define rep1(n) for(int i = 0; i < (n); i++)
#define rep2(i, n) for(int i = 0; i < (n); i++)
#define rep3(i, a, b) for(int i = (a); i < (b); i++)
#define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
template<class T, class U> bool chmin(T& a, const U& b){ if(a > b){ a = b; return 1; } return 0; }
template<class T, class U> bool chmax(T& a, const U& b){ if(a < b){ a = b; return 1; } return 0; }
struct SegTree1{
static constexpr int size = 225;
int data[size * 2];
void add(int x, int val){
do{
data[x] += val;
}while(x /= 2);
}
int get(int x1, int x2){
int ans = 0;
for(; x1 < x2; x1 /= 2, x2 /= 2){
if(x1 & 1) ans += data[x1++];
if(x2 & 1) ans += data[--x2];
}
return ans;
}
};
struct SegTree2{
static constexpr int size = 225;
SegTree1 data[size * 2];
void add(int x, int y, int val){
do{
data[x].add(y, val);
}while(x /= 2);
}
int get(int x1, int x2, int y1, int y2){
int ans = 0;
for(; x1 < x2; x1 /= 2, x2 /= 2){
if(x1 & 1) ans += data[x1++].get(y1, y2);
if(x2 & 1) ans += data[--x2].get(y1, y2);
}
return ans;
}
};
struct SegTree3{
static constexpr int size = 225;
SegTree2 data[size * 2];
void add(int x, int y, int z, int val){
x += size;
y += size;
z += size;
do{
data[x].add(y, z, val);
}while(x /= 2);
}
int get(int x1, int x2, int y1, int y2, int z1, int z2){
chmax(x1, 0);
chmin(x2, size);
chmax(y1, 0);
chmin(y2, size);
chmax(z1, 0);
chmin(z2, size);
x1 += size;
x2 += size;
y1 += size;
y2 += size;
z1 += size;
int ans = 0;
z2 += size;
for(; x1 < x2; x1 /= 2, x2 /= 2){
if(x1 & 1) ans += data[x1++].get(y1, y2, z1, z2);
if(x2 & 1) ans += data[--x2].get(y1, y2, z1, z2);
}
return ans;
}
};
struct SegTree{
static constexpr int size = 150000;
int data[size * 2];
void add(int x, int val){
if(0 <= x && x < size) abort();
x += size;
do{
data[x] += val;
}while(x /= 2);
}
int get(int x1, int x2){
chmax(x1, 0);
chmin(x2, size);
if(0 > x2 && x1 >= size) abort();
x1 += size;
x2 += size;
int ans = 0;
for(; x1 < x2; x1 /= 2, x2 /= 2){
if(x1 & 1) ans += data[x1++];
if(x2 & 1) ans += data[--x2];
}
return ans;
}
};
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
int b, n, d, m;
cin >> b >> n >> d >> m;
ll ans = 0;
if(b == 1){
vector<int> a(n);
each(i, a) cin >> i;
sort(all(a));
int min = 0;
rep(n){
while(a[i] - a[min] > d) min++;
ans += i - min;
}
}
else if(b == 2){
vector<array<int, 2>> a(n);
each(i, a){
cin >> i[0] >> i[1];
i[0]--; i[1]--;
}
each(i, a) i = {i[0] + i[1], i[0] - i[1] + 74999};
sort(all(a));
SegTree seg;
int min = 0;
rep(n){
while(a[i][0] - a[min][0] > d){
seg.add(a[min][1], -1);
min++;
}
ans += seg.get(a[i][1] - d, a[i][1] + d + 1);
seg.add(a[i][1], 1);
}
}
else{
vector<array<int, 4>> a(n);
each(i, a){
cin >> i[0] >> i[1] >> i[2];
i[0]--; i[1]--; i[2]--;
}
each(i, a) i = {i[0] + i[1] + i[2], -i[0] + i[1] + i[2] + 74, i[0] - i[1] + i[2] + 74, i[0] + i[1] - i[2] + 74};
sort(all(a));
static SegTree3 seg;
int min = 0;
rep(n){
while(a[i][0] - a[min][0] > d){
seg.add(a[min][1], a[min][2], a[min][3], -1);
min++;
}
ans += seg.get(a[i][1] - d, a[i][1] + d + 1, a[i][2] - d, a[i][2] + d + 1, a[i][3] - d, a[i][3] + d + 1);
seg.add(a[i][1], a[i][2], a[i][3], 1);
}
}
cout << ans << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
768 KB |
Output is correct |
| 2 |
Correct |
18 ms |
768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
768 KB |
Output is correct |
| 2 |
Correct |
26 ms |
768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
768 KB |
Output is correct |
| 2 |
Correct |
28 ms |
768 KB |
Output is correct |
| 3 |
Correct |
28 ms |
768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
20 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
46 ms |
2144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
46 ms |
2040 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
61 ms |
2168 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
70392 KB |
Output is correct |
| 2 |
Correct |
40 ms |
70400 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
255 ms |
7416 KB |
Output is correct |
| 2 |
Correct |
244 ms |
7416 KB |
Output is correct |
| 3 |
Correct |
204 ms |
7648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
692 ms |
117236 KB |
Output is correct |
| 2 |
Correct |
804 ms |
117308 KB |
Output is correct |
| 3 |
Correct |
489 ms |
117368 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1020 ms |
174968 KB |
Output is correct |
| 2 |
Correct |
1068 ms |
174864 KB |
Output is correct |
| 3 |
Correct |
622 ms |
175020 KB |
Output is correct |
