oj.uz

Submission #47729

# Submission time Handle Problem Language Result Execution time Memory
47729 2018-05-06T21:24:25 Z _EmanuelNrx_ Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 725 ms 31980 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;
    
    int sum = 0, nr = 0, nr2 = 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;
        }
       /*
        int a = seg[i].first, b = seg[i].second;
        if (a > b) swap(a, b);
        
        if (a <= 58 and 58 < b)
            ++nr, sum += b;
        else
        if (b <= 58)
            sum += seg[i].second, nr2++;
        else
            sum += seg[i].first;
        */
        aux.push_back(seg[i].first);
        aux.push_back(seg[i].second);
    }
    
   // cerr << nr << endl << nr2 << endl << sum + ans;
    
    if (!n)
        return ans;
    
    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 = (int) aux.size();
    
    sort(seg + 1, seg + n + 1, cmp);
    
    for (int i = 1; i <= n; ++i) {
        num[i] = seg[i];
        seg[i].first = (int) (lower_bound(aux.begin(), aux.end(), seg[i].first) - aux.begin() + 1);
        seg[i].second = (int) (lower_bound(aux.begin(), aux.end(), seg[i].second) - aux.begin() + 1);
    }
    
    for (int i = 1; i <= k; ++i) {
        pos[i] = (int) (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]) {
            bool 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 (max(seg[mid].second, seg[mid].first) <= pos[k])
                lef = mid + 1, psx = mid;
            else
                rig = mid - 1;
        }
        
        if (psx != 0)
            update(1, n), update(psx + 1, n);
    }
    
    return ans;
}

void generate(int n, int k)
{
    srand(unsigned(time(0)));
    cout << n << " " << k << endl;
    
    for (int i = 1; i <= n; ++i)
        cout << 1LL * rand() * rand() % 100 + 1 << " "
             << 1LL * rand() * rand() % 100 + 1 << endl;
    
    for (int i = 1; i <= k; ++i)
        cout << 1LL * rand() * rand() % 100 + 1 << endl;
    exit(0);
}

int main(void)
{
   // freopen("test.in", "r", stdin);
   // freopen("test.out", "w", stdout);
    
    int n, k;
    cin >> n >> k;
    
 //   generate(1000, 1);
    
    if (n <= 1000 and k <= 1000)
        cout << bruteForce(n, k) << endl;
    else
        cout << solve(n, k) << endl;
    
    return 0;
}

Compilation message

fortune_telling2.cpp: In function 'long long int solve(int, int)':
fortune_telling2.cpp:85:9: warning: unused variable 'sum' [-Wunused-variable]
     int sum = 0, nr = 0, nr2 = 0;
         ^~~
fortune_telling2.cpp:85:18: warning: unused variable 'nr' [-Wunused-variable]
     int sum = 0, nr = 0, nr2 = 0;
                  ^~
fortune_telling2.cpp:85:26: warning: unused variable 'nr2' [-Wunused-variable]
     int sum = 0, nr = 0, nr2 = 0;
                          ^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB Output is correct
2 Correct 17 ms 14456 KB Output is correct
3 Correct 17 ms 14508 KB Output is correct
4 Correct 17 ms 14508 KB Output is correct
5 Correct 17 ms 14548 KB Output is correct
6 Correct 17 ms 14620 KB Output is correct
7 Correct 17 ms 14640 KB Output is correct
8 Correct 15 ms 14824 KB Output is correct
9 Correct 14 ms 14824 KB Output is correct
10 Correct 14 ms 14824 KB Output is correct
11 Correct 17 ms 14824 KB Output is correct
12 Correct 16 ms 14824 KB Output is correct
13 Correct 17 ms 14824 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 15484 KB Output is correct
2 Correct 70 ms 16160 KB Output is correct
3 Correct 105 ms 17040 KB Output is correct
4 Correct 133 ms 17416 KB Output is correct
5 Correct 134 ms 17416 KB Output is correct
6 Correct 131 ms 17416 KB Output is correct
7 Correct 130 ms 17416 KB Output is correct
8 Correct 130 ms 17652 KB Output is correct
9 Correct 100 ms 17652 KB Output is correct
10 Correct 101 ms 17652 KB Output is correct
11 Correct 110 ms 17652 KB Output is correct
12 Correct 102 ms 17652 KB Output is correct
13 Correct 108 ms 17652 KB Output is correct
14 Correct 125 ms 17652 KB Output is correct
15 Correct 115 ms 17652 KB Output is correct
16 Correct 122 ms 17652 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 18824 KB Output is correct
2 Correct 359 ms 22376 KB Output is correct
3 Correct 469 ms 23696 KB Output is correct
4 Correct 712 ms 31300 KB Output is correct
5 Correct 214 ms 31300 KB Output is correct
6 Correct 707 ms 31356 KB Output is correct
7 Correct 708 ms 31356 KB Output is correct
8 Correct 725 ms 31356 KB Output is correct
9 Correct 686 ms 31436 KB Output is correct
10 Correct 683 ms 31436 KB Output is correct
11 Correct 638 ms 31980 KB Output is correct
12 Correct 652 ms 31980 KB Output is correct
13 Correct 698 ms 31980 KB Output is correct
14 Correct 513 ms 31980 KB Output is correct
15 Correct 522 ms 31980 KB Output is correct
16 Correct 518 ms 31980 KB Output is correct
17 Correct 531 ms 31980 KB Output is correct
18 Correct 497 ms 31980 KB Output is correct
19 Correct 576 ms 31980 KB Output is correct
20 Correct 568 ms 31980 KB Output is correct