fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <map>
  5. using namespace std;
  6. typedef long long ll;
  7. typedef struct _segtree{
  8.     struct _segtree * left;
  9.     struct _segtree * right;
  10.     ll sum;
  11. }segtree;
  12.  
  13. segtree * insert(segtree * t, int l, int r, int x){
  14.     if (l == r){
  15.         segtree * v = new segtree(*t);
  16.         v->left = nullptr;
  17.         v->right = nullptr;
  18.         v->sum = t->sum + 1;
  19.         return v;
  20.     }
  21.     segtree * v = new segtree(*t);
  22.     int mid = (l+r)>>1;
  23.     if (x <= mid){
  24.         v->left = insert(v->left, l, mid, x);
  25.     }else{
  26.         v->right = insert(v->right, mid+1, r, x);
  27.     }
  28.     v->sum = v->left->sum + v->right->sum;
  29.     return v;
  30. }
  31. segtree * build(int l, int r){
  32.     if (l == r){
  33.         segtree * v = new segtree();
  34.         v->left = nullptr;
  35.         v->right = nullptr;
  36.         v->sum = 0;
  37.         return v;
  38.     }
  39.     segtree * v = new segtree();
  40.     int mid = (l+r)>>1;
  41.     v->left = build(l, mid);
  42.     v->right = build( mid+1, r);
  43.     v->sum = 0;
  44.     return v;
  45. }
  46. ll lessthan(segtree * t, int l, int r, int ll){
  47.     if ( r <= ll)
  48.         return t->sum;
  49.     if(l == r)
  50.         return 0;
  51.     int mid = (l+r)>>1;
  52.     long long ans = 0;
  53.     if (mid < ll){
  54.         ans += lessthan(t->left, l, mid, ll);
  55.         ans += lessthan(t->right, mid+1, r, ll);
  56.     }else{
  57.         ans += lessthan(t->left, l, mid, ll);
  58.     }
  59.     return ans;
  60.  
  61. }
  62. typedef pair<int,int> pii;
  63. #define MAXN 200010
  64. segtree * e[MAXN];
  65. vector<pii> a;
  66. #define x first
  67. #define y second
  68. int main()
  69. {
  70.     #ifndef ONLINE_JUDGE
  71.         freopen("input.txt","r",stdin);
  72.         freopen("output.txt","w",stdout);
  73.     #endif
  74.     int h, w, m;
  75.     cin >> h >> w >> m;
  76.     int hm = w+1;
  77.     int vm = h+1;
  78.     for(int i = 0; i < m; ++ i){
  79.         int _x, _y; cin>>_x>>_y;
  80.         a.push_back(make_pair(_x,_y));
  81.         if(_x == 1){
  82.             hm = min(hm, _y);
  83.         }
  84.         if(_y == 1){
  85.             vm = min(vm, _x);
  86.         }
  87.     }
  88.     segtree * beg = build(1, h+2);
  89.     vector<int> r(w+1);
  90.     vector<int> dow(h+1);
  91.     for(int i = 1; i <= w; ++ i)   
  92.          r[i] = h+1;
  93.     for(int i = 1; i <= h; ++ i)
  94.         dow[i] = w+1;
  95.     for(int i = 0; i < m; ++ i){
  96.         r[a[i].y] = min(r[a[i].y] , a[i].x); 
  97.         dow[a[i].x] = min(dow[a[i].x], a[i].y);
  98.     }  
  99.     for(int i = 1; i <= w; ++ i){
  100.         e[i] = insert(beg, 1, h+2, r[i]);
  101.         beg = e[i];
  102.     }
  103.     e[w+1] = e[w];
  104.     ll subs = 0;
  105.     ll ret = 0;
  106.     for(int i = 1; i < vm; ++i){
  107.         ll uu = lessthan(e[dow[i]-1],1,h+2,i-1);
  108.         subs += dow[i] - uu -1; 
  109.         ret += dow[i]-1;
  110.     }
  111.     for(int i = 1; i < hm; ++i)
  112.         ret += r[i]-1;
  113.     cout << ret - subs <<endl;
  114.     return 0;
  115. }
Success #stdin #stdout 0s 5008KB
comments (?)
stdin
copy 
4 3 1
1 2
stdout
copy 
7
https://ideone.com/AH50pe
language:
C++ (gcc 8.3)
created:
3 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!