oj.uz

답안 #650460

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
650460 2022-10-13T19:36:43 Z Lobo Plus Minus (BOI17_plusminus) C++17
100 / 100
 404 ms 36824 KB 
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = -1;
const int mod = 1e9+7;

int n, m, k;

int fastexp(int x) {
    int pw = 2;
    int ans = 1;
    for(int i = 0; i <= 30; i++) {
        if((1<<i)&x) {
            ans*= pw;
            ans%= mod;
        }
        pw*=pw;
        pw%= mod;
    }
    return ans;
}

void solve() {
    cin >> n >> m >> k;
    map<int,pair<int,int>> rwp,rwm,clp,clm;
    set<int> rw,cl;
    for(int i = 1; i <= k; i++) {
        char tp; cin >> tp;
        int x,y; cin >> y >> x;
        cl.insert(x);
        rw.insert(y);
        if(tp == '+') {
            if(y%2 == 1) clp[x].fr = 1;
            else clp[x].sc = 1;
            if(x%2 == 1) rwp[y].fr = 1;
            else rwp[y].sc = 1;
        }
        else {
            if(y%2 == 1) clm[x].fr = 1;
            else clm[x].sc = 1;
            if(x%2 == 1) rwm[y].fr = 1;
            else rwm[y].sc = 1;
        }
    }


    int cnf1 = 1;
    int cnf2 = 1;

    int ans1 = 1;
    int antm = 0;
    for(auto i : cl) {
        ans1*= fastexp(i-antm-1);
        ans1%= mod;
        int ok0 = 1;
        if(clm[i].sc || clp[i].fr) ok0 = 0;
        int ok1 = 1;
        if(clm[i].fr || clp[i].sc) ok1 = 0;

        ans1*= (ok0+ok1);
        ans1%= mod;

        if(i%2 == 1) {
            if(!ok1) cnf1 = 0;
            if(!ok0) cnf2 = 0;
        }
        else {
            if(!ok1) cnf2 = 0;
            if(!ok0) cnf1 = 0;
        }
        antm = i;
    }
    ans1*= fastexp(m+1-antm-1);
    ans1%= mod;

    int ans2 = 1;
    int antn = 0;
    for(auto i : rw) {
        ans2*= fastexp(i-antn-1);
        ans2%= mod;
        int ok0 = 1;
        if(rwm[i].sc || rwp[i].fr) ok0 = 0;
        int ok1 = 1;
        if(rwm[i].fr || rwp[i].sc) ok1 = 0;

        ans2*= (ok0+ok1);
        ans2%= mod;
        antn = i;
    }
    ans2*= fastexp(n+1-antn-1);
    ans2%= mod;

    cout << (ans1+ans2-cnf1-cnf2+mod)%mod << endl;
}

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

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #2
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 2 ms 456 KB Output is correct
16 Correct 66 ms 1612 KB Output is correct
17 Correct 53 ms 1524 KB Output is correct
18 Correct 47 ms 1536 KB Output is correct
19 Correct 47 ms 1488 KB Output is correct
20 Correct 48 ms 1516 KB Output is correct

Subtask #3
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 2 ms 456 KB Output is correct
16 Correct 66 ms 1612 KB Output is correct
17 Correct 53 ms 1524 KB Output is correct
18 Correct 47 ms 1536 KB Output is correct
19 Correct 47 ms 1488 KB Output is correct
20 Correct 48 ms 1516 KB Output is correct
21 Correct 258 ms 22308 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 252 ms 21960 KB Output is correct
24 Correct 269 ms 21784 KB Output is correct
25 Correct 271 ms 21984 KB Output is correct
26 Correct 335 ms 30776 KB Output is correct
27 Correct 315 ms 30752 KB Output is correct
28 Correct 306 ms 30924 KB Output is correct
29 Correct 303 ms 30824 KB Output is correct
30 Correct 404 ms 36824 KB Output is correct