oj.uz

Submission #656746

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

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

const int N = 1e6,K = 23;

int a[N + 1],b[N + 1],sign[N + 1];

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

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

void buildST(int id,int l,int r) {
    if(l == r) {
        seg[id] = {{query[l],1}};
        return;
    }
    int mid = (l + r)/2;
    buildST(id*2,l,mid);
    buildST(id*2 + 1,mid + 1,r);

    seg[id] = seg[id*2];
    for(auto u : seg[id*2 + 1]) {
        seg[id].push_back(u);
    }
    sort(seg[id].begin(),seg[id].end());
    
    for(int i = 0;i < seg[id].size();i++) {
        seg[id][i].second = i + 1;
    }
}

int queryST(int id,int l,int r,int u,int v,int val) {
    if(v < l || u > r) return 0;
    
    if(u <= l && v >= r) {
        auto it = lower_bound(seg[id].begin(),seg[id].end(),make_pair(val,(int)-1));
        if(it == seg[id].end()) return 0;

        return (seg[id].size()) - (*it).second + 1;
    }
    int mid = (l + r)/2;
    return queryST(id*2,l,mid,u,v,val) + queryST(id*2 + 1,mid + 1,r,u,v,val);
}

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

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);
    }

    int res = 0;
    buildSP();
    buildST(1,0,query.size() - 1);

    // for(int i = 1;i <= n;i++) {
    //     cout<<a[i]<<" "<<b[i]<<endl;
    // }
    // for(auto u : query) {
    //     cout<<u<<endl;
    // }
    for(int i = 1;i <= n;i++) {
        if(a[i] == b[i]) {
            res += val[a[i]];
            continue;
        }
        // cout<<a[i]<<" "<<b[i]<<endl;
        int nw = querySP(a[i],b[i] - 1);

        int w = sign[i];
        if(nw != -1) w = 1;

        int cnt = queryST(1,0,query.size() - 1,nw + 1,query.size() - 1,b[i]);

        w ^= (cnt%2);

        if(w == 0) {
            res += val[a[i]];
            // cout<<val[a[i]]<<" "<<cnt<<" "<<nw<<endl;
        } else {
            res += val[b[i]];
            // cout<<val[b[i]]<<" "<<cnt<<" "<<nw<<endl;
        }
    }
    cout<<res<<endl;
    

    return 0;
}

Compilation message

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

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 102604 KB Output is correct
2 Correct 50 ms 102816 KB Output is correct
3 Correct 59 ms 103056 KB Output is correct
4 Correct 53 ms 103180 KB Output is correct
5 Correct 53 ms 103168 KB Output is correct
6 Correct 53 ms 103116 KB Output is correct
7 Correct 54 ms 103172 KB Output is correct
8 Correct 57 ms 103156 KB Output is correct
9 Correct 52 ms 103064 KB Output is correct
10 Correct 51 ms 102604 KB Output is correct
11 Correct 52 ms 102772 KB Output is correct
12 Correct 53 ms 102868 KB Output is correct
13 Correct 70 ms 102860 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 102604 KB Output is correct
2 Correct 50 ms 102816 KB Output is correct
3 Correct 59 ms 103056 KB Output is correct
4 Correct 53 ms 103180 KB Output is correct
5 Correct 53 ms 103168 KB Output is correct
6 Correct 53 ms 103116 KB Output is correct
7 Correct 54 ms 103172 KB Output is correct
8 Correct 57 ms 103156 KB Output is correct
9 Correct 52 ms 103064 KB Output is correct
10 Correct 51 ms 102604 KB Output is correct
11 Correct 52 ms 102772 KB Output is correct
12 Correct 53 ms 102868 KB Output is correct
13 Correct 70 ms 102860 KB Output is correct
14 Correct 89 ms 113212 KB Output is correct
15 Correct 124 ms 124408 KB Output is correct
16 Correct 148 ms 135884 KB Output is correct
17 Correct 202 ms 147352 KB Output is correct
18 Correct 209 ms 147356 KB Output is correct
19 Correct 202 ms 147396 KB Output is correct
20 Correct 203 ms 147540 KB Output is correct
21 Correct 209 ms 147364 KB Output is correct
22 Correct 159 ms 136776 KB Output is correct
23 Correct 145 ms 131416 KB Output is correct
24 Correct 136 ms 127412 KB Output is correct
25 Correct 164 ms 139780 KB Output is correct
26 Correct 162 ms 134820 KB Output is correct
27 Correct 173 ms 136840 KB Output is correct
28 Correct 194 ms 136748 KB Output is correct
29 Correct 198 ms 142020 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 102604 KB Output is correct
2 Correct 50 ms 102816 KB Output is correct
3 Correct 59 ms 103056 KB Output is correct
4 Correct 53 ms 103180 KB Output is correct
5 Correct 53 ms 103168 KB Output is correct
6 Correct 53 ms 103116 KB Output is correct
7 Correct 54 ms 103172 KB Output is correct
8 Correct 57 ms 103156 KB Output is correct
9 Correct 52 ms 103064 KB Output is correct
10 Correct 51 ms 102604 KB Output is correct
11 Correct 52 ms 102772 KB Output is correct
12 Correct 53 ms 102868 KB Output is correct
13 Correct 70 ms 102860 KB Output is correct
14 Correct 89 ms 113212 KB Output is correct
15 Correct 124 ms 124408 KB Output is correct
16 Correct 148 ms 135884 KB Output is correct
17 Correct 202 ms 147352 KB Output is correct
18 Correct 209 ms 147356 KB Output is correct
19 Correct 202 ms 147396 KB Output is correct
20 Correct 203 ms 147540 KB Output is correct
21 Correct 209 ms 147364 KB Output is correct
22 Correct 159 ms 136776 KB Output is correct
23 Correct 145 ms 131416 KB Output is correct
24 Correct 136 ms 127412 KB Output is correct
25 Correct 164 ms 139780 KB Output is correct
26 Correct 162 ms 134820 KB Output is correct
27 Correct 173 ms 136840 KB Output is correct
28 Correct 194 ms 136748 KB Output is correct
29 Correct 198 ms 142020 KB Output is correct
30 Correct 626 ms 230040 KB Output is correct
31 Correct 726 ms 252284 KB Output is correct
32 Runtime error 768 ms 262144 KB Execution killed with signal 9
33 Halted 0 ms 0 KB -