Submission #51977

# Submission time Handle Problem Language Result Execution time Memory
51977 2018-06-22T20:18:44 Z FLDutchman Star triangles (IZhO11_triangle) C++14
0 / 100
3 ms 600 KB
#include "bits/stdc++.h"
using namespace std;

#define int long long
#define FOR(i, l, r) for(int i = l; i < r; i++)
#define snd second
#define fst first
#define pb push_back

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;

vii ps, xs, ys;
vi xc, yc;
int N;

bool lt(ii &a, ii &b){
    return a.snd < b.snd;
}

int compress(vii &v){
    sort(v.begin(), v.end());
    int c = 0;
    v[0].fst = 0;
    FOR(i, 0, N) v[i].fst = (v[i].fst == v[i-1].fst ? c : ++c);
    return c+1;
}

signed main(){
    cin >> N;
    FOR(i, 0, N){
        int x, y;
        cin >> x >> y;
        ps.pb({x, y});
        xs.pb({x, i});
        ys.pb({y, i});
    }
    xc.assign(compress(xs), 0); 
    yc.assign(compress(ys), 0);
    for(ii &p: xs) {
        ps[p.snd].fst = p.fst;
        xc[p.fst]++;
    }
    for(ii &p: ys) {
        ps[p.snd].snd = p.fst;
        yc[p.fst]++;
    }
    int sum = 0;
    for(ii &p : ps){
        sum += (xc[p.fst]-1) * (yc[p.snd] - 1);
    }
    cout << sum;
}
# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 360 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Incorrect 3 ms 600 KB Output isn't correct
5 Halted 0 ms 0 KB -