Submission #1291424

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291424		haha	Star triangles (IZhO11_triangle)	C++20	0 / 100	158 ms	327680 KiB

triangle

#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;
const int maxn=2e5+5;

int n;
int x[maxn],y[maxn];
vector<int> nen;
vector<vector<int>> a,sum;

int get(int i,int j,int u,int v)
{
    return sum[u][v]-sum[i-1][v]-sum[u][j-1]+sum[i-1][j-1];
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
        nen.push_back(x[i]);
        nen.push_back(y[i]);
    }
    sort(nen.begin(),nen.end());
    nen.erase(unique(nen.begin(),nen.end()),nen.end());
    int maxX=0,maxY=0;
    for(int i=1;i<=n;i++){
        x[i]=lower_bound(nen.begin(),nen.end(),x[i])-nen.begin()+1;
        y[i]=lower_bound(nen.begin(),nen.end(),y[i])-nen.begin()+1;
        maxX=max(maxX,x[i]);
        maxY=max(maxY,y[i]);
    }
    a.assign(maxX+1,vector<int>(maxY+1,0));
    sum.assign(maxX+1,vector<int>(maxY+1,0));
    for(int i=1;i<=n;i++){
        a[x[i]][y[i]]=1;
    }
    for(int i=1;i<=maxX;i++){
        for(int j=1;j<=maxY;j++){
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
        }
    }
    ll ans=0;
    for(int i=1;i<=maxX;i++){
        for(int j=1;j<=maxY;j++){
            if(a[i][j]==1){
                int right=0,left=0,up=0,down=0;
                if(j+1<=maxY) right=get(i,j+1,i,maxY);
                if(j-1>=1) left=get(i,1,i,j-1);
                if(i-1>=1) up=get(1,j,i-1,j);
                if(i+1<=maxX) down=get(i+1,j,maxX,j);
                ans+=1LL*right*down;
                ans+=1LL*down*left;
                ans+=1LL*left*up;
                ans+=1LL*up*right;
            }
        }
    }
    cout<<ans;

}

• Subtask 1: 0 / 100