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. ll greatequalthan(segtree * t, int l, int r, int rr){
  63.     if ( rr <= l)
  64.         return t->sum;
  65.     if(l == r)
  66.         return 0;
  67.     int mid = (l+r)>>1;
  68.     long long ans = 0;
  69.     if (mid >= rr){
  70.         ans += greatequalthan(t->left, l, mid, rr);
  71.         ans += greatequalthan(t->right, mid+1, r, rr);
  72.     }else{
  73.         ans += greatequalthan(t->right, mid+1, r, rr);
  74.     }
  75.     return ans;
  76.  
  77. }
  78. typedef pair<int,int> pii;
  79. #define MAXN 200010
  80. segtree * e[MAXN];
  81. vector<pii> a;
  82. #define x first
  83. #define y second
  84. int main()
  85. {
  86.     #ifndef ONLINE_JUDGE
  87.         freopen("input.txt","r",stdin);
  88.         freopen("output.txt","w",stdout);
  89.     #endif
  90.     int h, w, m;
  91.     cin >> h >> w >> m;
  92.     int hm = w+1;
  93.     int vm = h+1;
  94.     for(int i = 0; i < m; ++ i){
  95.         int _x, _y; cin>>_x>>_y;
  96.         a.push_back(make_pair(_x,_y));
  97.         if(_x == 1){
  98.             hm = min(hm, _y);
  99.         }
  100.         if(_y == 1){
  101.             vm = min(vm, _x);
  102.         }
  103.     }
  104.     segtree * beg = build(1, h+2);
  105.     vector<int> r(w+1);
  106.     vector<int> dow(h+1);
  107.     for(int i = 1; i <= w; ++ i)   
  108.          r[i] = h+1;
  109.     for(int i = 1; i <= h; ++ i)
  110.         dow[i] = w+1;
  111.     for(int i = 0; i < m; ++ i){
  112.         r[a[i].y] = min(r[a[i].y] , a[i].x); 
  113.         dow[a[i].x] = min(dow[a[i].x], a[i].y);
  114.     }  
  115.     for(int i = 1; i <= w; ++ i){
  116.         e[i] = insert(beg, 1, h+2, r[i]);
  117.         beg = e[i];
  118.     }
  119.     e[w+1] = e[w];
  120.     ll subs = 0;
  121.     ll ret = 0;
  122.     for(int i = 1; i < vm; ++i){
  123.         ll uu = greatequalthan(e[min(dow[i]-1, hm-1)],1,h+2,i);
  124.         subs += uu; 
  125.         ret += dow[i]-1;
  126.     }
  127.     for(int i = 1; i < hm; ++i)
  128.         ret += r[i]-1;
  129.     cout << ret - subs <<endl;
  130.     return 0;
  131. }
Success #stdin #stdout 0s 4636KB
comments (?)
stdin
copy 
4 3 2
1 2
2 1
stdout
copy 
1
https://ideone.com/SH52qH
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!