oj.uz

Submission #875514

# Submission time Handle Problem Language Result Execution time Memory
875514 2023-11-20T00:17:31 Z abcvuitunggio Pairs (IOI07_pairs) C++17
100 / 100
 428 ms 62744 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
int b,n,d,m,a[100001][3],s[100001],cnt[76][76][76],sum[76][301][301],res,f[150001];
vector <int> v,v2;
vector <pair <pair <int, int>, pair <int, int>>> ve;
void update(int i, int val){
    i=max(i,1LL);
    for (;i<=m*2;i+=i&(-i))
        f[i]+=val;
}
void get(int i){
    for (;i;i-=i&(-i))
        res+=f[i];
}
int32_t main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> b >> n >> d >> m;
    for (int i=1;i<=n;i++){
        for (int j=0;j<b;j++)
            cin >> a[i][j];
        if (b==1)
            v.push_back(a[i][0]);
        if (b==2){
            int x=a[i][0],y=a[i][1];
            ve.push_back({{x-y-d,-1},{x+y-d,x+y+d}});
            ve.push_back({{x-y,0},{x+y,x+y}});
            ve.push_back({{x-y+d,1},{x+y-d,x+y+d}});
        }
        if (b==3){
            cnt[a[i][0]][a[i][1]][a[i][2]]++;
            sum[a[i][0]][a[i][1]-a[i][2]+m][a[i][1]+a[i][2]+m]++;
        }
    }
    if (b==1){
        sort(v.begin(),v.end());
        v.resize(unique(v.begin(),v.end())-v.begin());
        for (int i=1;i<=n;i++)
            s[lower_bound(v.begin(),v.end(),a[i][0])-v.begin()+1]++;
        for (int i=1;i<=v.size();i++)
            s[i]+=s[i-1];
        for (int i=1;i<=n;i++)
            res+=s[upper_bound(v.begin(),v.end(),a[i][0]+d)-v.begin()]-s[lower_bound(v.begin(),v.end(),a[i][0]-d)-v.begin()];
    }
    if (b==2){
        sort(ve.begin(),ve.end());
        for (auto p:ve)
            if (p.first.second==0)
                get(p.second.first);
            else{
                update(p.second.first,-p.first.second);
                update(p.second.second+1,p.first.second);
            }
    }
    if (b==3){
        for (int i=1;i<=m;i++)
            for (int j=1;j<=m*3;j++)
                for (int k=1;k<=m*3;k++)
                    sum[i][j][k]+=sum[i][j-1][k]+sum[i][j][k-1]-sum[i][j-1][k-1];
        for (int i=1;i<=m;i++)
            for (int j=1;j<=m;j++){
                int nd=d-abs(i-j);
                if (nd<0)
                    continue;
                for (int k=1;k<=m;k++)
                    for (int l=1;l<=m;l++){
                        int r=k-l-nd+m,r2=k-l+nd+m,c=k+l-nd+m,c2=k+l+nd+m;
                        if (max(r,c)>m*3||min(r2,c2)<1)
                            continue;
                        r=max(r,1LL);
                        r2=min(r2,m*3);
                        c=max(c,1LL);
                        c2=min(c2,m*3);
                        res+=(sum[j][r2][c2]-sum[j][r-1][c2]-sum[j][r2][c-1]+sum[j][r-1][c-1])*cnt[i][k][l];
                    }
            }
    }
    cout << (res-n)/2;
}

Compilation message

pairs.cpp: In function 'int32_t main()':
pairs.cpp:40:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for (int i=1;i<=v.size();i++)
      |                      ~^~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 5588 KB Output is correct
2 Correct 20 ms 5588 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 6100 KB Output is correct
2 Correct 30 ms 6256 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 6100 KB Output is correct
2 Correct 40 ms 6104 KB Output is correct
3 Correct 31 ms 6284 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 22340 KB Output is correct
2 Correct 49 ms 22220 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 21448 KB Output is correct
2 Correct 54 ms 22476 KB Output is correct
3 Correct 53 ms 21708 KB Output is correct
4 Correct 55 ms 23500 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 22724 KB Output is correct
2 Correct 58 ms 23240 KB Output is correct
3 Correct 68 ms 23776 KB Output is correct
4 Correct 60 ms 23244 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 59736 KB Output is correct
2 Correct 140 ms 59992 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15336 KB Output is correct
2 Correct 13 ms 15192 KB Output is correct
3 Correct 13 ms 15196 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 54356 KB Output is correct
2 Correct 111 ms 54352 KB Output is correct
3 Correct 80 ms 54536 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 62548 KB Output is correct
2 Correct 428 ms 62744 KB Output is correct
3 Correct 180 ms 62744 KB Output is correct