Submission #884300

#	Time	Username	Problem	Language	Result	Execution time	Memory
884300		vjudge1	Plus Minus (BOI17_plusminus)	C++17	100 / 100	39 ms	1624 KiB

plusminus

#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define ll long long 
#define pb push_back
#define pii pair<int, int>
#define a3 pair<pair<int, int>, int>

const int K = 1e5 + 4, M = 1e9 + 7;

int n, m, k;
a3 know[K];

int power(int a, ll b, int mod = M) {
    int ret = 1;
    for (; b; b >>= 1, a = 1ll * a * a % mod)
        if (b & 1)
            ret = 1ll * ret * a % mod;
    return ret;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> k;
    for (int i = 0; i < k; ++i) {
        char c;
        cin >> c;
        if (c == '+') {
            know[i].S = 1;
        }
        cin >> know[i].F.F >> know[i].F.S;
    }
    sort(know, know + k);

    int last = 1, it = 0, dp[] = {1, 1}, d[] = {1, 1};
    know[k] = {{n + 1, 0}, -1};

    while (it <= k) {
        if (know[it].F.F != last) {
            if (last == 1) {
                dp[0] = d[0];
                dp[1] = d[1];
            }
            else {
                int save[] = {dp[0], dp[1]};
                dp[0] = d[0] * (save[0] + save[1]) % M;
                dp[1] = d[1] * (save[0] + save[1]) % M;
            }

            int free = know[it].F.F - last - 1;
            if (free > 0) {
                dp[0] = dp[1] = 1ll * (dp[0] + dp[1]) * power(2, free - 1) % M;
            }
            d[0] = d[1] = 1;
            last = know[it].F.F;
        }


        if (know[it].S == 1) {
            d[know[it].F.S % 2] = 0;
        }
        else if (know[it].S == 0) {
            d[!(know[it].F.S % 2)] = 0;
        }
        ++it;
    }
    int ans = (dp[0] + dp[1]) % M;
    // cerr << ans << ' ';

    for (int i = 0; i < k; ++i) {
        if (know[i].F.F % 2 == 0) {
            know[i].S = !know[i].S;
        }
        know[i].F.F = 1;
    }
    sort(know, know + k);

    d[0] = 1;
    d[1] = 1;
    int D = 1, free = m;
    pii before = {0, 0}; // (x, state)

    for (int i = 0; i < k; ++i) {
        pii cur = {know[i].F.S, know[i].S};
        if (cur.F == before.F && cur.S != before.S) {
            D = 0;
        }
        if (cur.F != before.F) {
            --free;
            before = cur;
        }

        if (cur.S == 1) {
            d[cur.F % 2] = 0;
        }
        else if (cur.S == 0) {
            d[!(cur.F % 2)] = 0;
        }
    }

    int add = D * ((power(2, free) - d[0] - d[1] + M) % M) % M;
    ans = (ans + add) % M;
    cout << ans;

    return 0;
}

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