oj.uz

Submission #333818

# Submission time Handle Problem Language Result Execution time Memory
333818 2020-12-07T20:30:55 Z limabeans Star triangles (IZhO11_triangle) C++17
100 / 100
 1014 ms 20560 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;




int n;
vector<pair<int,int>> a;
map<int,vector<int>> byX, byY;


int getLess(int x, const vector<int>& w) {
    auto iter = lower_bound(w.begin(),w.end(),x);
    if (iter==w.begin()) return 0;
    --iter;
    return iter - w.begin() + 1;
}

int getGreater(int x, const vector<int>& w) {
    auto iter = upper_bound(w.begin(),w.end(),x);
    return w.end() - iter;
}


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

    cin>>n;
    a.resize(n);
    for (int i=0; i<n; i++) {
	cin>>a[i].first>>a[i].second;
	byX[a[i].first].push_back(a[i].second);
	byY[a[i].second].push_back(a[i].first);
    }

    for (auto &p: byX) {
	sort(p.second.begin(), p.second.end());
    }
    for (auto &p: byY) {
	sort(p.second.begin(), p.second.end());
    }


    ll res = 0;

    for (auto p: a) {
	int x = p.first;
	int y = p.second;
	res += 1ll*getLess(y,byX[x])*getLess(x,byY[y]);
	res += 1ll*getLess(y,byX[x])*getGreater(x,byY[y]);
	res += 1ll*getGreater(y,byX[x])*getLess(x,byY[y]);
	res += 1ll*getGreater(y,byX[x])*getGreater(x,byY[y]);
    }


    cout<<res<<endl;    
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 392 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 2 ms 492 KB Output is correct
12 Correct 17 ms 1772 KB Output is correct
13 Correct 17 ms 1900 KB Output is correct
14 Correct 21 ms 2540 KB Output is correct
15 Correct 304 ms 10476 KB Output is correct
16 Correct 336 ms 10860 KB Output is correct
17 Correct 314 ms 10524 KB Output is correct
18 Correct 313 ms 10604 KB Output is correct
19 Correct 938 ms 19436 KB Output is correct
20 Correct 678 ms 15520 KB Output is correct
21 Correct 1006 ms 20464 KB Output is correct
22 Correct 1014 ms 20560 KB Output is correct