fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define endl "\n"
  7. #define FOR(i, l, r) for (ll i = l; i <= r; i++)
  8. #define FORD(i, l, r) for (ll i = l; i >= r; i--)
  9. #define fre(NAME) freopen(NAME".inp","r",stdin); freopen(NAME".out","w",stdout)
  10. #define boost ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  11. #define ldb long double
  12. #pragma GCC optimize("O3")
  13. #define ull unsigned long long
  14. #define time cerr << "Time: " << 1.0 * clock() / CLOCKS_PER_SEC << endl;
  15. #define fi first
  16. #define se second
  17. #define pb push_back
  18. #define mpr make_pair
  19. #define sz(a) a.size()
  20. #define all(a) a.begin(),a.end()
  21. #define ms(a,n) memset(a,n,sizeof(a))
  22. #define FIX(a,n) fixed << setprecision(n) << a
  23.  
  24. // Bit
  25. #define MASK(x) (1<<(x))
  26. #define BIT(mask, i) (((mask) >> (i))&1)
  27. #define SET_ON(x,i) ((x) | MASK(i))
  28. #define SET_OFF(x,i) ((x) & ~MASK(i))
  29. #define c_bit(i) __builtin_popcountll(i)
  30.  
  31. typedef long double ld;
  32. typedef pair<ll,ll> pl;
  33. typedef pair<int,int> pi;
  34. typedef vector<ll> vll;
  35. typedef vector<int> vi;
  36.  
  37. const int MOD = 1e9+7;
  38. const ld PI = 3.141592653589793238462643383279502884L;
  39.  
  40. inline ll gcd(ll a, ll b){return b==0 ? a : gcd(b,a%b);}
  41. inline ll lcm(ll a, ll b){return a/gcd(a,b)*b;}
  42.  
  43. const ll LINF = 1e18 + 5;
  44. const int INF = 1e9;
  45. const int N = 5e5 + 5;
  46. const int LOG = __lg(N)+1;
  47.  
  48. const ll MAXN = 3005;
  49.  
  50. //ITIS
  51.  
  52. int t = 1;
  53.  
  54. struct segmentree{
  55.     int n;
  56.     vector<int> tree;
  57.  
  58.     segmentree(int x = 0) {
  59.         n = x;
  60.         tree.assign(4*n+5,0);
  61.     }
  62.  
  63.     void build(int idx,int l,int r) {
  64.         if(l==r) {
  65.             tree[idx] = 1;
  66.             return;
  67.         }
  68.         int mid = (l+r)>>1;
  69.         build(idx << 1,l,mid);
  70.         build(idx << 1 | 1,mid+1,r);
  71.         tree[idx] = tree[idx << 1] + tree[idx << 1 | 1];
  72.     }
  73.  
  74.     void update(int idx,int l,int r,int pos) {
  75.         if(l==r) {
  76.             tree[idx] = 0;
  77.             return;
  78.         }
  79.  
  80.         int mid = (l+r)>>1;
  81.         if(pos <= mid) {
  82.             update(idx << 1, l,mid,pos);
  83.         }
  84.         else {
  85.             update(idx << 1 | 1,mid+1,r,pos);
  86.         }
  87.         tree[idx] = tree[idx << 1] + tree[idx << 1 | 1];
  88.     }
  89.  
  90.     int query(int idx,int l,int r, int ql, int qr) {
  91.         if(qr < l || r < ql) return 0;
  92.         if(ql <= l && qr >= r) return tree[idx];
  93.  
  94.         int mid = (l+r) >> 1;
  95.         return query(idx << 1,l,mid,ql,qr) + query(idx << 1 | 1,mid+1,r,ql,qr);
  96.     }
  97.  
  98.     void update(int pos) {
  99.         update(1,1,n,pos);
  100.     }
  101.  
  102.     int query(int l,int r) {
  103.         if(l>r) return 0;
  104.         return query(1,1,n,l,r);
  105.     }
  106. };
  107.  
  108. int main() {
  109.     boost;
  110.     //cin >> t;
  111.     while (t--)
  112.     {
  113.         int n,m,k;
  114.         cin >> n >> m >> k;
  115.         vector<int> first_col(n+1,m+1);
  116.         vector<int> first_row(m+1,n+1);
  117.  
  118.         for(int i=1;i<=k;++i) {
  119.             int x,y;
  120.             cin >> x >> y;
  121.             first_col[x] = min(first_col[x],y);
  122.             first_row[y] = min(first_row[y],x);
  123.         }
  124.         int d = first_row[1] - 1;
  125.         int r = first_col[1] - 1;
  126.  
  127.         if(d == 0 && r == 0) {
  128.             cout << 1 << endl;
  129.             return 0;
  130.         }
  131.  
  132.         vector<vector<int>> block(d+5);
  133.         for(int col = 1;col<=r;++col) {
  134.             if(first_row[col] <= d) block [first_row[col]].push_back(col);
  135.         }
  136.  
  137.         segmentree seg(r);
  138.  
  139.         if(r > 0) seg.build(1,1,r);
  140.  
  141.         ll ans = 0;
  142.  
  143.         for(int col = 1; col <= r; ++col) {
  144.             ans += first_row[col] - 1;
  145.         }
  146.  
  147.         for(int i=1;i<=d;++i) {
  148.             for(int col : block[i]) {
  149.                 seg.update(col);
  150.             }
  151.             int reach = first_col[i] - 1;
  152.  
  153.             ans += max(0,reach - r);
  154.  
  155.             int lim = min(reach,r);
  156.  
  157.             if(lim > 0) {
  158.                 ans += lim - seg.query(1,lim);
  159.             }
  160.         }
  161.         cout << ans << endl;
  162.     }
  163.     //time;
  164.     return 0;
  165. }
  166.  
  167. /*
  168.     Hav a nice day xD
  169.     Author Bạch Ngọc Đức - Cross
  170. */
Success #stdin #stdout 0s 5340KB
comments (?)
stdin
copy 
5 5 4
2 3
3 4
4 2
5 2
stdout
copy 
17
https://ideone.com/oapcfS
language:
C++ (gcc 8.3)
created:
6 hours ago
visibility:
public

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!