oj.uz

Submission #52362

# Submission time Handle Problem Language Result Execution time Memory
52362 2018-06-25T15:28:10 Z upsolving(#1344) Fortune Telling 2 (JOI14_fortune_telling2) C++11
4 / 100
 354 ms 12380 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 <numeric>

using namespace std;

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

class Mapping
{
public:
    void init(const vector<int>& raw, int base = 0)
    {
        start = base;
        arr = raw;
        sort(arr.begin(), arr.end());
        arr.erase(unique(arr.begin(), arr.end()), arr.end());

        for (int i = 0; i < arr.size(); i++)
            idx[arr[i]] = base + i;
    }

    int get_idx(int k)
    {
        return idx[k];
    }

    int get_value(int idx)
    {
        return arr[idx - start];
    }

private:
    int start;
    vector<int> arr;
    map<int, int> idx;
};

template<typename T>
class SegmentTree
{
public:
    void init(const vector<T>& raw)
    {
        assert(!is_init);
        is_init = true;
        n = raw.size();
        int h = (int)ceil(log2(n));
        int tree_size = (1 << (h + 1));
        data.resize(tree_size);
        value = raw;

        init_internal(raw, 1, 0, n - 1);
    }

    T add(int idx, const T& added)
    {
        assert(is_init);
        return update(idx, value[idx] + added);
    }

    T update(int idx, const T& newVal)
    {
        assert(is_init);
        return update_internal(1, 0, n - 1, idx, newVal);
    }

    T query(int left, int right)
    {
        assert(is_init);
        return query_internal(1, 0, n - 1, left, right);
    }

    virtual T merge(const T& left, const T& right) = 0;
    virtual T merge_with_idx(const T& left, const T& right, int left_idx, int right_idx)
    {
        return merge(left, right);
    }

private:
    vector<T> data;
    vector<T> value;
    int n;
    bool is_init = false;

    T init_internal(const vector<T>& raw, int node, int start, int end)
    {
        int mid = (start + end) / 2;
        if (start == end)
            return data[node] = raw[start];
        else
            return data[node] = merge_with_idx(init_internal(raw, node * 2, start, mid),
                init_internal(raw, node * 2 + 1, mid + 1, end), node * 2, node * 2 + 1);
    }

    T update_internal(int node, int start, int end, int index, const T& newVal)
    {
        if (index < start || index > end)
            return data[node];

        if (start == end)
        {
            data[node] = newVal;
            value[index] = newVal;
        }
        else
        {
            int mid = (start + end) / 2;
            data[node] = merge_with_idx(update_internal(node * 2, start, mid, index, newVal),
                update_internal(node * 2 + 1, mid + 1, end, index, newVal), node * 2, node * 2 + 1);
        }

        return data[node];
    }

    T query_internal(int node, int start, int end, int left, int right)
    {
        if (left <= start && end <= right)
            return data[node];

        int mid = (start + end) / 2;

        if (mid < left)
            return query_internal(node * 2 + 1, mid + 1, end, left, right);

        if (mid + 1 > right)
            return query_internal(node * 2, start, mid, left, right);

        return merge_with_idx(query_internal(node * 2, start, mid, left, right),
            query_internal(node * 2 + 1, mid + 1, end, left, right), node * 2, node * 2 + 1);
    }
};

class MaxTree : public SegmentTree<int>
{
public:
    virtual int merge(const int& l, const int& r) override
    {
        return max(l, r);
    }
};

class SumTree : public SegmentTree<int>
{
public:
    virtual int merge(const int& l, const int& r) override
    {
        return l + r;
    }
};

int card[200005][2];
int view[200005];
int s[200005], e[200005];

int main()
{
    int n, k;

    scanf("%d %d", &n, &k);

    vector<int> numbers;
    Mapping mapping;

    for (int i = 0; i < n; i++)
    {
        scanf("%d %d", &card[i][0], &card[i][1]);

        s[i] = min(card[i][0], card[i][1]);
        e[i] = max(card[i][0], card[i][1]);

        numbers.push_back(card[i][0]);
        numbers.push_back(card[i][1]);
    }

    vector<int> q;

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

        q.push_back(t);

        numbers.push_back(t);
    }

    vector<int> raw(numbers.size() + 5, 0);

    SumTree sumTree;
    MaxTree maxTree;

    sumTree.init(raw);
    maxTree.init(raw);

    mapping.init(numbers);

    for (int i = 0; i < k; i++)
    {
        maxTree.update(mapping.get_idx(q[i]), i);
        sumTree.add(mapping.get_idx(q[i]), 1);
    }

    vector<ii> ts;

    for (int i = 0; i < n; i++)
    {
        int l = mapping.get_idx(s[i]);
        int r = mapping.get_idx(e[i]);

        if (l == r)
            continue;

        int s = maxTree.query(l, r);

        if (s != 0 && card[i][0] < card[i][1])
            view[i] = 1;

        ts.emplace_back(s, i);
    }

    sort(ts.begin(), ts.end());

    int qx = 0;
    for (auto& ti : ts)
    {
        while (qx < ti.first)
        {
            sumTree.add(mapping.get_idx(q[qx]), -1);
            qx++;
        }

        int swapNum = sumTree.query(mapping.get_idx(e[ti.second]), raw.size() - 1);

        view[ti.second] = (view[ti.second] + swapNum) % 2;
    }

    i64 ans = 0;

    for (int i = 0; i < n; i++)
        ans += card[i][view[i]];

    printf("%lld\n", ans);

    return 0;
}

