| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 585946 |
2022-06-29T15:12:47 Z |
Do_you_copy |
Pairs (IOI07_pairs) |
C++14 |
|
268 ms |
29776 KB |
#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using pii = pair <int, int>;
ll min(const ll &a, const ll &b){
return (a < b) ? a : b;
}
ll max(const ll &a, const ll &b){
return (a > b) ? a : b;
}
const ll Mod = 1000000007;
const int maxN = 1e5 + 1;
int n, d, m;
struct TPoint{
int x, y = 0, z = 0;
bool operator < (const TPoint &other){
if (x == other.x){
if (y == other.y) return z < other.z;
return y < other.y;
}
return x < other.x;
}
};
struct TPointt{
};
struct TQuery{
int x, y, t;
bool operator < (const TQuery &other){
if (x == other.x) return t < other.t;
return x < other.x;
}
};
TPoint a[maxN];
struct TQ{
int p, q, r, s, t, i;
bool operator < (const TQ &other){
if (p == other.p) return t > other.t;
return p < other.p;
}
};
struct Node{
Node *l, *r;
int val;
Node(const int &x) : l(nullptr), r(nullptr), val(0){}
};
Node* root;
int bit[230][230][226];
void updatebit(int x, int y, int z, int val){
for (int i = x; i <= 229; i += (i & -i)){
for (int j = y; j <= 229; j += (j & -j)){
for (int k = z; k <= 225; k += (k & -k)){
bit[i][j][k] += val;
}
}
}
}
int getbit(int x, int y, int z){
ll ans = 0;
x = min(x, 229);
y = min(y, 229);
z = min(z, 225);
if (x < 1 || y < 1 || z < 1) return 0;
for (int i = x; i > 0; i -= (i & -i)){
for (int j = y; j > 0; j -= (j & -j)){
for (int k = z; k > 0; k -= (k & -k)){
ans += bit[i][j][k];
}
}
}
return ans;
}
void create(Node *id){
if (!id->l){
id->l = new Node(0);
}
if (!id->r){
id->r = new Node(0);
}
}
void update(Node *id, int l, int r, int i, int x){
if (r < i || l > i) return;
if (l == r){
id->val += x;
return;
}
int m = (l + r) / 2;
create(id);
update(id->l, l, m, i, x);
update(id->r, m + 1, r, i, x);
id->val = id->l->val + id->r->val;
}
ll get(Node *id, int l, int r, int i, int j){
if (r < i || l > j) return 0;
if (i <= l && r <= j){
return id->val;
}
int m = (l + r) / 2;
create(id);
return get(id->l, l, m, i, j) + get(id->r, m + 1, r, i, j);
}
void Init(){
int type; cin >> type >> n >> d >> m;
if (type == 1){
for (int i = 1; i <= n; ++i) cin >> a[i].x;
sort(a + 1, a + n + 1);
ll ans = 0;
for (int i = 1; i <= n; ++i){
TPoint tem = {a[i].x - d, 0, 0};
int k = lower_bound(a + 1, a + n + 1, tem) - a;
ans += i - k;
}
cout << ans;
}
if (type == 2){
ll ans = 0;
vector <TQuery> v;
for (int i = 1; i <= n; ++i){
cin >> a[i].x >> a[i].y;
v.pb({a[i].x - a[i].y, a[i].x + a[i].y, 1});
v.pb({a[i].x - a[i].y + d + 1 , a[i].x + a[i].y, -1});
}
sort(v.begin(), v.end());
root = new Node(0);
for (const auto &i : v){
if (i.t == 1){
ans += get(root, 1, 150000, max(1, i.y - d), i.y + d);
}
update(root, 1, 150000, i.y, i.t);
}
cout << ans;
}
if (type == 3){
ll ans = 0;
vector <TQ> v;
for (int i = 1; i <= n; ++i){
cin >> a[i].x >> a[i].y >> a[i].z;
int p = a[i].x - a[i].y - a[i].z;
int q = a[i].x - a[i].y + a[i].z + 75;
int r = a[i].x + a[i].y - a[i].z + 75;
int s = a[i].x + a[i].y + a[i].z;
v.pb({p, q, r, s, 1, i});
v.pb({p + d + 1, q, r, s, -1, i});
}
sort(v.begin(), v.end());
for (const auto &i: v){
if (i.t == 1){
ans += getbit(i.q + d, i.r + d, i.s + d)
- getbit(i.q - d - 1, i.r + d, i.s + d)
- getbit(i.q + d, i.r - d - 1, i.s + d)
- getbit(i.q + d, i.r + d, i.s - d - 1)
+ getbit(i.q - d - 1, i.r - d - 1, i.s + d)
+ getbit(i.q - d - 1, i.r + d, i.s - d - 1)
+ getbit(i.q + d, i.r - d - 1, i.s - d - 1)
- getbit(i.q - d - 1, i.r - d - 1, i.s - d - 1);
}
updatebit(i.q, i.r, i.s, i.t);
}
cout << ans;
}
}
int main(){
if (fopen(taskname".txt", "r")){
freopen(taskname".txt", "r", stdin);
}
faster
//freopen(taskname.inp, "r", stdin)
//freopen(taskname.out, "w", stdout)
Init();
}
Compilation message
pairs.cpp: In function 'int main()':
pairs.cpp:187:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
187 | freopen(taskname".txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1504 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
1872 KB |
Output is correct |
| 2 |
Correct |
18 ms |
1876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
2348 KB |
Output is correct |
| 2 |
Correct |
23 ms |
2280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
2260 KB |
Output is correct |
| 2 |
Correct |
22 ms |
2376 KB |
Output is correct |
| 3 |
Correct |
20 ms |
2256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2388 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2388 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
87 ms |
5296 KB |
Output is correct |
| 2 |
Correct |
86 ms |
5196 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
103 ms |
5472 KB |
Output is correct |
| 2 |
Correct |
96 ms |
5452 KB |
Output is correct |
| 3 |
Correct |
95 ms |
5388 KB |
Output is correct |
| 4 |
Correct |
96 ms |
5456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
141 ms |
12856 KB |
Output is correct |
| 2 |
Correct |
149 ms |
13856 KB |
Output is correct |
| 3 |
Correct |
124 ms |
7508 KB |
Output is correct |
| 4 |
Correct |
105 ms |
7076 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
13104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
102 ms |
8420 KB |
Output is correct |
| 2 |
Incorrect |
103 ms |
8420 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
268 ms |
22308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
253 ms |
29776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
