fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef long double ld;
  6. typedef double db; 
  7. typedef string str; 
  8.  
  9. typedef pair<int,int> pi;
  10. typedef pair<ll,ll> pl; 
  11. typedef pair<db,db> pd; 
  12.  
  13. typedef vector<int> vi; 
  14. typedef vector<ll> vl; 
  15. typedef vector<db> vd; 
  16. typedef vector<str> vs; 
  17. typedef vector<pi> vpi;
  18. typedef vector<pl> vpl; 
  19. typedef vector<pd> vpd; 
  20.  
  21. #define mp make_pair
  22. #define f first
  23. #define s second
  24. #define sz(x) (int)x.size()
  25. #define all(x) begin(x), end(x)
  26. #define rall(x) (x).rbegin(), (x).rend() 
  27. #define rsz resize
  28. #define ins insert 
  29. #define ft front() 
  30. #define bk back()
  31. #define pf push_front 
  32. #define pb push_back
  33. #define eb emplace_back 
  34. #define lb lower_bound 
  35. #define ub upper_bound 
  36.  
  37. #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
  38. #define F0R(i,a) FOR(i,0,a)
  39. #define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
  40. #define R0F(i,a) ROF(i,0,a)
  41. #define trav(a,x) for (auto& a: x)
  42.  
  43. const int MOD = 1e9+7; // 998244353;
  44. const int MX = 2e5+5; 
  45. const ll INF = 1e18; 
  46. const ld PI = acos((ld)-1);
  47. const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; 
  48.  
  49. template<class T> bool ckmin(T& a, const T& b) { 
  50. 	return b < a ? a = b, 1 : 0; }
  51. template<class T> bool ckmax(T& a, const T& b) { 
  52. 	return a < b ? a = b, 1 : 0; } 
  53. int pct(int x) { return __builtin_popcount(x); } 
  54. int bit(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
  55. int cdiv(int a, int b) { return a/b+!(a<0||a%b == 0); } // division of a by b rounded up, assumes b > 0 
  56.  
  57. // INPUT
  58. template<class A> void re(complex<A>& c);
  59. template<class A, class B> void re(pair<A,B>& p);
  60. template<class A> void re(vector<A>& v);
  61. template<class A, size_t SZ> void re(array<A,SZ>& a);
  62.  
  63. template<class T> void re(T& x) { cin >> x; }
  64. void re(db& d) { str t; re(t); d = stod(t); }
  65. void re(ld& d) { str t; re(t); d = stold(t); }
  66. template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }
  67.  
  68. template<class A> void re(complex<A>& c) { A a,b; re(a,b); c = {a,b}; }
  69. template<class A, class B> void re(pair<A,B>& p) { re(p.f,p.s); }
  70. template<class A> void re(vector<A>& x) { trav(a,x) re(a); }
  71. template<class A, size_t SZ> void re(array<A,SZ>& x) { trav(a,x) re(a); }
  72.  
  73. // TO_STRING
  74. #define ts to_string
  75. template<class A, class B> str ts(pair<A,B> p);
  76. template<class A> str ts(complex<A> c) { return ts(mp(c.real(),c.imag())); }
  77. str ts(bool b) { return b ? "true" : "false"; }
  78. str ts(char c) { str s = ""; s += c; return s; }
  79. str ts(str s) { return s; }
  80. str ts(const char* s) { return (str)s; }
  81. str ts(vector<bool> v) { 
  82. 	bool fst = 1; str res = "{";
  83. 	F0R(i,sz(v)) {
  84. 		if (!fst) res += ", ";
  85. 		fst = 0; res += ts(v[i]);
  86. 	}
  87. 	res += "}"; return res;
  88. }
  89. template<size_t SZ> str ts(bitset<SZ> b) {
  90. 	str res = ""; F0R(i,SZ) res += char('0'+b[i]);
  91. 	return res; }
  92. template<class T> str ts(T v) {
  93. 	bool fst = 1; str res = "{";
  94. 	for (const auto& x: v) {
  95. 		if (!fst) res += ", ";
  96. 		fst = 0; res += ts(x);
  97. 	}
  98. 	res += "}"; return res;
  99. }
  100. template<class A, class B> str ts(pair<A,B> p) {
  101. 	return "("+ts(p.f)+", "+ts(p.s)+")"; }
  102.  
  103. // OUTPUT
  104. template<class A> void pr(A x) { cout << ts(x); }
  105. template<class H, class... T> void pr(const H& h, const T&... t) { 
  106. 	pr(h); pr(t...); }
  107. void ps() { pr("\n"); } // print w/ spaces
  108. template<class H, class... T> void ps(const H& h, const T&... t) { 
  109. 	pr(h); if (sizeof...(t)) pr(" "); ps(t...); }
  110.  
  111. // DEBUG
  112. void DBG() { cerr << "]" << endl; }
  113. template<class H, class... T> void DBG(H h, T... t) {
  114. 	cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
  115. 	DBG(t...); }
  116. #ifdef LOCAL // compile with -DLOCAL
  117. #define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
  118. #else
  119. #define dbg(...) 42
  120. #endif
  121.  
  122. // FILE I/O
  123. void setIn(string s) { freopen(s.c_str(),"r",stdin); }
  124. void setOut(string s) { freopen(s.c_str(),"w",stdout); }
  125. void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
  126. void setIO(string s = "") {
  127. 	unsyncIO();
  128. 	// cin.exceptions(cin.failbit); 
  129. 	// throws exception when do smth illegal
  130. 	// ex. try to read letter into int
  131. 	if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
  132. }
  133.  
  134. mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 
  135.  
  136. /**
  137.  * Description: modular arithmetic operations 
  138.  * Source: 
  139. 	* KACTL
  140. 	* https://c...content-available-to-author-only...s.com/blog/entry/63903
  141. 	* https://c...content-available-to-author-only...s.com/contest/1261/submission/65632855 (tourist)
  142. 	* https://c...content-available-to-author-only...s.com/contest/1264/submission/66344993 (ksun)
  143.  * Verification: 
  144. 	* https://o...content-available-to-author-only...s.com/problems/modulararithmetic
  145.  */
  146.  
  147. struct mi {
  148. 	typedef decay<decltype(MOD)>::type T; 
  149.  	/// don't silently convert to T
  150. 	T v; explicit operator T() const { return v; }
  151. 	mi() { v = 0; }
  152. 	mi(ll _v) { 
  153. 		v = (-MOD < _v && _v < MOD) ? _v : _v % MOD;
  154. 		if (v < 0) v += MOD;
  155. 	}
  156. 	friend bool operator==(const mi& a, const mi& b) { 
  157. 		return a.v == b.v; }
  158. 	friend bool operator!=(const mi& a, const mi& b) { 
  159. 		return !(a == b); }
  160. 	friend bool operator<(const mi& a, const mi& b) { 
  161. 		return a.v < b.v; }
  162. 	friend void re(mi& a) { ll x; re(x); a = mi(x); }
  163. 	friend str ts(mi a) { return ts(a.v); }
  164.  
  165. 	mi& operator+=(const mi& m) { 
  166. 		if ((v += m.v) >= MOD) v -= MOD; 
  167. 		return *this; }
  168. 	mi& operator-=(const mi& m) { 
  169. 		if ((v -= m.v) < 0) v += MOD; 
  170. 		return *this; }
  171. 	mi& operator*=(const mi& m) { 
  172. 		v = (ll)v*m.v%MOD; return *this; }
  173. 	mi& operator/=(const mi& m) { return (*this) *= inv(m); }
  174. 	friend mi pow(mi a, ll p) {
  175. 		mi ans = 1; assert(p >= 0);
  176. 		for (; p; p /= 2, a *= a) if (p&1) ans *= a;
  177. 		return ans;
  178. 	}
  179. 	friend mi inv(const mi& a) { assert(a.v != 0); 
  180. 		return pow(a,MOD-2); }
  181.  
  182. 	mi operator-() const { return mi(-v); }
  183. 	mi& operator++() { return *this += 1; }
  184. 	mi& operator--() { return *this -= 1; }
  185. 	friend mi operator+(mi a, const mi& b) { return a += b; }
  186. 	friend mi operator-(mi a, const mi& b) { return a -= b; }
  187. 	friend mi operator*(mi a, const mi& b) { return a *= b; }
  188. 	friend mi operator/(mi a, const mi& b) { return a /= b; }
  189. };
  190. typedef vector<mi> vmi;
  191. typedef pair<mi,mi> pmi;
  192. typedef vector<pmi> vpmi;
  193.  
  194. vector<vmi> comb;
  195. void genComb(int SZ) {
  196. 	comb.assign(SZ,vmi(SZ)); comb[0][0] = 1;
  197. 	FOR(i,1,SZ) F0R(j,i+1) 
  198. 		comb[i][j] = comb[i-1][j]+(j?comb[i-1][j-1]:0);
  199. }
  200.  
  201. mi ans, i2 = mi(1)/2, i3 = mi(1)/3;
  202. int n,m,k;
  203. pi r[MX], c[MX];
  204.  
  205. mi c2(mi x) { return x*(x-1)*i2; }
  206.  
  207. void vert() {
  208. 	mi sum = c2(m);
  209. 	map<int,int> cur;
  210. 	cur[0] = 0, cur[m+1] = m+1;
  211. 	int lst = 0;
  212. 	vector<array<int,3>> ev;
  213. 	F0R(i,k) {
  214. 		ev.pb({r[i].f,1,i});
  215. 		ev.pb({r[i].s+1,-1,i});
  216. 	}
  217. 	auto gap = [&](pi a, pi b) {
  218. 		assert(a.s < b.f);
  219. 		return c2(b.f-a.s-1);
  220. 	};
  221. 	auto ad = [&](int a, int b) {
  222. 		auto it = cur.insert({a,b}).f;
  223. 		sum -= gap(*prev(it),*next(it));
  224. 		sum += gap(*prev(it),*it);
  225. 		sum += gap(*it,*next(it));
  226. 	};
  227. 	auto del = [&](int a, int b) {
  228. 		auto it = cur.find(a);
  229. 		sum += gap(*prev(it),*next(it));
  230. 		sum -= gap(*prev(it),*it);
  231. 		sum -= gap(*it,*next(it));
  232. 		cur.erase(it);
  233. 	};
  234. 	sort(all(ev));
  235. 	trav(t,ev) {
  236. 		ans += (t[0]-1-lst)*sum; lst = t[0]-1;
  237. 		if (t[1] == 1) {
  238. 			pi y = c[t[2]];
  239. 			ad(y.f,y.s);
  240. 		} else {
  241. 			pi y = c[t[2]];
  242. 			del(y.f,y.s);
  243. 		}
  244. 		// dbg("HUH",t,sum);
  245. 	}
  246. 	ans += (n-lst)*sum;
  247. }
  248.  
  249. typedef array<mi,3> T;
  250.  
  251. T operator-=(T& a, T b) {
  252. 	F0R(i,3) a[i] -= b[i];
  253. 	return a;
  254. }
  255. T operator-(T a, T b) { return a -= b; }
  256. T operator+=(T& a, T b) {
  257. 	F0R(i,3) a[i] += b[i];
  258. 	return a;
  259. }
  260.  
  261. mi cum(T cval, mi r) {
  262. 	return r*(cval[0]+(r+1)*i2*(cval[1]+cval[2]*(2*r+1)*i3));
  263. }
  264.  
  265. mi cum(T cval, int l, int r) {
  266. 	return cum(cval,r)-cum(cval,l-1);
  267. }
  268.  
  269. int tim;
  270.  
  271. int lo(int a) {
  272. 	if (a == k) {
  273. 		return -MOD;
  274. 	}
  275. 	if (a == k+1) { // (0,0) -> (0,m+1) -> (n+1,m+1)
  276. 		return min(m+1,tim);
  277. 	}
  278. 	assert(tim >= r[a].f+c[a].f);
  279. 	return max(c[a].f,tim-r[a].s);
  280. }
  281.  
  282. T LO(int a) {
  283. 	if (a == k) return {-MOD,0,0};
  284. 	if (a == k+1) {
  285. 		if (tim >= m+1) return {m+1,0,0};
  286. 		return {0,1,0};
  287. 	}
  288. 	assert(tim >= r[a].f+c[a].f);
  289. 	if (tim >= r[a].s+c[a].f) return {-r[a].s,1,0};
  290. 	return {c[a].f,0,0};
  291. }
  292.  
  293. int hi(int a) {
  294. 	if (a == k) { // (0,0) -> (n+1,0) -> (n+1,m+1)
  295. 		return max(0,tim-(n+1));
  296. 	}
  297. 	if (a == k+1) {
  298. 		return MOD;
  299. 	}
  300. 	assert(tim >= r[a].f+c[a].f);
  301. 	return min(c[a].s,tim-r[a].f);
  302. }
  303.  
  304. T HI(int a) {
  305. 	if (a == k) {
  306. 		if (tim >= n+1) return {-(n+1),1,0};
  307. 		return {0,0,0};
  308. 	}
  309. 	if (a == k+1) return {MOD,0,0};
  310. 	assert(tim >= r[a].f+c[a].f);
  311. 	if (tim >= r[a].f+c[a].s) return {c[a].s,0,0};
  312. 	return {-r[a].f,1,0};
  313. }
  314.  
  315. struct cmp {
  316. 	bool operator()(const int& a, const int& b) const {
  317. 		return lo(a) < lo(b);
  318. 	}
  319. };
  320.  
  321. T stor[MX], cval;
  322.  
  323. void calc(int a, int b) {
  324. 	auto x = LO(b)-HI(a); 
  325. 	assert(x[2] == 0); x[0] -= 1;
  326. 	mi A = x[1], B = x[0];
  327. 	x = {B*(B-1),A*(2*B-1),A*A};
  328. 	F0R(i,3) x[i] *= i2;
  329. 	// dbg("AD",a,b);
  330. 	stor[a] = x; cval += x;
  331. }
  332.  
  333. void diag() {
  334. 	cval = {0,0,0}; tim = 1; calc(k,k+1);
  335. 	// dbg("HUH",cval,cum(cval,2,2));
  336. 	vector<array<int,3>> ev;
  337. 	F0R(i,k) {
  338. 		pi R = r[i], C = c[i];
  339. 		ev.pb({R.s+C.s+1,-1,i});
  340. 		ev.pb({R.f+C.f,0,i});
  341. 		ev.pb({R.s+C.f,1,i});
  342. 		ev.pb({R.f+C.s,1,i});
  343. 	}
  344. 	/*FOR(i,4,100) {
  345. 		tim = i;
  346. 		mi x = cum(LO(0),tim,tim), y = cum(HI(0),tim,tim);
  347. 		assert(x == lo(0) && y == hi(0));
  348. 	}
  349. 	FOR(i,1,100) {
  350. 		tim = i;
  351. 		mi x = cum(LO(k),tim,tim), y = cum(HI(k),tim,tim);
  352. 		assert(x == lo(k) && y == hi(k));
  353. 	}
  354. 	FOR(i,1,100) {
  355. 		tim = i;
  356. 		mi x = cum(LO(k+1),tim,tim), y = cum(HI(k+1),tim,tim);
  357. 		assert(x == lo(k+1) && y == hi(k+1));
  358. 	}
  359. 	exit(0);*/
  360. 	ev.pb({n+1,1,k}); ev.pb({m+1,2,k+1});
  361. 	sort(all(ev));
  362. 	set<int,cmp> cur; tim = 0;
  363. 	cur.insert(k), cur.insert(k+1);
  364. 	int lst = 1; 
  365. 	trav(t,ev) {
  366. 		/*dbg(cur,ans);
  367. 		dbg(lst+1,t[0]-1,cum(cval,lst+1,t[0]-1));
  368. 		dbg(cval);
  369. 		dbg(t);
  370. 		dbg();*/
  371. 		ans += cum(cval,lst+1,t[0]-1); lst = t[0]-1;
  372. 		tim = t[0];
  373. 		dbg(tim,HI(k),LO(k+1));
  374. 		if (t[1] == -1) {
  375. 			tim = lst;
  376. 			auto it = cur.find(t[2]); assert(it != end(cur) && *it == t[2]);
  377. 			cval -= stor[*prev(it)]; cval -= stor[*it];
  378. 			dbg("SUB",*prev(it)); dbg("SUB",*it);
  379. 			calc(*prev(it),*next(it));
  380. 			cur.erase(it);
  381. 		} else if (t[1] == 0) {
  382. 			auto it = cur.insert(t[2]).f;
  383. 			cval -= stor[*prev(it)]; dbg("SUB",*prev(it));
  384. 			calc(*prev(it),*it); calc(*it,*next(it));
  385. 		} else {
  386. 			auto it = cur.find(t[2]); assert(it != end(cur) && *it == t[2]);
  387. 			if (it != begin(cur)) {
  388. 				cval -= stor[*prev(it)]; dbg("SUB",*prev(it)); 
  389. 				calc(*prev(it),*it);
  390. 			}
  391. 			if (next(it) != end(cur)) {
  392. 				cval -= stor[*it];  dbg("SUB",*it);
  393. 				calc(*it,*next(it));
  394. 			}
  395. 		} 
  396. 	}
  397. 	//dbg("OH",cur,cval);
  398. 	ans += cum(cval,lst+1,n+m);
  399. 	dbg(ans);
  400. 	// exit(0);
  401. }
  402.  
  403. int main() {
  404. 	setIO(); re(n,m,k);
  405. 	F0R(i,k) re(r[i].f,c[i].f,r[i].s,c[i].s);
  406. 	diag();
  407. 	dbg(ans);
  408. 	F0R(i,k) r[i] = {n+1-r[i].s,n+1-r[i].f};
  409. 	diag();
  410. 	//dbg(ans);
  411. 	//exit(0);
  412. 	vert(); 
  413. 	//dbg("HUH",ans);
  414. 	swap(n,m);
  415. 	F0R(i,k) swap(r[i],c[i]);
  416. 	vert();
  417. 	//dbg("HUH",ans);
  418. 	ps(ans);
  419. 	// you should actually read the stuff at the bottom
  420. }
  421.  
  422. /* stuff you should look for
  423. 	* int overflow, array bounds
  424. 	* special cases (n=1?)
  425. 	* do smth instead of nothing and stay organized
  426. 	* WRITE STUFF DOWN
  427. */
  428.  
  429.  
Success #stdin #stdout 0s 5996KB
comments (?)
stdin
copy 
6 9 5
1 6 4 8
3 2 6 2
2 1 6 1
1 3 5 5
3 9 4 9
stdout
copy 
42
https://ideone.com/YWVyTd
BSUIR Semifinal 20 E (Public)
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!