結果

問題 No.743 Segments on a Polygon
ユーザー jelljell
提出日時 2018-10-12 10:05:02
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 60 ms / 2,000 ms
コード長 3,722 bytes
コンパイル時間 1,620 ms
コンパイル使用メモリ 173,592 KB
実行使用メモリ 6,248 KB
最終ジャッジ日時 2024-04-26 21:22:09
合計ジャッジ時間 2,969 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 59 ms
6,112 KB
testcase_01 AC 59 ms
6,116 KB
testcase_02 AC 59 ms
6,248 KB
testcase_03 AC 59 ms
6,116 KB
testcase_04 AC 60 ms
6,240 KB
testcase_05 AC 58 ms
6,120 KB
testcase_06 AC 59 ms
6,120 KB
testcase_07 AC 60 ms
6,116 KB
testcase_08 AC 58 ms
6,116 KB
testcase_09 AC 44 ms
6,244 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#define debug 0
#define esc(ret) cout << (ret) << endl,exit(0)
#define fcout(d) cout << fixed << setprecision(d)
#define urep(i,s,t) for(int i = (int)(s); i <= (int)(t); ++i)
#define drep(i,s,t) for(int i = (int)(s); i >= (int)(t); --i)
#define rep(i,n) urep(i,0,(n) - 1)
#define rep1(i,n) urep(i,1,(n))
#define rrep(i,n) drep(i,(n) - 1,0)
#define all(v) begin(v),end(v)
#define rall(v) rbegin(v),rend(v)
#define vct vector
#define prique priority_queue
#define l_bnd lower_bound
#define u_bnd upper_bound
#define rsz resize
#define ers erase
#define emp emplace
#define emf emplace_front
#define emb emplace_back
#define pof pop_front
#define pob pop_back
#define mkp make_pair
#define mkt make_tuple
#define fir first
#define sec second
#define odd(x) ((x) & 1)
#define even(x) (~(x) & 1)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef vct<vct<ll>> mat;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tiii;
typedef map<int,int> mpii;
typedef unordered_map<int,int> umpii;

const int SZ = 1 << 18;
const int dir[8][2] = { {1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,1},{-1,-1},{1,-1} };
const ll inf32 = (1 << 30) - 1;
const ll inf64 = (1LL << 62) - 1;
const ll mod = 1e9 + 7;
const db eps = 1e-15;

template <class T, class U> T qceil(T x, U y) { return x > 0 ? (x - 1) / y + 1 : x / y; }
template <class T, class U> bool parity(T x, U y) { return odd(x) ^ even(y); }
template <class T, class U> bool chmax(T &m, U x) { if(m < x) { m = x; return 1; } return 0; }
template <class T, class U> bool chmin(T &m, U x) { if(m > x) { m = x; return 1; } return 0; }
template <class T> bool cmprs(T &v) {
    T tmp = v;
    sort(all(tmp));
    tmp.erase(unique(all(tmp)),end(tmp));
    for(auto it = begin(v); it != end(v); ++it) *it = l_bnd(all(tmp),*it) - begin(tmp) + 1;
    return v.size() > tmp.size();
}
mat mulmat(mat &x, mat &y, ll md = mod) {
    int xrow = x.size();
    int xcol = x[0].size();
    int ycol = y[0].size();
    mat ret(xrow,vct<ll>(ycol));
    rep(i,xrow)rep(j,ycol)rep(k,xcol) ret[i][j] += x[i][k] * y[k][j] % md,ret[i][j] %= md;
    return ret;
}

template<class T> T gcd(T a, T b){ if(a % b) return gcd(b, a % b); return b; }

ll modpow(ll n, ull e, ll md = mod) {
    n %= md;
    if(!e) return 0;
    return modpow(n * n % md,e / 2,md) * (e & 1 ? n : 1) % md;
}

template <class Abel = int> struct Segtree {
	typedef function<Abel(const Abel&,const Abel&)> func_type;
	const func_type opr;
	const Abel idel;
	int range = 1;
	vector<int> data;

	Segtree(int sz, Abel init_val, const func_type& f = plus<Abel>(), Abel id = 0) : opr(f),idel(id) {
		init(sz,init_val);
	}

	void init(int sz, Abel val) {
		while(sz >= range) range <<= 1;
		data.resize(range << 1);
		fill(begin(data) + range,end(data),val);
		for(int idx = range - 1; idx; idx--) data[idx] = opr(data[idx * 2],data[idx * 2 + 1]);
	}

	Abel get(int idx) { return data[idx + range]; }

	//for interval [l,r)
	Abel query(int l, int r) {
		l += range;
		r += range;
		Abel ret = idel;
		while(l < r) {
			if(l & 1) ret = opr(ret,data[l++]);
			if(r & 1) ret = opr(ret,data[--r]);
			l /= 2;
		    r /= 2;
		}
		return ret;
	}

	void update(int idx, Abel val) {
		idx += range;
		data[idx] = val;
		while(idx /= 2) {
			data[idx] = opr(data[idx * 2],data[idx * 2 + 1]);
		}
	}
	
	void add(int idx, Abel diff = 1) {
	    update(idx,get(idx) + diff);
	}
};

vct<pii> sgm;
int N,M;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	cin>>N>>M;
	rep(i,N){
		int a,b;
		cin>>a>>b;
		if(a>b) swap(a,b);
		sgm.emb(a,b);
	}
	sort(all(sgm));
	Segtree<> sgt(M,0);
	ll ans=0;
	for(pii p:sgm){
		ans+=sgt.query(p.fir,p.sec);
		sgt.add(p.sec);
	}
	esc(ans);
}
0