| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 333241 |
2020-12-05T04:12:25 Z |
CodeTiger927 |
Pairs (IOI07_pairs) |
C++14 |
|
4000 ms |
524292 KB |
using namespace std;
#include <iostream>
int B,D,N,M;
struct node1d {
int v;
node1d *c[2];
node1d() {
v = 0;
c[0] = nullptr;
c[1] = nullptr;
}
void upd(int l,int r,int x,int v) {
this -> v += v;
if(l != r) {
int m = (l + r) >> 1;
if(x <= m) {
if(!c[0]) c[0] = new node1d();
c[0] -> upd(l,m,x,v);
}else{
if(!c[1]) c[1] = new node1d();
c[1] -> upd(m + 1,r,x,v);
}
}
}
int qry(int l,int r,int x,int y) {
if(x <= l && r <= y) return v;
if(y < l || x > r) return 0;
int res = 0;
int m = (l + r) >> 1;
if(c[0]) res += c[0] -> qry(l,m,x,y);
if(c[1]) res += c[1] -> qry(m + 1,r,x,y);
return res;
}
};
struct node2d {
node1d* v;
node2d *c[2];
node2d() {
if(B == 3) {
v = new node1d();
}else{
v = new node1d();
}
c[0] = nullptr;
c[1] = nullptr;
}
void upd(int l,int r,int x,int y,int v) {
this -> v -> upd(0,2 * M,y,v);
if(l != r) {
int m = (l + r) >> 1;
if(x <= m) {
if(!c[0]) c[0] = new node2d();
c[0] -> upd(l,m,x,y,v);
}else{
if(!c[1]) c[1] = new node2d();
c[1] -> upd(m + 1,r,x,y,v);
}
}
}
int qry(int l,int r,int x1,int x2,int y1,int y2) {
if(x1 <= l && r <= x2) return v -> qry(0,2 * M,y1,y2);
if(x2 < l || x1 > r) return 0;
int res = 0;
int m = (l + r) >> 1;
if(c[0]) res += c[0] -> qry(l,m,x1,x2,y1,y2);
if(c[1]) res += c[1] -> qry(m + 1,r,x1,x2,y1,y2);
return res;
}
};
int main() {
scanf("%d %d %d %d",&B,&N,&D,&M);
long long ans = 0;
if(B == 1) {
node1d* st = new node1d();
for(int i = 0;i < N;++i) {
int a;
scanf("%d",&a);
ans += st -> qry(0,M,max(0,a - D),a + D);
st -> upd(0,M,a,1);
}
}else if(B == 2) {
node2d* st = new node2d();
for(int i = 0;i < N;++i) {
int c,d;
scanf("%d %d",&c,&d);
int a = (c + d);
int b = (c - d) + M;
ans += st -> qry(0,2 * M,max(0,a - D),a + D,max(0,b - D),b + D);
st -> upd(0,2 * M,a,b,1);
}
}else{
node2d* st[80];
for(int i = 0;i <= M;++i) {
st[i] = new node2d();
}
for(int i = 0;i < N;++i) {
int d,e,f;
scanf("%d %d %d",&d,&e,&f);
int a = (d + e);
int b = (d - e) + M;
int c = f;
// cout << a << " " << b << " " << c << endl;
for(int j = 0;j <= M;++j) {
int curD = D - abs(c - j);
if(curD < 0) continue;
ans += st[j] -> qry(0,2 * M,max(0,a - curD),a + curD,max(0,b - curD),b + curD);
}
st[c] -> upd(0,2 * M,a,b,1);
}
}
printf("%lld\n",ans);
return 0;
}
Compilation message
pairs.cpp: In function 'int main()':
pairs.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
76 | scanf("%d %d %d %d",&B,&N,&D,&M);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp:82:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
82 | scanf("%d",&a);
| ~~~~~^~~~~~~~~
pairs.cpp:90:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
90 | scanf("%d %d",&c,&d);
| ~~~~~^~~~~~~~~~~~~~~
pairs.cpp:103:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
103 | scanf("%d %d %d",&d,&e,&f);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
364 KB |
Output is correct |
| 2 |
Correct |
23 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
202 ms |
33516 KB |
Output is correct |
| 2 |
Correct |
107 ms |
33516 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
192 ms |
33516 KB |
Output is correct |
| 2 |
Correct |
95 ms |
6636 KB |
Output is correct |
| 3 |
Correct |
53 ms |
1516 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
9068 KB |
Output is correct |
| 2 |
Correct |
17 ms |
9068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
150 ms |
2668 KB |
Output is correct |
| 2 |
Correct |
86 ms |
2668 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1077 ms |
67308 KB |
Output is correct |
| 2 |
Correct |
866 ms |
67180 KB |
Output is correct |
| 3 |
Correct |
656 ms |
34796 KB |
Output is correct |
| 4 |
Correct |
672 ms |
53520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2840 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
2156 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2156 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
76 ms |
620 KB |
Output is correct |
| 2 |
Correct |
256 ms |
624 KB |
Output is correct |
| 3 |
Correct |
49 ms |
620 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3138 ms |
32952 KB |
Output is correct |
| 2 |
Execution timed out |
4081 ms |
23020 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4021 ms |
32580 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
