| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 157737 |
2019-10-12T19:12:42 Z |
stefdasca |
Pairs (IOI07_pairs) |
C++14 |
|
3817 ms |
319872 KB |
#include<bits/stdc++.h>
using namespace std;
int tip, n, d, m;
long long ans;
struct tp
{
int x, y, z;
};
tp vv[100002], vv2[100002];
void solvesmall()
{
for(int i = 1; i <= n; ++i)
{
cin >> vv[i].x;
if(tip >= 2)
cin >> vv[i].y;
if(tip >= 3)
cin >> vv[i].z;
}
for(int i = 1; i <= n; ++i)
for(int j = i+1; j <= n; ++j)
{
int dd = abs(vv[i].x - vv[j].x) + abs(vv[i].y - vv[j].y) + abs(vv[i].z - vv[j].z);
if(dd <= d)
++ans;
}
cout << ans << '\n';
}
int v[100002];
void solve1()
{
for(int i = 1; i <= n; ++i)
cin >> v[i];
sort(v+1, v+n+1);
for(int i = 1; i <= n; ++i)
{
int sm = i;
int st = 1;
int dr = i-1;
while(st <= dr)
{
int mid = (st + dr) / 2;
if(v[i] - v[mid] <= d)
sm = mid, dr = mid - 1;
else
st = mid + 1;
}
ans += (i - sm);
}
cout << ans << '\n';
}
pair<int, int> nr[100002];
int aib[401][200002];
vector<int>coord[150002];
void upd(int bu, int pz, int val)
{
aib[bu][pz] += val;
}
int compute(int bu, int pz)
{
pz = max(pz, 0);
pz = min(pz, 200000);
return aib[bu][pz];
}
int cb(int linie, int col)
{
int ans = 0;
int st = 0;
int dr = coord[linie].size() - 1;
if(coord[linie].back() <= col)
return coord[linie].size();
if(coord[linie][0] > col)
return 0;
while(st <= dr)
{
int mid = (st + dr) / 2;
if(coord[linie][mid] <= col)
ans = (mid + 1), st = mid + 1;
else
dr = mid - 1;
}
return ans;
}
void solve2()
{
int buk = 400;
for(int i = 1; i <= n; ++i)
{
int x, y;
cin >> x >> y;
nr[i].first = x + y;
nr[i].second = x - y + 100000;
coord[nr[i].first].push_back(nr[i].second);
int nrbuk = nr[i].first / buk + (nr[i].first % buk > 0);
upd(nrbuk, nr[i].second, 1);
}
for(int i = 1; i <= 400; ++i)
for(int j = 1; j <= 200000; ++j)
aib[i][j] += aib[i][j-1];
for(int i = 0; i <= 150000; ++i)
sort(coord[i].begin(), coord[i].end());
for(int i = 1; i <= n; ++i)
{
int st = max(1, nr[i].first - d);
int sf = min(150000, nr[i].first + d);
int nrbuk = st / buk + (st % buk > 0);
--ans;
while(st <= sf && st <= nrbuk * buk)
{
if(!coord[st].empty())
ans += cb(st, nr[i].second + d) - cb(st, nr[i].second - d - 1);
++st;
}
while(st + buk - 1 <= sf)
{
nrbuk = st / buk + (st % buk > 0);
ans += compute(nrbuk, nr[i].second + d) - compute(nrbuk, nr[i].second - d - 1);
st += buk;
}
while(st <= sf)
{
if(!coord[st].empty())
ans += cb(st, nr[i].second + d) - cb(st, nr[i].second - d - 1);
++st;
}
}
cout << ans / 2 << '\n';
}
int is[80][80][80];
int sp[80][80][80];
void solve3()
{
for(int i = 1; i <= n; ++i)
cin >> vv[i].x >> vv[i].y >> vv[i].z, is[vv[i].x][vv[i].y][vv[i].z]++;
for(int i = 1; i <= 75; ++i)
for(int j = 1; j <= 75; ++j)
for(int x = 1; x <= 75; ++x)
sp[i][j][x] = sp[i][j][x-1] + is[i][j][x];
for(int i = 1; i <= n; ++i)
{
--ans;
for(int x = 1; x <= 75; ++x)
{
if(abs(vv[i].x - x) > d)
continue;
for(int y = 1; y <= 75; ++y)
{
int rem = d - abs(vv[i].x - x) - abs(vv[i].y - y);
if(rem >= 0)
ans = ans + sp[x][y][min(75, vv[i].z + rem)] - sp[x][y][max(0, vv[i].z - rem - 1)];
}
}
}
cout << ans/2 << '\n';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> tip >> n >> d >> m;
if(tip == 1)
solve1();
else
if(tip == 2)
solve2();
else
if(tip == 3)
solve3();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
3832 KB |
Output is correct |
| 2 |
Correct |
5 ms |
3836 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
3960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
4216 KB |
Output is correct |
| 2 |
Correct |
26 ms |
4216 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
4316 KB |
Output is correct |
| 2 |
Correct |
31 ms |
4316 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
4216 KB |
Output is correct |
| 2 |
Correct |
35 ms |
4196 KB |
Output is correct |
| 3 |
Correct |
33 ms |
4216 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
454 ms |
317068 KB |
Output is correct |
| 2 |
Correct |
467 ms |
317000 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
665 ms |
318408 KB |
Output is correct |
| 2 |
Correct |
691 ms |
318396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2009 ms |
318448 KB |
Output is correct |
| 2 |
Correct |
2056 ms |
318584 KB |
Output is correct |
| 3 |
Correct |
2658 ms |
318508 KB |
Output is correct |
| 4 |
Correct |
2300 ms |
318484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1468 ms |
319872 KB |
Output is correct |
| 2 |
Correct |
2114 ms |
319868 KB |
Output is correct |
| 3 |
Correct |
1306 ms |
318620 KB |
Output is correct |
| 4 |
Correct |
1530 ms |
318572 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
7416 KB |
Output is correct |
| 2 |
Correct |
46 ms |
7416 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
72 ms |
7640 KB |
Output is correct |
| 2 |
Correct |
242 ms |
7672 KB |
Output is correct |
| 3 |
Correct |
543 ms |
7660 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
406 ms |
9208 KB |
Output is correct |
| 2 |
Correct |
2840 ms |
9080 KB |
Output is correct |
| 3 |
Correct |
3817 ms |
9192 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1448 ms |
9680 KB |
Output is correct |
| 2 |
Correct |
3500 ms |
9720 KB |
Output is correct |
| 3 |
Correct |
3801 ms |
9704 KB |
Output is correct |
