Submission #969059

#	Time	Username	Problem	Language	Result	Execution time	Memory
969059		Beerus13	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	345 ms	79388 KiB

fortune_telling2

#include<bits/stdc++.h>
using namespace std;
#define Mask(i) (1 << i)
#define ll long long
const int ar = 2e5 + 5;
const int N = 6e5 + 5;

struct query {
    int x, v, pos;
    bool operator < (query &other) {
        if(x != other.x) return x > other.x;
        return pos < other.pos;
    }
}; vector<query> queries;

int n, q;
int a[ar][2];
int pos[ar], t[ar];
vector<int> Numbers;
int st[N << 2], cnt[ar];
int Max[N][21]; 
int ok[N];

int getmax(int l, int r){
    int k = 31 - __builtin_clz(r - l + 1);
    return max(Max[l][k], Max[r - Mask(k) + 1][k]);
}

int ID(int x) {
    return lower_bound(Numbers.begin(), Numbers.end(), x) - Numbers.begin() + 1;
}

void update(int u, int val) {
    int id = 1, l = 1, r = Numbers.size();
    while(l < r) {
        int mid = l + r >> 1;
        if(u > mid) id = id << 1 | 1, l = mid + 1;
        else id = id << 1, r = mid;
    }
    st[id] += val;
    while(id > 1) id = id >> 1, st[id] = st[id << 1] + st[id << 1 | 1];
}

int get(int id, int l, int r, int u, int v) {
    if(u > r || v < l) return 0;
    if(u <= l && r <= v) return st[id];
    int mid = l + r >> 1;
    int tmp1 = get(id << 1, l, mid, u, v);
    int tmp2 = get(id << 1 | 1, mid + 1, r, u, v);
    return tmp1 + tmp2;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i][0] >> a[i][1];
        Numbers.push_back(a[i][0]);
        Numbers.push_back(a[i][1]);
    }
    for(int i = 1; i <= q; ++i) {
        cin >> t[i];
        Numbers.push_back(t[i]);
    }
    sort(Numbers.begin(), Numbers.end());
    Numbers.resize(unique(Numbers.begin(), Numbers.end()) - Numbers.begin());
    for(int i = 1; i <= q; ++i) {
        int vt = ID(t[i]);
        Max[vt][0] = i;
    }
    for(int j = 1; j < 21; j++) {
        for(int i = 1; i <= (int)Numbers.size() - Mask(j) + 1; i++) {
            Max[i][j] = max(Max[i][j - 1], Max[i + Mask(j - 1)][j - 1]);
        }
    }
    for(int i = 1; i <= n; ++i) {
        int L = ID(a[i][0]), R = ID(a[i][1]);
        if(L > R) swap(L, R);
        pos[i] = getmax(L, R - 1);
        if(pos[i]) if(a[i][0] < a[i][1]) cnt[i] = 1;
    }
    for(int i = 1; i <= n; ++i) {
        queries.push_back({max(a[i][0], a[i][1]), i, 1});
    }
    for(int i = 1; i <= q; ++i) {
        queries.push_back({t[i], i, 0});
    }
    sort(queries.begin(), queries.end());
    for(auto it : queries) {
        if(it.pos == 0) update(it.v, 1);
        else cnt[it.v] += get(1, 1, Numbers.size(), pos[it.v] + 1, Numbers.size());
    }
  	ll ans = 0;
    for(int i = 1; i <= n; ++i) {
        ans += a[i][cnt[i] & 1];
    }
    cout << ans << '\n';
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'void update(int, int)':
fortune_telling2.cpp:36:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |         int mid = l + r >> 1;
      |                   ~~^~~
fortune_telling2.cpp: In function 'int get(int, int, int, int, int)':
fortune_telling2.cpp:47:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |     int mid = l + r >> 1;
      |               ~~^~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:74:59: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   74 |             Max[i][j] = max(Max[i][j - 1], Max[i + Mask(j - 1)][j - 1]);
      |                                                         ~~^~~
fortune_telling2.cpp:3:23: note: in definition of macro 'Mask'
    3 | #define Mask(i) (1 << i)
      |                       ^

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65