Advertisement
BaoJIaoPisu

Untitled

Aug 18th, 2022
657
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.94 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. using ll = long long;
  6. using ld = long double;
  7. using ull = unsigned long long;
  8.  
  9. using pii = pair<int, int>;
  10. using pll = pair<ll, ll>;
  11. using pld = pair<ld, ld>;
  12.  
  13. #define fi first
  14. #define se second
  15. #define pb push_back
  16. #define pf push_front
  17. #define mp make_pair
  18. #define ins insert
  19.  
  20. #define sz(x) (int)(x.size());
  21. #define all(x) x.begin(), x.end()
  22. #define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
  23.  
  24. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  25.  
  26. int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
  27. int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  28. int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
  29.  
  30. template<class X, class Y>
  31.     bool minimize(X &x, const Y &y) {
  32.         if (x > y)
  33.         {
  34.             x = y;
  35.             return true;
  36.         }
  37.         return false;
  38.     }
  39. template<class X, class Y>
  40.     bool maximize(X &x, const Y &y) {
  41.         if (x < y)
  42.         {
  43.             x = y;
  44.             return true;
  45.         }
  46.         return false;
  47.     }
  48.  
  49. const int MOD = 1e9 + 7; //998244353
  50.  
  51. template<class X, class Y>
  52.     void add(X &x, const Y &y) {
  53.         x = (x + y);
  54.         if(x >= MOD) x -= MOD;
  55.     }
  56.  
  57. template<class X, class Y>
  58.     void sub(X &x, const Y &y) {
  59.         x = (x - y);
  60.         if(x < 0) x += MOD;
  61.     }
  62.  
  63. /* Author : Le Ngoc Bao Anh, 11A5, LQD High School for Gifted Student*/
  64.  
  65. const ll INF = 1e9;
  66. const int N = 1005;
  67.  
  68. int cnt[N][N], f[N][N];
  69. bool visited[N][N][6];
  70. int Up[6], Down[6], Left[6], Right[6];
  71. pii state[6];
  72.  
  73. void solve() {
  74.     int a, b, c, n, m, k;
  75.     cin >> a >> b >> c >> n >> m >> k;
  76.     for(int i = 1; i <= k; i++) {
  77.         int x, y; cin >> x >> y;
  78.         cnt[x][y] = 1;
  79.     }
  80.  
  81.     for(int i = 1; i <= n; i++) {
  82.         for(int j = 1; j <= m; j++) {
  83.             cnt[i][j] = cnt[i - 1][j] + cnt[i][j - 1] - cnt[i - 1][j - 1] + cnt[i][j];
  84.         }
  85.     }
  86.  
  87.     auto ok = [&](int x, int y, int h, int w) -> bool {
  88.         int u = x + h - 1, v = y + w - 1;
  89.         if(x < 1 || y < 1 || u > n || v > m || h < 1 || w < 1) return false;
  90.         int p = cnt[u][v] - cnt[x - 1][v] - cnt[u][y - 1] + cnt[x - 1][y - 1];
  91.         return (p > 0 ? false : true);
  92.     };
  93.  
  94.     auto goUp = [&](int &x, int &y, int &direct) -> bool {
  95.         if(!ok(x - 1, y, state[direct].fi, state[direct].se)) return false;
  96.         x--; return true;
  97.     };
  98.  
  99.     auto goDown = [&](int &x, int &y, int &direct) -> bool {
  100.         if(!ok(x + 1, y, state[direct].fi, state[direct].se)) return false;
  101.         x++; return true;
  102.     };
  103.  
  104.     auto goLeft = [&](int &x, int &y, int &direct) -> bool {
  105.         if(!ok(x, y - 1, state[direct].fi, state[direct].se)) return false;
  106.         y--; return true;
  107.     };
  108.  
  109.     auto goRight = [&](int &x, int &y, int &direct) -> bool {
  110.         if(!ok(x, y + 1, state[direct].fi, state[direct].se)) return false;
  111.         y++; return true;
  112.     };
  113.  
  114.     // DIRECT : 0 -> a * b
  115.     //          1 -> b * a
  116.     //          2 -> a * c
  117.     //          3 -> c * a
  118.     //          4 -> b * c
  119.     //          5 -> c * b
  120.     state[0] = make_pair(a, b);
  121.     state[1] = make_pair(b, a);
  122.     state[2] = make_pair(a, c);
  123.     state[3] = make_pair(c, a);
  124.     state[4] = make_pair(b, c);
  125.     state[5] = make_pair(c, b);
  126.     Right[0] = 2; Right[1] = 4; Right[2] = 0; Right[3] = 5; Right[4] = 1; Right[5] = 3;
  127.     for(int i = 0; i < 6; i++) Left[i] = Right[i];
  128.     Down[0] = 5; Down[1] = 3; Down[2] = 4; Down[3] = 1; Down[4] = 2; Down[5] = 0;
  129.     for(int i = 0; i < 6; i++) Up[i] = Down[i];
  130.  
  131.     auto flipLeft = [&](int &x, int &y, int &direct) -> bool {
  132.         int nDirect = Left[direct];
  133.         if(!ok(x, y - state[nDirect].se, state[nDirect].fi, state[nDirect].se)) return false;
  134.         direct = nDirect;
  135.         y -= state[direct].se;
  136.         return true;
  137.     };
  138.  
  139.     auto flipRight = [&](int &x, int &y, int &direct) -> bool {
  140.         int nDirect = Right[direct];
  141.         if(!ok(x, y + state[direct].se, state[nDirect].fi, state[nDirect].se)) return false;
  142.         y += state[direct].se;
  143.         direct = nDirect;
  144.         return true;
  145.     };
  146.  
  147.     auto flipUp = [&](int &x, int &y, int &direct) -> bool {
  148.         int nDirect = Up[direct];
  149.         if(!ok(x - state[nDirect].fi, y, state[nDirect].fi, state[nDirect].se)) return false;
  150.         direct = nDirect;
  151.         x -= state[direct].fi;
  152.         return true;
  153.     };
  154.  
  155.     auto flipDown = [&](int &x, int &y, int &direct) -> bool {
  156.         int nDirect = Down[direct];
  157.         if(!ok(x + state[direct].fi, y, state[nDirect].fi, state[nDirect].se)) return false;
  158.         x += state[direct].fi;
  159.         direct = nDirect;
  160.         return true;
  161.     };
  162.  
  163.     queue<pair<pii, int>> q;
  164.     auto addState = [&](int x, int y, int direct) -> void {
  165.         if(visited[x][y][direct]) return;
  166.         visited[x][y][direct] = true;
  167.         q.push(mp(mp(x, y), direct));
  168.     };
  169.  
  170.     q.push(mp(mp(1, 1), 0));
  171.     visited[1][1][0] = true;
  172.     while(!q.empty()) {
  173.         int x = q.front().fi.fi, y = q.front().fi.se;
  174.         int direct = q.front().se; q.pop();
  175.         f[x][y]++;
  176.         f[x + state[direct].fi][y + state[direct].se]++;
  177.         f[x + state[direct].fi][y]--;
  178.         f[x][y + state[direct].se]--;
  179.  
  180.         int u = x, v = y, curr = direct;
  181.         if(goUp(u, v, curr)) addState(u, v, curr);
  182.  
  183.         u = x, v = y, curr = direct;
  184.         if(goDown(u, v, curr)) addState(u, v, curr);
  185.  
  186.         u = x, v = y, curr = direct;
  187.         if(goLeft(u, v, curr)) addState(u, v, curr);
  188.  
  189.         u = x, v = y, curr = direct;
  190.         if(goRight(u, v, curr)) addState(u, v, curr);
  191.  
  192.         u = x, v = y, curr = direct;
  193.         if(flipUp(u, v, curr)) addState(u, v, curr);
  194.  
  195.         u = x, v = y, curr = direct;
  196.         if(flipDown(u, v, curr)) addState(u, v, curr);
  197.  
  198.         u = x, v = y, curr = direct;
  199.         if(flipLeft(u, v, curr)) addState(u, v, curr);
  200.  
  201.         u = x, v = y, curr = direct;
  202.         if(flipRight(u, v, curr)) addState(u, v, curr);
  203.     }
  204.  
  205.     int ans = 0;
  206.     for(int i = 1; i <= n; i++) {
  207.         for(int j = 1; j <= m; j++) {
  208.             f[i][j] = f[i][j] + f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];
  209.             ans += (f[i][j] > 0);
  210.         }
  211.     }
  212.  
  213.     cout << ans;
  214. }
  215.  
  216. int main()
  217. {
  218.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  219.     #ifndef ONLINE_JUDGE
  220.     freopen("input.txt", "r", stdin);
  221.     freopen("output.txt", "w", stdout);
  222.     #else
  223.     //online
  224.     #endif
  225.  
  226.     int tc = 1, ddd = 0;
  227.     // cin >> tc;
  228.     while(tc--) {
  229.         //ddd++;
  230.         //cout << "Case #" << ddd << ": ";
  231.         solve();
  232.     }
  233. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement