Submission #1295114

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295114		k12_khoi	Star triangles (IZhO11_triangle)	C++17	100 / 100	197 ms	28924 KiB

triangle

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int,int>
#define X first
#define Y second

const int N=3e5+5;

int n,x,y; ll res;
int cnt[N],dem[N];
vector <int> ve,comp,temp;
vector <pii> a;
vector <pii> query_x[N],queryY[N];

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);

    ve.clear();
    comp.clear();
    a.clear();

    cin >> n;
    for (int i=0;i<n;i++)
    {
        cin >> x >> y;
        ve.push_back(x);
        comp.push_back(y);
        a.push_back(make_pair(x,y));
    }
    sort(ve.begin(),ve.end());
    ve.resize(unique(ve.begin(),ve.end())-ve.begin());
    sort(comp.begin(),comp.end());
    comp.resize(unique(comp.begin(),comp.end())-comp.begin());

    for (int i=0;i<n;i++)
    {
        a[i].X=lower_bound(ve.begin(),ve.end(),a[i].X)-ve.begin();
        a[i].Y=lower_bound(comp.begin(),comp.end(),a[i].Y)-comp.begin();
        query_x[a[i].X].push_back(make_pair(a[i].Y,i));
        queryY[a[i].Y].push_back(make_pair(a[i].X,i));
    }

    for (int i=0;i<ve.size();i++)
    {
        temp.clear();

        for (pii j:query_x[i])
        temp.push_back(j.X);

        sort(temp.begin(),temp.end());
        temp.resize(unique(temp.begin(),temp.end())-temp.begin());

        for (int i=0;i<=temp.size();i++)
        cnt[i]=0;

        for (int j=0;j<query_x[i].size();j++)
        {
            query_x[i][j].X=lower_bound(temp.begin(),temp.end(),query_x[i][j].X)-temp.begin();
            cnt[query_x[i][j].X]++;
        }

        for (int i=temp.size()-1;i>=0;i--)
        cnt[i]+=cnt[i+1];

        for (pii j:query_x[i])
        dem[j.Y]=cnt[0]-cnt[j.X]+cnt[j.X+1];
    }

    for (int i=0;i<comp.size();i++)
    {
        temp.clear();

        for (pii j:queryY[i])
        temp.push_back(j.X);

        sort(temp.begin(),temp.end());
        temp.resize(unique(temp.begin(),temp.end())-temp.begin());

        for (int i=0;i<=temp.size();i++)
        cnt[i]=0;

        for (int j=0;j<queryY[i].size();j++)
        {
            queryY[i][j].X=lower_bound(temp.begin(),temp.end(),queryY[i][j].X)-temp.begin();
            cnt[queryY[i][j].X]++;
        }

        for (int i=temp.size()-1;i>=0;i--)
        cnt[i]+=cnt[i+1];

        for (pii j:queryY[i])
        res+=1LL*(cnt[0]-cnt[j.X]+cnt[j.X+1])*dem[j.Y];
    }

    cout << res;
}

• Subtask 1: 100 / 100