oj.uz

Submission #656749

# Submission time Handle Problem Language Result Execution time Memory
656749 2022-11-08T07:16:49 Z uylulu Fortune Telling 2 (JOI14_fortune_telling2) C++14
35 / 100
 1057 ms 259120 KB 
#include <bits/stdc++.h>
using namespace std;

#define ld long double
#define ll long long
#define endl "\n"

const int N = 5e5,K = 20;

int a[N + 1],b[N + 1],sign[N + 1];
int val[N + 1],lst[N + 1],cnt = 0;
int sparse[N + 1][K + 1],lg[N + 1];

map<int,int> mp;
vector<int> query;

vector<pair<int,int>> seg[4*N + 1];

int bit[N + 1];

void add(int pos) {
    while(pos > 0) {
        bit[pos]++;
        pos -= pos&(-pos);
    }
}

int queryBIT(int pos) {
    int res = 0;
    for(int i = pos;i <= cnt;i += i&(-i)) {
        res += bit[i];
    }
    return res;
}


void buildSP() {
    for(int i = 2;i <= N;i++) {
        lg[i] = lg[i/2] + 1;
    }
    for(int i = 0;i <= cnt;i++) {
        sparse[i][0] = lst[i];
    }
    for(int j = 1;j <= K;j++) {
        for(int i = 0;i + (1<<j) <= cnt;i++) {
            sparse[i][j] = max(sparse[i][j - 1],sparse[i + (1<<(j - 1))][j - 1]);
        }
    }
}

int querySP(int l,int r) {
    int len = lg[r - l + 1];
    return max(sparse[l][len],sparse[r - (1<<len) + 1][len]);
}

