oj.uz

Submission #77515

# Submission time Handle Problem Language Result Execution time Memory
77515 2018-09-28T10:26:35 Z zubec 즐거운 사진 수집 (JOI13_collecting) C++14
100 / 100
 1628 ms 240656 KB 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <bitset>
#include <complex>

using namespace std;

typedef unsigned uint;
typedef long long Int;

const int INF = 1001001001;
const Int INFLL = 1001001001001001001LL;

template<typename T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<typename T> void chmin(T& a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T& a, T b) { if (a < b) a = b; }

int rowflip[(1<<21) + 50], colflip[(1<<21) + 50];
int rowall[21], colall[21];

void flip(int *seg, int *all, int dep, int x)
{
    int p = (1<<dep) + x, sz = 1;
    seg[p] ^= 1; p >>= 1; sz <<= 1; --dep;

    while (p > 0) {
        if (seg[p] % sz == 0) {
            --all[dep];
        }
        seg[p] = seg[2*p] + seg[2*p+1];
        if (seg[p] % sz == 0) {
            ++all[dep];
        }
        p >>= 1; sz <<= 1; --dep;
    }
}

int main()
{
    int N, Q;
    scanf("%d%d", &N, &Q);

    for (int i = 0; i <= N; ++i) {
        rowall[i] = 1 << i;
        colall[i] = 1 << i;
    }

    for (int i = 0; i < Q; ++i) {
        int T, X;
        scanf("%d%d", &T, &X);

        --X;

        if (T == 0) {
            flip(rowflip, rowall, N, X);
        } else {
            flip(colflip, colall, N, X);
        }

        Int leaves = (1LL << N) * (1LL << N);

        for (int j = 0; j < N; ++j) {
            leaves -= (Int)rowall[j] * colall[j] * 3;
        }

        printf("%lld\n", 4 * (leaves - 1) / 3 + 1);
    }

    return 0;
}

Compilation message

collecting.cpp: In function 'int main()':
collecting.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &Q);
     ~~~~~^~~~~~~~~~~~~~~~
collecting.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &T, &X);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 444 KB Output is correct
4 Correct 2 ms 448 KB Output is correct
5 Correct 2 ms 500 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 2 ms 524 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 572 KB Output is correct
2 Correct 3 ms 648 KB Output is correct
3 Correct 3 ms 724 KB Output is correct
4 Correct 3 ms 752 KB Output is correct
5 Correct 3 ms 764 KB Output is correct
6 Correct 3 ms 776 KB Output is correct
7 Correct 3 ms 864 KB Output is correct
8 Correct 4 ms 960 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1485 ms 44140 KB Output is correct
2 Correct 1512 ms 61464 KB Output is correct
3 Correct 1288 ms 68164 KB Output is correct
4 Correct 1509 ms 96120 KB Output is correct
5 Correct 1628 ms 113088 KB Output is correct
6 Correct 1550 ms 129572 KB Output is correct
7 Correct 1627 ms 148412 KB Output is correct
8 Correct 1621 ms 165868 KB Output is correct
9 Correct 1344 ms 170944 KB Output is correct
10 Correct 1538 ms 189752 KB Output is correct
11 Correct 1535 ms 215292 KB Output is correct
12 Correct 1532 ms 232452 KB Output is correct
13 Correct 1452 ms 240656 KB Output is correct