Submission #769928

#	Time	Username	Problem	Language	Result	Execution time	Memory
769928		raysh07	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	281 ms	22976 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

struct point {
    int a, b, i, pos;
};

int n, q;
const int N = 2e5 + 69;
int t[N];
int s1[4 * N], f[N];
vector <pair<int, int>> t1;

void Build(int l, int r, int pos){
    if (l == r){
        s1[pos] = t1[l - 1].second;
        return;
    }
    
    int mid = (l + r)/2;
    Build(l, mid, pos*2);
    Build(mid + 1, r, pos*2 + 1);
    
    s1[pos] = max(s1[pos * 2], s1[pos * 2 + 1]);
}

int query1(int l, int r, int pos, int ql, int qr){
    if (l >= ql && r <= qr) return s1[pos];
    else if (l > qr || r < ql) return -INF;
    
    int mid = (l + r)/2;
    return max(query1(l, mid, pos*2, ql, qr), query1(mid + 1, r, pos*2 + 1, ql, qr));
}

void upd(int x){
    for (int i = x; i <= q; i += i & (-i)){
        f[i]++;
    }
}

int query(int x){
    int res = 0;
    for (int i = x; i; i -= i & (-i)){
        res += f[i];
    }
    
    return res;
}

bool comp(point a, point b){
    return max(a.a, a.b) > max(b.a, b.b);
}

void Solve() 
{
    cin >> n >> q;
    
    vector <point> a(n);
    
    for (int i = 0; i < n; i++){
        cin >> a[i].a >> a[i].b;
        a[i].i = i;
    }
    
    for (int i = 1; i <= q; i++){
        cin >> t[i];
        t1.push_back({t[i], i});
    }
    
    sort(t1.begin(), t1.end());
    Build(1, q, 1);
    
    
    for (int i = 0; i < n; i++){
        if (lower_bound(t1.begin(), t1.end(), make_pair(a[i].a, 0LL)) == lower_bound(t1.begin(), t1.end(), make_pair(a[i].b, 0LL))){
          //  cout << i << "\n";
            a[i].pos = 0;
            continue;
        }
        
        if (a[i].a < a[i].b) swap(a[i].a, a[i].b);
        int id1 = lower_bound(t1.begin(), t1.end(), make_pair(a[i].b, 0LL)) - t1.begin();
        int id2 = lower_bound(t1.begin(), t1.end(), make_pair(a[i].a, 0LL)) - t1.begin();
        id1++;
        
      //  cout << id1 << " " << id2 << "\n";
        
        a[i].pos = query1(1, q, 1, id1, id2);
     //   cout << a[i].pos << "\n";
    }
    // for (int i = 0; i < n; i++){
    //     cout << a[i].a << " " << a[i].b << " " << a[i].pos << "\n";
    // }
    
    sort(a.begin(), a.end(), comp);
    reverse(t1.begin(), t1.end());
    
    int ptr = 0;
    int ans = 0;
    for (int i = 0; i < n; i++){
        while (ptr != q && t1[ptr].first >= max(a[i].a, a[i].b)){
          //  cout << "ADDED " << t1[ptr].second << "\n";
            upd(t1[ptr].second);
            ptr++;
        }
        
     //   cout << a[i].a << " " << a[i].b << " ";
        
        int flip = query(q) - query(a[i].pos);
     //   cout << flip << "\n";
        if (flip & 1) swap(a[i].a, a[i].b);
        ans += a[i].a;
     //   cout << "HOLY " << a[i].a << "\n";
    }
    
    cout << ans << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
 //   cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

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