답안 #47729

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
47729	2018-05-06T21:24:25 Z	_EmanuelNrx_	운세 보기 2 (JOI14_fortune_telling2)	C++14	100 / 100	725 ms	31980 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	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

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

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