結果
問題 | No.743 Segments on a Polygon |
ユーザー |
![]() |
提出日時 | 2018-10-05 21:58:10 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,898 bytes |
コンパイル時間 | 2,325 ms |
コンパイル使用メモリ | 186,916 KB |
実行使用メモリ | 156,924 KB |
最終ジャッジ日時 | 2024-10-12 13:08:11 |
合計ジャッジ時間 | 30,451 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 1 TLE * 9 |
ソースコード
#include<bits/stdc++.h>using namespace std;using Int = long long;using T = Int;struct BinaryIndexedTree{vector< T > data;BinaryIndexedTree(Int sz){data.assign(++sz, 0);}T sum(Int k){T ret = 0;for(++k; k > 0; k -= k & -k) ret += data[k];return (ret);}void add(Int k, T x){for(++k; k < data.size(); k += k & -k) data[k] += x;}};struct SegmentTreeBIT{Int sz;vector< BinaryIndexedTree > seg;vector< vector< Int > > beet;SegmentTreeBIT(Int n){sz = 1;while(sz < n) sz <<= 1;beet.resize(2 * sz - 1);}void update(Int x, Int y, Int z){x += sz - 1;seg[x].add(lower_bound(begin(beet[x]), end(beet[x]), y) - begin(beet[x]), z);while(x > 0) {x = (x - 1) >> 1;seg[x].add(lower_bound(begin(beet[x]), end(beet[x]), y) - begin(beet[x]), z);}}void build(){for(Int k = beet.size() - 1; k >= 0; k--) {sort(begin(beet[k]), end(beet[k]));beet[k].erase(unique(begin(beet[k]), end(beet[k])), end(beet[k]));}for(Int k = 0; k < beet.size(); k++) {seg.emplace_back(BinaryIndexedTree(beet[k].size()));}}Int query(Int a, Int b, Int x, Int y, Int k, Int l, Int r){if(a >= r || b <= l) return (0);if(a <= l && r <= b) {Int p = y, q = x;y = lower_bound(begin(beet[k]), end(beet[k]), y) - begin(beet[k]);x = lower_bound(begin(beet[k]), end(beet[k]), x) - begin(beet[k]);return (seg[k].sum(y) - seg[k].sum(x));}return (query(a, b, x, y, 2 * k + 1, l, (l + r) >> 1) + query(a, b, x, y, 2 * k + 2, (l + r) >> 1, r));}Int query(Int a, Int b, Int x, Int y){return (query(a, b, x, y, 0, 0, sz));}void preupdate(Int x, Int y){x += sz - 1;beet[x].push_back(y);while(x > 0) {x = (x - 1) >> 1;beet[x].push_back(y);}}void prequery(Int a, Int b, Int x, Int y, Int k, Int l, Int r){if(a >= r || b <= l) return;if(a <= l && r <= b) {beet[k].push_back(y);beet[k].push_back(x);return;}prequery(a, b, x, y, 2 * k + 1, l, (l + r) >> 1);prequery(a, b, x, y, 2 * k + 2, (l + r) >> 1, r);}void prequery(Int a, Int b, Int x, Int y){prequery(a, b, x, y, 0, 0, sz);}};//INSERT ABOVE HEREsigned main(){Int n,m;scanf("%lld %lld",&n,&m);vector<Int> a(n),b(n);for(Int i=0;i<n;i++) scanf("%lld %lld",&a[i],&b[i]);SegmentTreeBIT seg(m);for(Int i=0;i<n;i++){if(a[i]>b[i]) swap(a[i],b[i]);seg.prequery(0,a[i],a[i],b[i]);seg.prequery(a[i],b[i],b[i],m);seg.preupdate(a[i],b[i]);}seg.build();long long ans=0;for(Int i=0;i<n;i++){if(a[i]>b[i]) swap(a[i],b[i]);ans+=seg.query(0,a[i],a[i],b[i]);ans+=seg.query(a[i],b[i],b[i],m);seg.update(a[i],b[i],1);}printf("%lld\n",ans);return 0;}