結果

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

ソースコード

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);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0