oj.uz

Submission #43191

# Submission time Handle Problem Language Result Execution time Memory
43191 2018-03-10T13:37:36 Z jwvg0425 즐거운 사진 수집 (JOI13_collecting) C++14
100 / 100
 3390 ms 257068 KB 
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#include <sstream>
#include <iterator>
#include <regex>
#define MOD 1000000007

using namespace std;

using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

class FenwickTree
{
public:
    FenwickTree()
    {
    }

    FenwickTree(int k)
    {
        data.resize(k);
    }

    i64 sum(int n)
    {
        i64 ans = 0;

        while (n > 0)
        {
            ans += data[n];
            n -= (n & -n);
        }

        return ans;
    }

    void add(int n, i64 num)
    {
        while (n < data.size())
        {
            data[n] += num;
            n += (n & -n);
        }
    }

private:
    vector<i64> data;
};

i64 total = 1;

vector<FenwickTree> lrZeroNs;
vector<FenwickTree> udZeroNs;

void update(int x, int n, int idx, vector<int>& v, FenwickTree& lr, vector<FenwickTree>& lrs, vector<FenwickTree>& uds, int change)
{
    if (n == 1)
        return;

    i64 lrt = lr.sum(x + n - 1) - lr.sum(x - 1);
    i64 udCount = uds[idx].sum(1 << idx);

    //다 같은 색
    if ((lrt == 0 || lrt == n))
    {
        total -= 4 * udCount;
        lrs[idx].add(1 + x / n, 1);
    }
    else if (((v[change] == 1 && lrt == 1) || (v[change] == 0 && lrt == n - 1))) // 원래 통째로 였다가 나뉜거
    {
        total += 4 * udCount;
        lrs[idx].add(1 + x / n, -1);
    }

    int hn = n / 2;

    if (change < x + hn)
        update(x, hn, idx + 1, v, lr, lrs, uds, change);
    else
        update(x + hn, hn, idx + 1, v, lr, lrs, uds, change);
}

int main()
{
    int n, q;
    scanf("%d %d", &n, &q);

    vector<int> lr((1 << n) + 1);
    vector<int> ud((1 << n) + 1);
    FenwickTree lrtree((1 << n) + 1);
    FenwickTree udtree((1 << n) + 1);

    for (int i = 0; i < n; i++)
    {
        lrZeroNs.emplace_back((1 << i) + 1);
        udZeroNs.emplace_back((1 << i) + 1);

        for (int j = 1; j <= (1 << i); j++)
        {
            lrZeroNs[i].add(j, 1);
            udZeroNs[i].add(j, 1);
        }
    }

    for (int i = 0; i < q; i++)
    {
        int t, x;
        scanf("%d %d", &t, &x);

        vector<int>& v = t == 0 ? lr : ud;
        FenwickTree& tree = t == 0 ? lrtree : udtree;
        auto& trees = t == 0 ? lrZeroNs : udZeroNs;
        auto& others = t == 0 ? udZeroNs : lrZeroNs;

        int prev = v[x];

        if (v[x] == 0)
            v[x] = 1;
        else
            v[x] = 0;

        tree.add(x, v[x] - prev); 
        update(1, (1 << n), 0, v, tree, trees, others, x);
        printf("%lld\n", total);
    }

    return 0;
}

Compilation message

collecting.cpp: In member function 'void FenwickTree::add(int, i64)':
collecting.cpp:55:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (n < data.size())
                  ^
collecting.cpp: In function 'int main()':
collecting.cpp:102:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &q);
                           ^
collecting.cpp:124:31: 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 1 ms 248 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 2 ms 424 KB Output is correct
4 Correct 2 ms 496 KB Output is correct
5 Correct 2 ms 568 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 2 ms 600 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 620 KB Output is correct
2 Correct 3 ms 620 KB Output is correct
3 Correct 3 ms 636 KB Output is correct
4 Correct 3 ms 652 KB Output is correct
5 Correct 3 ms 652 KB Output is correct
6 Correct 3 ms 668 KB Output is correct
7 Correct 3 ms 668 KB Output is correct
8 Correct 3 ms 684 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3325 ms 68568 KB Output is correct
2 Correct 3276 ms 86032 KB Output is correct
3 Correct 2693 ms 86032 KB Output is correct
4 Correct 3194 ms 120732 KB Output is correct
5 Correct 3372 ms 137712 KB Output is correct
6 Correct 3388 ms 154156 KB Output is correct
7 Correct 3313 ms 172848 KB Output is correct
8 Correct 3390 ms 190204 KB Output is correct
9 Correct 2706 ms 190204 KB Output is correct
10 Correct 2874 ms 202060 KB Output is correct
11 Correct 3294 ms 240040 KB Output is correct
12 Correct 3313 ms 257068 KB Output is correct
13 Correct 2802 ms 257068 KB Output is correct