TCO12 500pt : ThreePoints
問題概要
2次元平面上に点がN(<3*10^5)個ある。x座標、y座標はどれも互いに異なる。3点選んでx[0]
解法
とりあえず座標圧縮しておく。その後x座標の大きい方から右上にいくつ点があるのかとx[1]
acceptされたコード
#include <algorithm> #include <cstring> using namespace std; typedef long long int64; const int MAX_N = 300000; struct Point{ int y, x; Point(){} Point(int y, int x):y(y), x(x){} }; bool operator< (const Point& lhs, const Point& rhs){ return lhs.x < rhs.x; } Point ps[MAX_N]; int tmp[MAX_N]; BinaryIndexedTree bit1, bit2; struct ThreePoints { int64 countColoring(int N, int xzero, int xmul, int xadd, int xmod, int yzero, int ymul, int yadd, int ymod) { int X, Y; ps[0] = Point(yzero, xzero); for(int i=0; i<N-1; ++i){ ps[i+1].y = ((int64)ps[i].y * ymul + yadd) % ymod; ps[i+1].x = ((int64)ps[i].x * xmul + xadd) % xmod; } for(int i=0; i<N; ++i){ tmp[i] = ps[i].x; } sort(tmp, tmp+N); X = unique(tmp, tmp+N) - tmp; for(int i=0; i<N; ++i){ ps[i].x = lower_bound(tmp, tmp+X, ps[i].x) - tmp; } for(int i=0; i<N; ++i){ tmp[i] = ps[i].y; } sort(tmp, tmp+N); Y = unique(tmp, tmp+N) - tmp; for(int i=0; i<N; ++i){ ps[i].y = lower_bound(tmp, tmp+Y, ps[i].y) - tmp; } sort(ps, ps + N); int64 ans = 0; bit1.init(N); bit2.init(N); for(int i=N-1; i>=0; --i){ int64 np = bit1.sum(ps[i].y, Y); int64 up = bit2.sum(ps[i].y, Y); if(np > 0){ ans += np * (np - 1) / 2 - up; } bit1.add(ps[i].y, 1); bit2.add(ps[i].y, np); } return ans; } };