結果

問題 No.743 Segments on a Polygon
ユーザー beetbeet
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 HERE
signed 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0