Submission #1304200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304200		hoa208	Star triangles (IZhO11_triangle)	C++20	100 / 100	112 ms	14488 KiB

triangle

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define pa pair<ll, ll>
#define fi first
#define se second
#define bit(mask, j) ((mask >> j) & 1)
const   ll mod = 1e9 + 7;
const   ll INF = 1e18;
//--------------------------------------------------------------------

struct point {
	ll x, y, id;
};
const ll N = 3e5 + 10;
point a[N];
ll n;
const int maxbit = 5e5 + 10;
ll BIT[maxbit];
void update(int x, ll val, int _n) {
	while(x <= _n) {
	   BIT[x] += val;
	   x += x & -x; 
	}
}
ll get(int x) {
	ll res = 0;
	while(x > 0) {
		res += BIT[x];
		x -= x & -x;
	}
	return res;
}
void update_lr(int l, int r, ll val, int _n) {
	update(l, val, _n);
	update(r + 1, -val, _n);
}
int walk(int x, int _n) {
	int pos = 0;
	int LG = __lg(_n);
	FORD(j, LG, 0) {
		if(pos + (1 << j) <= _n && BIT[pos + (1 << j)] < x) {
			pos += (1 << j);
			x -= BIT[pos];
		}
	}
	return pos + 1;
}
ll cnt_y[N], cnt_x[N];
void hbmt() {
	cin >> n;
	FOR(i, 1, n) {
		cin >> a[i].x >> a[i].y;
		a[i].id = i;
	}
	sort(a + 1, a + n + 1, [&] (point &a, point &b) {
		return a.x < b.x || a.x == b.x && a.y < b.y;
	});
	ll pre = -1;
	FOR(i, 1, n) {
		if(pre == -1) {
			pre = i;
		}
		if(a[i].x != a[i + 1].x) {
			if(pre != -1)
				update_lr(pre, i, i - pre, n);
			pre = -1;
		}
	}
	FOR(i, 1, n) {
		cnt_y[a[i].id] = get(i);
	}
	FOR(i, 1, n) BIT[i] = 0;
	sort(a + 1, a + n + 1, [&] (point &a, point &b) {
		return a.y < b.y || a.y == b.y && a.x < b.x;
	});	
	pre = -1;
	FOR(i, 1, n) {
		if(pre == -1) {
			pre = i;
		}
		if(a[i].y != a[i + 1].y) {
			if(pre != -1)
				update_lr(pre, i, i - pre, n);
			pre = -1;
		}
	}
	FOR(i, 1, n) {
		cnt_x[a[i].id] = get(i);
	}
	ll ans = 0;
	FOR(i, 1, n) {
		ans += cnt_x[a[i].id] * cnt_y[a[i].id];
	}
	cout << ans;
}

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

	#define NAME "hbmt"
	if(fopen(NAME".inp", "r")) {
		freopen(NAME".inp", "r", stdin);
		freopen(NAME".out", "w", stdout);
	}
	
	//int t;cin>>t;while(t--)
	hbmt();
	return 0;
}

Compilation message (stderr)

triangle.cpp: In function 'int main()':
triangle.cpp:107:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |                 freopen(NAME".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
triangle.cpp:108:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |                 freopen(NAME".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100