| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 157691 |
2019-10-12T18:00:16 Z |
stefdasca |
Pairs (IOI07_pairs) |
C++14 |
|
2703 ms |
321056 KB |
#include<bits/stdc++.h>
using namespace std;
int tip, n, d, m;
long long ans;
struct tp
{
int x, y, z;
};
tp vv[10002];
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;
// for(; pz <= 200000; pz += (pz & (-pz)))
// aib[bu][pz] += val;
}
int compute(int bu, int pz)
{
pz = max(pz, 0);
pz = min(pz, 200000);
return aib[bu][pz];
int ans = 0;
for(; pz > 0; pz -= (pz & (-pz)))
ans += aib[bu][pz];
return ans;
}
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;
// x = min(i, 75000);
// y = min(i, 75000);
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];
// cout << nr[5].first << '\n';
for(int i = 0; i <= 150000; ++i)
sort(coord[i].begin(), coord[i].end());
for(int i = 1; i <= n; ++i)
{
// if(i <= 10)
// cout << nr[i].first << '\n';
int st = max(1, nr[i].first - d);
int sf = min(150000, nr[i].first + d);
int nrbuk = st / buk + (st % buk > 0);
--ans;
// if(i <= 10)
// cout << nr[i].first << " " << st << " " << buk << " " << sf << '\n';
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;
}
int gn = 0;
// if(i <= 10)
// cout << st << " " << buk << " " << sf << '\n';
while(st + buk - 1 <= sf)
{
nrbuk = st / buk + (st % buk > 0);
gn += compute(nrbuk, nr[i].second + d) - compute(nrbuk, nr[i].second - d - 1);
ans += compute(nrbuk, nr[i].second + d) - compute(nrbuk, nr[i].second - d - 1);
st += buk;
}
// if(i <= 10)
// cout << gn << '\n';
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';
}
void solve3()
{
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> tip >> n >> d >> m;
if(tip == 1)
solve1();
else
if(n <= 20000)
solvesmall();
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 |
3832 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
3960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
4600 KB |
Output is correct |
| 2 |
Correct |
24 ms |
4728 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
30 ms |
5112 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
5116 KB |
Output is correct |
| 2 |
Correct |
34 ms |
5112 KB |
Output is correct |
| 3 |
Correct |
33 ms |
5112 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
3932 KB |
Output is correct |
| 2 |
Correct |
7 ms |
3832 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
670 ms |
318972 KB |
Output is correct |
| 2 |
Correct |
661 ms |
319000 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2058 ms |
319284 KB |
Output is correct |
| 2 |
Correct |
2101 ms |
319380 KB |
Output is correct |
| 3 |
Correct |
2703 ms |
319224 KB |
Output is correct |
| 4 |
Correct |
2347 ms |
319224 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1464 ms |
321056 KB |
Output is correct |
| 2 |
Correct |
2082 ms |
321028 KB |
Output is correct |
| 3 |
Correct |
1252 ms |
319820 KB |
Output is correct |
| 4 |
Correct |
1542 ms |
319668 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
3832 KB |
Output is correct |
| 2 |
Correct |
7 ms |
3832 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
3832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
3832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
3892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
