Submission #884274

#	Time	Username	Problem	Language	Result	Execution time	Memory
884274		vjudge1	Plus Minus (BOI17_plusminus)	C++17	100 / 100	164 ms	30732 KiB

plusminus

/// I'm only brave when I have to be
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL);
#define file_io freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define FOR(i,k,n) for(int i = k; i < n; ++ i)
#define debf cout<<"(0-0)\n";
#define all(x) x.begin(), x.end()
#define dec(x) cout << fixed << setprecision(x);
#define pf push_front
#define ppf pop_front
#define dash " ------- "
#define what(x) cerr << #x << " is " << x << endl;
#define eb emplace_back
//#define int short int
#define int long long
#define sz(s) (int) (s.size())
#define fl cout.flush()

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
typedef unsigned long long ull;
typedef long double ld;

template <class T> using max_heap = priority_queue <T, vector <T>, less <T> >;
template <class T> using min_heap = priority_queue <T, vector <T>, greater <T> >;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

constexpr int MOD = 1e9 + 7, N = 2e5 + 8, M = 1e9, SQ = 300, INF = 2e8 + 8, LGN = 22, mod = 998244353, P = 131113;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, m, k, ptx, pty, ans;
vector <pair <char, int> > vx[N];
vector <pair <char, int> > vy[N];
map <int, int> mpx;
map <int, int> mpy;

int pw (int p, int q){
  int ret = 1;
  int xx = p;
  while (q){
    if (q & 1){
      ret *= xx;
      ret %= MOD;
    }
    xx *= xx;
    xx %= MOD;
    q >>= 1;
  }
  return ret;
}

int32_t main(){
  fast_io;
  cin >> n >> m >> k;
  FOR (i, 0, k){
    char ch;
    int x, y;
    cin >> ch >> x >> y;
    if (mpx[x] == 0){
      mpx[x] = ++ ptx;
    }
    if (mpy[y] == 0){
      mpy[y] = ++ pty;
    }
    vx[mpx[x]].pb({ch, y});
    vy[mpy[y]].pb({ch, x});
  }
  bool xt = true;
  for (int i = 1; i <= ptx; ++ i){
    int zp = -1, zn = -1;
    for (pair <char, int> j : vx[i]){
      if (j.F == '+'){
        if (j.S % 2 == zn || (j.S % 2 != zp && zp != -1)){
          xt = false;
        }
        zp = j.S % 2;
      }
      else {
        if (j.S % 2 == zp || (j.S % 2 != zn && zn != -1)){
          xt = false;
        }
        zn = j.S % 2;
      }
    }
  }
  bool yt = true;
  for (int i = 1; i <= pty; ++ i){
    int zp = -1, zn = -1;
    for (pair <char, int> j : vy[i]){
      if (j.F == '+'){
        if (j.S % 2 == zn || (j.S % 2 != zp && zp != -1)){
          yt = false;
        }
        zp = j.S % 2;
      }
      else {
        if (j.S % 2 == zp || (j.S % 2 != zn && zn != -1)){
          yt = false;
        }
        zn = j.S % 2;
      }
    }
  }
  if (xt){
    ans += pw (2, n - ptx);
  }
  if (yt){
    ans += pw (2, m - pty);
  }
  if (xt && yt){
    -- ans;
    if (k == 0){
      -- ans;
    }
  }
  ans += MOD;
  ans %= MOD;
  cout << ans;
  return 0;
}

// Yesterday is history
// Tomorrow is a mystery
// but today is a gift
// That is why it is called the present

• Subtask 1: 12 / 12
• Subtask 2: 42 / 42
• Subtask 3: 46 / 46