Compilation message

fortune_telling2.cpp: In member function 'void Mapping::init(const std::vector<int>&, int)':
fortune_telling2.cpp:37:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < arr.size(); i++)
                         ~~^~~~~~~~~~~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:178:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:185:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &card[i][0], &card[i][1]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:199:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &t);
         ~~~~~^~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 5 ms 616 KB Output is correct
3 Correct 6 ms 800 KB Output is correct
4 Correct 5 ms 800 KB Output is correct
5 Correct 6 ms 800 KB Output is correct
6 Correct 5 ms 820 KB Output is correct
7 Correct 7 ms 820 KB Output is correct
8 Correct 7 ms 820 KB Output is correct
9 Correct 5 ms 820 KB Output is correct
10 Correct 4 ms 820 KB Output is correct
11 Correct 5 ms 828 KB Output is correct
12 Correct 5 ms 828 KB Output is correct
13 Correct 5 ms 828 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 5 ms 616 KB Output is correct
3 Correct 6 ms 800 KB Output is correct
4 Correct 5 ms 800 KB Output is correct
5 Correct 6 ms 800 KB Output is correct
6 Correct 5 ms 820 KB Output is correct
7 Correct 7 ms 820 KB Output is correct
8 Correct 7 ms 820 KB Output is correct
9 Correct 5 ms 820 KB Output is correct
10 Correct 4 ms 820 KB Output is correct
11 Correct 5 ms 828 KB Output is correct
12 Correct 5 ms 828 KB Output is correct
13 Correct 5 ms 828 KB Output is correct
14 Correct 54 ms 3540 KB Output is correct
15 Correct 132 ms 6544 KB Output is correct
16 Correct 248 ms 9820 KB Output is correct
17 Correct 327 ms 12380 KB Output is correct
18 Correct 354 ms 12380 KB Output is correct
19 Correct 309 ms 12380 KB Output is correct
20 Correct 302 ms 12380 KB Output is correct
21 Correct 293 ms 12380 KB Output is correct
22 Correct 203 ms 12380 KB Output is correct
23 Incorrect 173 ms 12380 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 5 ms 616 KB Output is correct
3 Correct 6 ms 800 KB Output is correct
4 Correct 5 ms 800 KB Output is correct
5 Correct 6 ms 800 KB Output is correct
6 Correct 5 ms 820 KB Output is correct
7 Correct 7 ms 820 KB Output is correct
8 Correct 7 ms 820 KB Output is correct
9 Correct 5 ms 820 KB Output is correct
10 Correct 4 ms 820 KB Output is correct
11 Correct 5 ms 828 KB Output is correct
12 Correct 5 ms 828 KB Output is correct
13 Correct 5 ms 828 KB Output is correct
14 Correct 54 ms 3540 KB Output is correct
15 Correct 132 ms 6544 KB Output is correct
16 Correct 248 ms 9820 KB Output is correct
17 Correct 327 ms 12380 KB Output is correct
18 Correct 354 ms 12380 KB Output is correct
19 Correct 309 ms 12380 KB Output is correct
20 Correct 302 ms 12380 KB Output is correct
21 Correct 293 ms 12380 KB Output is correct
22 Correct 203 ms 12380 KB Output is correct
23 Incorrect 173 ms 12380 KB Output isn't correct
24 Halted 0 ms 0 KB -