Submission #1066585

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066585		12345678	Plus Minus (BOI17_plusminus)	C++17	100 / 100	87 ms	16720 KiB

plusminus

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e5+5, mod=1e9+7;

ll n, m, k, x[nx], y[nx], szn, szm, res;
char c[nx];
map<ll, ll> mpx, mpy;
set<ll> s;

ll binpow(ll a, ll b)
{
    if (b==0) return 1;
    ll tmp=binpow(a, b/2);
    if (b%2) return (((tmp*tmp)%mod)*a)%mod;
    else return (tmp*tmp)%mod;
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m>>k;
    for (int i=1; i<=k; i++)
    {
        cin>>c[i]>>x[i]>>y[i];
        if (c[i]=='+') s.insert((x[i]+y[i])%2);
        else s.insert((x[i]+y[i]+1)%2);
        if (c[i]=='+') mpx[x[i]]|=(1<<(y[i]%2));
        else mpx[x[i]]|=(1<<((y[i]+1)%2));
        if (c[i]=='+') mpy[y[i]]|=(1<<(x[i]%2));
        else mpy[y[i]]|=(1<<((x[i]+1)%2));
    }
    szn=n-mpx.size();
    for (auto [_, t]:mpx) if (t==3) szn=-1;
    if (szn!=-1) res=(res+binpow(2, szn));
    szm=m-mpy.size();
    for (auto [_, t]:mpy) if (t==3) szm=-1;
    if (szm!=-1) res=(res+binpow(2, szm));
    res=(res-(2-s.size())+mod)%mod;
    cout<<res;
}

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