oj.uz

Submission #341715

# Submission time Handle Problem Language Result Execution time Memory
341715 2020-12-30T14:28:18 Z spike1236 Star triangles (IZhO11_triangle) C++14
100 / 100
 1371 ms 20564 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ll long long
#define ld long double
#define all(_v) _v.begin(), _v.end()
#define sz(_v) (int)_v.size()
#define pii pair <int, int>
#define pll pair <ll, ll>
#define veci vector <int>
#define vecll vector <ll>

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
const double PI = 3.1415926535897932384626433832795;
const double eps = 1e-9;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;

const int MAXN = 3e5 + 10;
pii a[MAXN];
map <int, veci> x, y;

void solve() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i].f >> a[i].s;
        x[a[i].f].pb(a[i].s);
        y[a[i].s].pb(a[i].f);
    }
    for(auto it : x)
        sort(all(x[it.f]));
    for(auto it : y)
        sort(all(y[it.f]));
    ll ans = 0;
    for(int i = 1; i <= n; ++i) {
        ll res1, res2;
        res1 = res2 = 0;
        if(x[a[i].f].back() > a[i].s) res1 = x[a[i].f].end() - upper_bound(all(x[a[i].f]), a[i].s);
        if(y[a[i].s].back() > a[i].f) res2 = y[a[i].s].end() - upper_bound(all(y[a[i].s]), a[i].f);
        ans += res1 * 1ll * res2;
        res2 = 0;
        if(y[a[i].s][0] < a[i].f) res2 = lower_bound(all(y[a[i].s]), a[i].f) - y[a[i].s].begin();
        ans += res1 * 1ll * res2;
        res1 = 0;
        if(x[a[i].f][0] < a[i].s) res1 = lower_bound(all(x[a[i].f]), a[i].s) - x[a[i].f].begin();
        ans += res1 * 1ll * res2;
        res2 = 0;
        if(y[a[i].s].back() > a[i].f) res2 = y[a[i].s].end() - upper_bound(all(y[a[i].s]), a[i].f);
        ans += res1 * 1ll * res2;
    }
    cout << ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    ///cin >> T;
    while(T--) solve(), cout << '\n';
    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 384 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 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 1 ms 512 KB Output is correct
11 Correct 2 ms 492 KB Output is correct
12 Correct 15 ms 1772 KB Output is correct
13 Correct 15 ms 1772 KB Output is correct
14 Correct 24 ms 2540 KB Output is correct
15 Correct 391 ms 10604 KB Output is correct
16 Correct 462 ms 10988 KB Output is correct
17 Correct 433 ms 10568 KB Output is correct
18 Correct 406 ms 10484 KB Output is correct
19 Correct 1259 ms 19308 KB Output is correct
20 Correct 891 ms 15608 KB Output is correct
21 Correct 1296 ms 20420 KB Output is correct
22 Correct 1371 ms 20564 KB Output is correct