結果
問題 | No.743 Segments on a Polygon |
ユーザー |
![]() |
提出日時 | 2018-10-12 10:05:02 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 59 ms / 2,000 ms |
コード長 | 3,722 bytes |
コンパイル時間 | 2,322 ms |
コンパイル使用メモリ | 175,088 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-14 12:40:48 |
合計ジャッジ時間 | 3,673 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
#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);}