oj.uz

Submission #47667

# Submission time Handle Problem Language Result Execution time Memory
47667 2018-05-06T08:08:06 Z _EmanuelNrx_ Fortune Telling 2 (JOI14_fortune_telling2) C++14
4 / 100
 262 ms 19296 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);
            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, m;
    cin >> n >> k;

    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:153:15: warning: unused variable 'm' [-Wunused-variable]
     int n, k, m;
               ^

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 14564 KB Output is correct
3 Correct 20 ms 14628 KB Output is correct
4 Correct 19 ms 14708 KB Output is correct
5 Correct 19 ms 14740 KB Output is correct
6 Correct 18 ms 14776 KB Output is correct
7 Correct 23 ms 14936 KB Output is correct
8 Correct 16 ms 14936 KB Output is correct
9 Correct 15 ms 14960 KB Output is correct
10 Correct 15 ms 15004 KB Output is correct
11 Correct 23 ms 15040 KB Output is correct
12 Correct 22 ms 15048 KB Output is correct
13 Correct 18 ms 15100 KB Output is correct

Subtask #2
0 / 31.0

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

Subtask #3
0 / 65.0

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