Submission #1112224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112224		PagodePaiva	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	4 / 100	3058 ms	19932 KiB

fortune_telling2

#include<bits/stdc++.h>
#define int long long
#define fr first
#define sc second

using namespace std;

const int N = 200010;
const int B = 200;
int v[N][2];
int blocks[N];

struct Segtree{
    pair <int, int> tree[4*N]; int lazy[4*N];
    pair <int, int> join(pair <int, int> a, pair <int, int> b){
        return {max(a.fr, b.fr), max(a.sc, b.sc)};
    }
    void unlazy(int node, int l, int r){
        if(lazy[node]%2) swap(tree[node].fr, tree[node].sc);
        if(l != r){
            lazy[2*node] += lazy[node];
            lazy[2*node+1] += lazy[node];
        }
        lazy[node] = 0;
    }
    void build(int node, int l, int r){
        lazy[node] = 0;
        if(l == r){
            tree[node] = {v[l][0], v[l][1]};
            return;
        }
        int mid = (l+r)/2;
        build(2*node, l, mid);
        build(2*node+1, mid+1, r);
        tree[node] = join(tree[2*node], tree[2*node+1]);
    }
    void update(int node, int l, int r, int tl, int tr, int val){
        unlazy(node, tl, tr);
        if(l > tr or tl > r) return;
        if(l <= tl and tr <= r){
            if(tree[node].first <= val) {
                lazy[node]++;
                unlazy(node, tl, tr);
                return;
            }
            else{
                int mid = (tl+tr)/2;
                if(tl == tr) return;
                update(2*node, l, r, tl, mid, val);
                update(2*node+1, l, r, mid+1, tr, val);
                tree[node] = join(tree[2*node], tree[2*node+1]);
            }
            return;
        }
        int mid = (tl+tr)/2;
        update(2*node, l, r, tl, mid, val);
        update(2*node+1, l, r, mid+1, tr, val);
        tree[node] = join(tree[2*node], tree[2*node+1]);
        return;
    }
    pair <int, int> query(int node, int l, int r, int tl, int tr){
        unlazy(node, tl, tr);
        if(l > tr or tl > r) return {0, 0};
        if(l <= tl and tr <= r) return tree[node];
        int mid = (tl+tr)/2;
        return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
    }
} seg;

bool comp2(array <int, 3> a, array <int, 3> b){
    if(blocks[a[2]] > blocks[b[2]]) return false;
    if(blocks[a[2]] < blocks[b[2]]) return true;
    if(max(a[0], a[1]) < max(b[0], b[1])) return true;
    return false;
}

bool comp(array <int, 3> a, array <int, 3> b){
    if(min(a[0], a[1]) < min(b[0], b[1])) return true;
    return false;
}

int32_t main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector <array <int, 3>> vv;
    for(int i = 1;i <= n;i++){
        int a, b;
        cin >> a >> b;
        vv.push_back({a, b, i});
    }
    sort(vv.begin(), vv.end(), comp);
    for(int i = 1;i <= n;i++){
        blocks[vv[i-1][2]] = i/B;
    }
    sort(vv.begin(), vv.end(), comp2);
    for(int i = 0;i < n;i++){
        v[i+1][0] = vv[i][0];
        v[i+1][1] = vv[i][1];
        //cout << v[i+1][0] << ' ' << v[i+1][1] << '\n';
    }
    seg.build(1,1, n);
    for(int i = 0;i < k;i++){
        int q;
        cin >> q;
        seg.update(1, 1, n, 1, n, q);
    }
    int res = 0;
    for(int i = 1;i <= n;i++){
        res += seg.query(1, i, i, 1, n).first;   
    }
    cout << res << '\n';
}

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