| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1076734 |
2024-08-26T16:02:22 Z |
Faisal_Saqib |
Pairs (IOI07_pairs) |
C++17 |
|
1759 ms |
6356 KB |
#pragma optimze("Ofast")
#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
using namespace std;
// #define endl '\n'
#define ll long long
const int N=76;
int pre[N][N][N];
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
bitset<100> have1;
int have3[N][N][N];
void solve_1d()
{
int n,d,m;
cin>>n>>d>>m;
vector<int> a;
for(int i=0;i<n;i++)
{
int x;
cin>>x;
a.push_back(x);
}
long long cnt=0;
sort(begin(a),end(a));
int i=0;
for(int j=0;j<n;j++)
{
while(i<n and a[i]<(a[j]-d))
{
i++;
}
cnt+=(j-i);
}
cout<<cnt<<'\n';
}
void solve_2d()
{
int n,d,m;
cin>>n>>d>>m;
vector<pair<int,int>> b;
for(int i=0;i<n;i++)
{
int x,y;
cin>>x>>y;
b.push_back({x+y,x-y});
}
ordered_set sp;
ll cnt=0;
sort(begin(b),end(b));
int j=0;
for(int i=0;i<n;i++)
{
while(j<=i and (b[i].first-b[j].first)>d)
{
sp.erase(sp.upper_bound(b[j].second));
j++;
}
int l=b[j].second-d;
int r=b[j].second+d;
cnt+=sp.order_of_key(r+1);
cnt-=sp.order_of_key(l);
sp.insert(b[i].second);
}
cout<<cnt<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);
int b,m;
cin>>b;
if(b==1)
{
solve_1d();
}
else if(b==2)
{
solve_2d();
}
else
{
int n,d;
cin>>n>>d>>m;
long long ap1=n;
ap1*=ap1;
long long kp=(2e8);
if(ap1<=kp)
{
vector<vector<int>> a;
for(int i=0;i<n;i++)
{
int x,y,z;
cin>>x>>y>>z;
a.push_back({x,y,z});
}
long long cnt=0;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if((abs(a[i][0]-a[j][0])+abs(a[i][1]-a[j][1])+abs(a[i][2]-a[j][2]))<=d)
{
cnt++;
}
}
}
cout<<cnt<<'\n';
exit(0);
}
vector<pair<int,pair<int,int>>> a;
for(int i=0;i<n;i++)
{
int x,y,z;
cin>>x>>y>>z;
a.push_back({x,{y,z}});
have1[x]=1;
have3[x][y][z]++;
while(z<=m)
{
pre[x][y][z]++;
z++;
}
}
long long cnt=0;
d=min(d,(m-1)*b);
sort(begin(a),end(a));
a.resize(unique(begin(a),end(a))-begin(a));
for(int i=0;i<a.size();i++)
{
int x=a[i].first,y=a[i].second.first,z=a[i].second.second;
int p=0;
for(int dx=0;dx<=(d) and dx<=(m-1);dx++)
{
if((x+dx>m or !have1[x+dx]) and ((x-dx)<=0 or !have1[x-dx]))
continue;
for(int dy=0;dy<=(m-1) and dy<=d and (dy+dx)<=d and (dy+dx)<=(2*(m-1));dy++)
{
int dz=d-(dy+dx);
if((x+dx)<=m)
{
if((y+dy)<=m)
{
p+=(pre[x+dx][y+dy][min(m,z+dz)]-pre[x+dx][y+dy][max(0,z-dz-1)])-((dx==0) and (dy==0));
}
if((y-dy)>0 and (dy!=0))
{
p+=(pre[x+dx][y-dy][min(m,z+dz)]-pre[x+dx][y-dy][max(0,z-dz-1)])-((dx==0) and (dy==0));
}
}
if((x-dx)>0 and (dx!=0))
{
if((y+dy)<=m)
{
p+=(pre[x-dx][y+dy][min(m,z+dz)]-pre[x-dx][y+dy][max(0,z-dz-1)])-((dx==0) and (dy==0));
}
if((y-dy)>0 and (dy!=0))
{
p+=(pre[x-dx][y-dy][min(m,z+dz)]-pre[x-dx][y-dy][max(0,z-dz-1)])-((dx==0) and (dy==0));
}
}
}
}
cnt+=p*have3[x][y][z];
}
cout<<cnt/2<<'\n';
}
return 0;
}
Compilation message
pairs.cpp:1: warning: ignoring '#pragma optimze ' [-Wunknown-pragmas]
1 | #pragma optimze("Ofast")
|
pairs.cpp: In function 'int main()':
pairs.cpp:136:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
136 | for(int i=0;i<a.size();i++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
1504 KB |
Output is correct |
| 2 |
Correct |
9 ms |
1504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
1760 KB |
Output is correct |
| 2 |
Correct |
13 ms |
1724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
1808 KB |
Output is correct |
| 2 |
Correct |
14 ms |
1868 KB |
Output is correct |
| 3 |
Correct |
15 ms |
1760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
2012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
2520 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
67 ms |
2764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
348 KB |
Output is correct |
| 2 |
Correct |
2 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
2768 KB |
Output is correct |
| 2 |
Correct |
30 ms |
2900 KB |
Output is correct |
| 3 |
Correct |
21 ms |
2772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
5332 KB |
Output is correct |
| 2 |
Correct |
728 ms |
5332 KB |
Output is correct |
| 3 |
Correct |
1120 ms |
5324 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
433 ms |
6356 KB |
Output is correct |
| 2 |
Correct |
1562 ms |
6100 KB |
Output is correct |
| 3 |
Correct |
1759 ms |
6252 KB |
Output is correct |
