Submission #1275856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275856		itsKiaRash	Plus Minus (BOI17_plusminus)	C++20	100 / 100	174 ms	31708 KiB

plusminus

#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds; // find_by_order   order_of_key
// template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
// #pragma GCC optimize ("O2,unroll-loops")
// #pragma GCC optimize ("Ofast")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define int ll
#define FAST_IO (ios_base::sync_with_stdio(false), cin.tie(NULL));
#define file_init freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define testc int ttt;cin>>ttt;while(ttt--)
#define alll(x)	(x).begin(),(x).end()
#define pqi priority_queue<pii, vector<pii>, greater<pii>>
#define endl '\n'
#define pb push_back
#define ins insert
#define pii pair<int, int>
#define ff first
#define ss second
#define bg begin
#define rbg rbegin
#define sz size()
#define mset(x,y) memset(x,y,sizeof(x))
#define clr clear()
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define vci vector<int>
#define sti set<int>
#define nl cout<<'\n'
#define upb upper_bound
#define lrb lower_bound
ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b);}
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }
const ll inf = 1e18 + 18;
const int maxn = 2e5 + 7, mod = 1e9 + 7; //998244353
int n, m, k, ans, cntx, cnty;
// int pw[maxn];
bool N, M;
map<int, vector<pii>> xs, ys;
sti alx, aly;
ll pw(ll a,ll b){ll res=1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
void chkx(){
    N = true;
    for(auto[x, vec] : xs){
        bool ep, op, on, en; ep = op = on = en = false;
        for(auto[ind, bar] : vec){
            if(bar){
                if(ind % 2 == 0) ep = true; else op = true;
            }
            else{
                if(ind % 2 == 0) en = true; else on = true;
            }
        }
        if(ep && op || en && on || ep && en || op && on) {N = false; break;}
    }
}
void chky(){
    M = true;
    for(auto[y, vec] : ys){
        bool ep, op, on, en; ep = op = on = en = false;
        for(auto[ind, bar] : vec){
            if(bar){
                if(ind % 2 == 0) ep = true; else op = true;
            }
            else{
                if(ind % 2 == 0) en = true; else on = true;
            }
        }
        if(ep && op || en && on || ep && en || op && on) {M = false; break;}
    }
}

int32_t main(){
    FAST_IO
    cin >> n >> m >> k ;
    if(k == 0){cout << (((pw(2, n) + pw(2, m) - 2) % mod + mod) % mod) << endl; return 0;}
    for(int i = 1 ; i <= k ; i ++){
        char c; int x, y; cin >> c >> x >> y ; int bar = 0; alx.ins(x); aly.ins(y);
        if(c == '+') bar = 1;
        xs[x].pb({y, bar});
        ys[y].pb({x, bar});
    } cntx = alx.sz; cnty = aly.sz;
    chkx(); chky();
    // cout << N << ' ' << M << endl;
    if(N){
        ans += pw(2, (n - cntx)); ans %= mod;
    }
    if(M){
        ans += pw(2, (m - cnty)); ans %= mod;
    }
    if(N && M) {ans --; ans += mod; ans %= mod;}
    cout << ans << endl;
    
    return 0;
}

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