signed main() {
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    int n,k;
    cin>>n>>k;
    for(int i = 1;i <= n;i++) {
        cin>>a[i]>>b[i];
        sign[i] = 0;
        if(a[i] > b[i]) {
            sign[i] = 1;
            swap(a[i],b[i]);
        }
        mp[a[i]] = -1;
        mp[b[i]] = -1;
    }
    for(int i = 0;i < k;i++) {
        int x;
        cin>>x;
        mp[x] = -1;
        query.push_back(x);
    }

    for(auto u : mp) {
        mp[u.first] = cnt;
        val[cnt] = u.first;
        cnt++;
    }
    for(int i = 1;i <= n;i++) {
        a[i] = mp[a[i]];
        b[i] = mp[b[i]];
    }
    for(int i = 0;i < query.size();i++) {
        query[i] = mp[query[i]];
    }
    for(int i = 0;i <= cnt;i++) {
        lst[i] = -1;
    }
    for(int i = 0;i < query.size();i++) {
        lst[query[i]] = max(lst[query[i]],i);
    }

    ll res = 0;
    buildSP();

    vector<pair<int,int>> asd;
    
    for(int i = 1;i <= n;i++) {
        if(a[i] == b[i]) {
            res += val[a[i]];
            continue;
        }
        int nw = querySP(a[i],b[i] - 1);
        asd.push_back({nw + 1,i});
    }
    
    sort(asd.begin(),asd.end());
    reverse(asd.begin(),asd.end());

    int ptr = query.size() - 1;

    for(auto u : asd) {
        while(ptr >= u.first) {
            add(query[ptr]);
            ptr--;
        }
        int w = sign[u.second];
        if(u.first > 0) {
            w = 1;
        }

        int cnt = queryBIT(b[u.second]);
        w ^= (cnt%2);

        if(w == 0) {
            res += val[a[u.second]];
        } else {
            res += val[b[u.second]];
        }
    }
    cout<<res<<endl;

    return 0;
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:89:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int i = 0;i < query.size();i++) {
      |                   ~~^~~~~~~~~~~~~~
fortune_telling2.cpp:95:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int i = 0;i < query.size();i++) {
      |                   ~~^~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 49364 KB Output is correct
2 Correct 24 ms 49476 KB Output is correct
3 Correct 25 ms 49752 KB Output is correct
4 Correct 26 ms 49692 KB Output is correct
5 Correct 26 ms 49668 KB Output is correct
6 Correct 26 ms 49748 KB Output is correct
7 Correct 30 ms 49640 KB Output is correct
8 Correct 24 ms 49704 KB Output is correct
9 Correct 24 ms 49696 KB Output is correct
10 Correct 24 ms 49364 KB Output is correct
11 Correct 24 ms 49568 KB Output is correct
12 Correct 25 ms 49572 KB Output is correct
13 Correct 26 ms 49716 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 49364 KB Output is correct
2 Correct 24 ms 49476 KB Output is correct
3 Correct 25 ms 49752 KB Output is correct
4 Correct 26 ms 49692 KB Output is correct
5 Correct 26 ms 49668 KB Output is correct
6 Correct 26 ms 49748 KB Output is correct
7 Correct 30 ms 49640 KB Output is correct
8 Correct 24 ms 49704 KB Output is correct
9 Correct 24 ms 49696 KB Output is correct
10 Correct 24 ms 49364 KB Output is correct
11 Correct 24 ms 49568 KB Output is correct
12 Correct 25 ms 49572 KB Output is correct
13 Correct 26 ms 49716 KB Output is correct
14 Correct 45 ms 53836 KB Output is correct
15 Correct 67 ms 58268 KB Output is correct
16 Correct 97 ms 62736 KB Output is correct
17 Correct 149 ms 67200 KB Output is correct
18 Correct 124 ms 67268 KB Output is correct
19 Correct 124 ms 66960 KB Output is correct
20 Correct 126 ms 67256 KB Output is correct
21 Correct 127 ms 66920 KB Output is correct
22 Correct 95 ms 61500 KB Output is correct
23 Correct 74 ms 58700 KB Output is correct
24 Correct 72 ms 56756 KB Output is correct
25 Correct 97 ms 63176 KB Output is correct
26 Correct 95 ms 60660 KB Output is correct
27 Correct 105 ms 61528 KB Output is correct
28 Correct 92 ms 61516 KB Output is correct
29 Correct 123 ms 64468 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 49364 KB Output is correct
2 Correct 24 ms 49476 KB Output is correct
3 Correct 25 ms 49752 KB Output is correct
4 Correct 26 ms 49692 KB Output is correct
5 Correct 26 ms 49668 KB Output is correct
6 Correct 26 ms 49748 KB Output is correct
7 Correct 30 ms 49640 KB Output is correct
8 Correct 24 ms 49704 KB Output is correct
9 Correct 24 ms 49696 KB Output is correct
10 Correct 24 ms 49364 KB Output is correct
11 Correct 24 ms 49568 KB Output is correct
12 Correct 25 ms 49572 KB Output is correct
13 Correct 26 ms 49716 KB Output is correct
14 Correct 45 ms 53836 KB Output is correct
15 Correct 67 ms 58268 KB Output is correct
16 Correct 97 ms 62736 KB Output is correct
17 Correct 149 ms 67200 KB Output is correct
18 Correct 124 ms 67268 KB Output is correct
19 Correct 124 ms 66960 KB Output is correct
20 Correct 126 ms 67256 KB Output is correct
21 Correct 127 ms 66920 KB Output is correct
22 Correct 95 ms 61500 KB Output is correct
23 Correct 74 ms 58700 KB Output is correct
24 Correct 72 ms 56756 KB Output is correct
25 Correct 97 ms 63176 KB Output is correct
26 Correct 95 ms 60660 KB Output is correct
27 Correct 105 ms 61528 KB Output is correct
28 Correct 92 ms 61516 KB Output is correct
29 Correct 123 ms 64468 KB Output is correct
30 Correct 347 ms 81312 KB Output is correct
31 Correct 450 ms 93920 KB Output is correct
32 Correct 666 ms 108424 KB Output is correct
33 Runtime error 1057 ms 259120 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -