Submission #924847

#	Time	Username	Problem	Language	Result	Execution time	Memory
924847		Karoot	Star triangles (IZhO11_triangle)	C++17	100 / 100	1251 ms	87456 KiB

triangle

#include <iostream>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>

#define all(x)  (x).begin(), (x).end()
#define rall(x)  (x).rbegin(), (x).rend()

using namespace std;

typedef long long ll;

ll linf = 1e15+1;

inline void scoobydoobydoo(){
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
}

unordered_map<ll, set<ll>> yM;
unordered_map<ll, set<ll>> xM;

map<pair<ll, ll>, ll> yToI;
map<pair<ll, ll>, ll> xToI;

int main(){
    scoobydoobydoo();
    ll n; cin >> n;
    vector<pair<ll, ll> > v(n);
    for (ll i = 0; i < n; i++){
        ll x, y; cin >> x >> y;
        yM[y].insert(x);
        xM[x].insert(y);
        v[i] = {x, y};
    }


    for (auto p : yM){
        ll counter = 0;
        for (ll x : p.second){
            yToI[{p.first, x}] = counter++;
        }
    }

    for (auto p : xM){
        ll counter = 0;
        for (ll x : p.second){
            xToI[{p.first, x}] = counter++;
        }
    }
    ll tot = 0;

    for (ll i = 0; i < n; i++){
        ll x = v[i].first;
        ll y = v[i].second;
        auto biggerYPtr = yM[y].lower_bound(x);
        ll smallerY = yToI[{x, *biggerYPtr}];
        ll biggerY = yM[y].size()-smallerY-1;
        auto biggerXPtr = xM[x].lower_bound(y);
        ll smallerX = xToI[{y, *biggerXPtr}];
        ll biggerX = xM[x].size()-smallerX-1;
        //cout << x << " " << y << endl;
        //cout << smallerX << " " << biggerX << " " << smallerY << " " << biggerY << endl;
        tot += smallerX*smallerY;
        tot += smallerX*biggerY;
        tot += biggerX*smallerY;
        tot += biggerX*biggerY;
    }   


    cout << tot << endl;



    return 0;
}

• Subtask 1: 100 / 100