oj.uz

Submission #1076762

# Submission time Handle Problem Language Result Execution time Memory
1076762 2024-08-26T16:18:08 Z Faisal_Saqib Pairs (IOI07_pairs) C++17
100 / 100
 1761 ms 6100 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];
const int M=75010;
const int limit=2*M;
const int M1=3*M;
int fen[M1];
void add(int x,int v)
{
    // if(v==1)
    // {
    //     cout<<"Adding "<<x<<endl;
    // }
    // else
    // {
    //     cout<<"Removing "<<x<<endl;
    // }
    while(x<M1)
    {
        fen[x]+=v;
        x+=(x&-x);
    }
}
ll get(int x)
{
    ll sum=0;
    while(x>0)
    {
        sum+=fen[x];
        x-=(x&-x);
    }
    return sum;
}
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+M});
    }
    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)
        {
            add(b[j].second,-1);
            j++;
        }
        int l=max(1,b[i].second-d);
        int r=min(limit,b[i].second+d);
        cnt+=get(r);
        cnt-=get(l-1);
        add(b[i].second,1);
    }
    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:160: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]
  160 |         for(int i=0;i<a.size();i++)
      |                     ~^~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1504 KB Output is correct
2 Correct 9 ms 1504 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1760 KB Output is correct
2 Correct 13 ms 1760 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1760 KB Output is correct
2 Correct 14 ms 1852 KB Output is correct
3 Correct 12 ms 1760 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2012 KB Output is correct
2 Correct 19 ms 2132 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2268 KB Output is correct
2 Correct 22 ms 2268 KB Output is correct
3 Correct 22 ms 2268 KB Output is correct
4 Correct 22 ms 2012 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3024 KB Output is correct
2 Correct 25 ms 3032 KB Output is correct
3 Correct 25 ms 3024 KB Output is correct
4 Correct 25 ms 3032 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2768 KB Output is correct
2 Correct 20 ms 2768 KB Output is correct
3 Correct 21 ms 2692 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 5328 KB Output is correct
2 Correct 758 ms 5332 KB Output is correct
3 Correct 1067 ms 5328 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 413 ms 6100 KB Output is correct
2 Correct 1553 ms 6096 KB Output is correct
3 Correct 1761 ms 6100 KB Output is correct