답안 #47730 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
47730	2018-05-06T21:29:59 Z	EmanuelNrx	운세 보기 2 (JOI14_fortune_telling2)	C++14	100 / 100	726 ms	31800 KB

fortune_telling2

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #47730

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 31.0 / 31.0

Subtask #3 65.0 / 65.0

Subtask #1
4.0 / 4.0

Subtask #2
31.0 / 31.0

Subtask #3
65.0 / 65.0