제출 #884332

#제출 시각아이디문제언어결과실행 시간메모리
884332ArminPlus Minus (BOI17_plusminus)C++17
100 / 100
76 ms24880 KiB
/// 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]; unordered_map <int, int> mpx; unordered_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
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...