oj.uz

Submission #991335

# Submission time Handle Problem Language Result Execution time Memory
991335 2024-06-02T05:35:01 Z gmroh06 즐거운 사진 수집 (JOI13_collecting) C++14
100 / 100
 808 ms 78420 KB 
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
inline void fastio() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}
 
ll n, q, MAX;
ll row_tree[1 << 21], col_tree[1 << 21];
ll row[21], col[21];
 
void update(ll* tree, ll* cnt, ll loc) {
    loc |= MAX;
    tree[loc] ^= 1;
    ll d = n;
 
    while (loc > 1) {
        loc >>= 1, d--;
 
        if (tree[loc] % (1LL << n - d) == 0) cnt[d]--;
 
        tree[loc] = tree[loc << 1] + tree[loc << 1 | 1];
 
        if (tree[loc] % (1LL << n - d) == 0) cnt[d]++;
    }
}
 
int main() {
    fastio();
 
    cin >> n >> q;
 
    MAX = 1 << n;
 
    for (ll i = 0; i <= 20; i++) {
        row[i] = col[i] = 1LL << i;
    }
 
    while (q--) {
        ll t, x, ans = 1LL << 2 * n;
 
        cin >> t >> x;
 
        t ? update(col_tree, col, x - 1) : update(row_tree, row, x - 1);
 
        for (ll i = 0; i < n; i++) {
            ans += 1LL << 2 * i;
            ans -= row[i] * col[i] * 4;
        }
 
        cout << ans << '\n';
    }
 
    return 0;
}

Compilation message

collecting.cpp: In function 'void update(ll*, ll*, ll)':
collecting.cpp:24:35: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   24 |         if (tree[loc] % (1LL << n - d) == 0) cnt[d]--;
      |                                 ~~^~~
collecting.cpp:28:35: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   28 |         if (tree[loc] % (1LL << n - d) == 0) cnt[d]++;
      |                                 ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 728 ms 60496 KB Output is correct
2 Correct 768 ms 78164 KB Output is correct
3 Correct 603 ms 59220 KB Output is correct
4 Correct 808 ms 78420 KB Output is correct
5 Correct 734 ms 77908 KB Output is correct
6 Correct 643 ms 76828 KB Output is correct
7 Correct 736 ms 78000 KB Output is correct
8 Correct 723 ms 78164 KB Output is correct
9 Correct 594 ms 57856 KB Output is correct
10 Correct 591 ms 60496 KB Output is correct
11 Correct 748 ms 76628 KB Output is correct
12 Correct 691 ms 76676 KB Output is correct
13 Correct 573 ms 60352 KB Output is correct