oj.uz

Submission #47673

# Submission time Handle Problem Language Result Execution time Memory
47673 2018-05-06T08:29:01 Z _EmanuelNrx_ Fortune Telling 2 (JOI14_fortune_telling2) C++14
4 / 100
 245 ms 18652 KB 
#include <bits/stdc++.h>
using namespace std;

const int DIM = 600005;

pair<int, int> seg[DIM], num[DIM]; vector<int> aux, lst[DIM];
int sgt[DIM << 2], bit[DIM], arr[DIM], pos[DIM];

inline bool cmp(pair<int, int> sg1, pair<int, int> sg2)
{
    return max(sg1.first, sg1.second) < max(sg2.first, sg2.second);
}

void update(int nod, int lef, int rig, int pos, int val)
{
    if (lef == rig)
        sgt[nod] = max(sgt[nod], val);
    else {
        int mid = (lef + rig) >> 1;

        if (pos <= mid)
            update(nod << 1, lef, mid, pos, val);
        else
            update(nod << 1 | 1, mid + 1, rig, pos, val);

        sgt[nod] = max(sgt[nod << 1], sgt[nod << 1 | 1]);
    }
}

int query(int nod, int lef, int rig, int _lef, int _rig)
{
    if (_lef <= lef and rig <= _rig)
        return sgt[nod];
    else {
        int mid = (lef + rig) >> 1;

        if (_rig <= mid)
            return query(nod << 1, lef, mid, _lef, _rig);
        if (_lef >  mid)
            return query(nod << 1 | 1, mid + 1, rig, _lef, _rig);

        return max(query(nod << 1, lef, mid, _lef, _rig),
                   query(nod << 1 | 1, mid + 1, rig, _lef, _rig));
    }
}

void update(int pos, int n)
{
    for (int i = pos; i <= n; i += (i & -i))
        bit[i] ^= 1;
}

int query(int pos, int x = 0)
{
    for (int i = pos; i >= 1; i -= (i & -i))
        x ^= bit[i];
    return x;
}

long long bruteForce(int n, int k)
{
    for (int i = 1; i <= n; ++i)
        cin >> seg[i].first >> seg[i].second;

    while (k--) {
        int x;
        cin >> x;

        for (int i = 1; i <= n; ++i)
            if (seg[i].first <= x)
                swap(seg[i].first, seg[i].second);
    }

    long long ans = 0;
    for (int i = 1; i <= n; ++i)
        ans += seg[i].first;

    return ans;
}

long long solve(int n, int k)
{
    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> seg[i].first >> seg[i].second;

        if (seg[i].first == seg[i].second) {
            ans += seg[i--].first; --n;
            continue;
        }

        aux.push_back(seg[i].first);
        aux.push_back(seg[i].second);
    }

    for (int i = 1; i <= k; ++i) {
        cin >> pos[i];
        aux.push_back(pos[i]);
    }

    sort(aux.begin(), aux.end());
    aux.resize(unique(aux.begin(), aux.end()) - aux.begin()); int m = aux.size();

    sort(seg + 1, seg + n + 1, cmp);

    for (int i = 1; i <= n; ++i) {
        num[i] = seg[i];
        seg[i].first = lower_bound(aux.begin(), aux.end(), seg[i].first) - aux.begin() + 1;
        seg[i].second = lower_bound(aux.begin(), aux.end(), seg[i].second) - aux.begin() + 1;
    }

    for (int i = 1; i <= k; ++i) {
        pos[i] = lower_bound(aux.begin(), aux.end(), pos[i]) - aux.begin() + 1;
        update(1, 1, m, pos[i], i);
    }

    for (int i = 1; i <= n; ++i) {
        int a = seg[i].first, b = seg[i].second;

        if (a > b)
            swap(a, b);
        lst[query(1, 1, m, a, b - 1)].push_back(i);
    }

    for (; k >= 0; --k) {
        for (int x : lst[k]) {
            int val = query(x);
            if (k) val ^= (num[x].second > num[x].first);
            ans += val ? num[x].second : num[x].first;
        }

        int psx = 0;
        for (int lef = 1, rig = n; lef <= rig; ) {
            int mid = (lef + rig) >> 1;

            if (seg[mid].second <= pos[k])
                lef = mid + 1, psx = mid;
            else
                rig = mid - 1;
        }

        if (psx != 0)
            update(1, n), update(psx + 1, n);
    }

    return ans;
}

int main(void)
{
  //  freopen("test.in", "r", stdin);
  //  freopen("test.out", "w", stdout);

    int n, k;
    cin >> n >> k;

    bool ok = true;
    if (n <= 1000 && k <= 1000)
        cout << bruteForce(n, k) << endl;
    else
        cout << solve(n, k) << endl;

    return 0;
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:157:10: warning: unused variable 'ok' [-Wunused-variable]
     bool ok = true;
          ^~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB Output is correct
2 Correct 16 ms 14456 KB Output is correct
3 Correct 18 ms 14512 KB Output is correct
4 Correct 18 ms 14588 KB Output is correct
5 Correct 18 ms 14680 KB Output is correct
6 Correct 18 ms 14720 KB Output is correct
7 Correct 18 ms 14752 KB Output is correct
8 Correct 16 ms 14752 KB Output is correct
9 Correct 16 ms 14752 KB Output is correct
10 Correct 15 ms 14752 KB Output is correct
11 Correct 18 ms 14784 KB Output is correct
12 Correct 17 ms 14784 KB Output is correct
13 Correct 18 ms 14784 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 15468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 245 ms 18652 KB Output isn't correct
2 Halted 0 ms 0 KB -