Submission #875514

#	Time	Username	Problem	Language	Result	Execution time	Memory
875514		abcvuitunggio	Pairs (IOI07_pairs)	C++17	100 / 100	428 ms	62744 KiB

pairs

#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 (stderr)

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 / 6
• Subtask 2: 6 / 6
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10
• Subtask 12: 10 / 10
• Subtask 13: 10 / 10