oj.uz

Submission #47730

# Submission time Handle Problem Language Result Execution time Memory
47730 2018-05-06T21:29:59 Z EmanuelNrx Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 726 ms 31800 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 23 ms 14640 KB Output is correct
4 Correct 18 ms 14640 KB Output is correct
5 Correct 18 ms 14708 KB Output is correct
6 Correct 17 ms 14708 KB Output is correct
7 Correct 18 ms 14708 KB Output is correct
8 Correct 17 ms 14708 KB Output is correct
9 Correct 16 ms 14716 KB Output is correct
10 Correct 14 ms 14716 KB Output is correct
11 Correct 17 ms 14716 KB Output is correct
12 Correct 19 ms 14716 KB Output is correct
13 Correct 18 ms 14724 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 15484 KB Output is correct
2 Correct 76 ms 16164 KB Output is correct
3 Correct 106 ms 16972 KB Output is correct
4 Correct 130 ms 17396 KB Output is correct
5 Correct 133 ms 17396 KB Output is correct
6 Correct 132 ms 17436 KB Output is correct
7 Correct 135 ms 17436 KB Output is correct
8 Correct 126 ms 17672 KB Output is correct
9 Correct 100 ms 17672 KB Output is correct
10 Correct 100 ms 17672 KB Output is correct
11 Correct 129 ms 17672 KB Output is correct
12 Correct 103 ms 17672 KB Output is correct
13 Correct 107 ms 17672 KB Output is correct
14 Correct 125 ms 17672 KB Output is correct
15 Correct 118 ms 17672 KB Output is correct
16 Correct 149 ms 17672 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 18672 KB Output is correct
2 Correct 368 ms 22116 KB Output is correct
3 Correct 487 ms 23656 KB Output is correct
4 Correct 710 ms 31548 KB Output is correct
5 Correct 211 ms 31548 KB Output is correct
6 Correct 726 ms 31548 KB Output is correct
7 Correct 715 ms 31548 KB Output is correct
8 Correct 724 ms 31548 KB Output is correct
9 Correct 697 ms 31548 KB Output is correct
10 Correct 690 ms 31548 KB Output is correct
11 Correct 642 ms 31800 KB Output is correct
12 Correct 649 ms 31800 KB Output is correct
13 Correct 684 ms 31800 KB Output is correct
14 Correct 553 ms 31800 KB Output is correct
15 Correct 516 ms 31800 KB Output is correct
16 Correct 515 ms 31800 KB Output is correct
17 Correct 508 ms 31800 KB Output is correct
18 Correct 496 ms 31800 KB Output is correct
19 Correct 602 ms 31800 KB Output is correct
20 Correct 567 ms 31800 KB Output is correct