Submission #719875

#	Time	Username	Problem	Language	Result	Execution time	Memory
719875		Hacv16	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	814 ms	130860 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAX = 2e6 + 15;
const int INF = 0x3f3f3f3f;

class SparseSegmentTree
{
    public:
        void createNode(){
            e.push_back( 0 );
            d.push_back( 0 );
 
            mx.push_back( 0 );
            sum.push_back( 0 );
        }
 
        int getLeft(int node){
            if(e[node] == 0){
                e[node] = ++curNode;
                createNode();
            }
 
            return e[node];
        }
 
        int getRight(int node){
            if(d[node] == 0){
                d[node] = ++curNode;
                createNode();
            }
 
            return d[node];
        }
 
        void update(int node, int l, int r, int i, int v){
            if(l == r){
                mx[ node ] = v;
                sum[ node ]++;
                return;
            }
 
            int m = (l + r)/2;
 
            if(i <= m) update(getLeft(node) , l , m , i , v);
            else update(getRight(node) , m + 1 , r , i , v);
 
            sum[ node ] = sum[ e[node] ] + sum[ d[node] ];
            mx[ node ] = max(mx[ e[node] ] , mx[ d[node] ]);
        }
 
        int queryMax(int node, int l, int r, int i, int j){
            if(i > j) return 0;
            if(node == 0 || j < l || r < i) return 0;
            if(i <= l && r <= j) return mx[ node ];
 
            int m = (l + r)/2;
 
            int maxLeft = queryMax(e[node] , l , m , i , j);
            int maxRight = queryMax(d[node] , m + 1 , r , i , j);
 
            return max(maxLeft , maxRight);
        }
 
        int querySum(int node, int l, int r, int i, int j){
            if(node == 0 || j < l || r < i) return 0;
            if(i <= l && r <= j) return sum[ node ];
 
            int m = (l + r) >> 1;
 
            int sumLeft = querySum(e[node] , l , m , i , j);
            int sumRight = querySum(d[node] , m + 1 , r , i , j);
 
            return sumLeft + sumRight;
        }
 
        SparseSegmentTree() : curNode( 1 ) { createNode(); createNode(); }
 
    protected:
        int curNode;
        vector<int> e, d;
        vector<int> mx, sum;
};

struct Event{
	ll x, type, id;

	Event(ll a = INF, ll b = 0, ll c = 0) : x(a), type(b), id(c) { }

	bool operator < (Event other){
		if(x != other.x) return x > other.x;
		return type < other.type;
	}
};

ll n, q, x[MAX], y[MAX], T[MAX];
bool changeOrder[MAX];
vector<Event> sweep;

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> q;

	for(int i = 1; i <= n; i++){
		cin >> x[i] >> y[i];

		if(x[i] < y[i]){ 
			swap(x[i], y[i]); 
			changeOrder[i] = true;
		}
	}

	SparseSegmentTree aux;

	for(int i = 1; i <= q; i++){
		cin >> T[i];

		aux.update(1, 0, INF, T[i], i);
		sweep.emplace_back(i, 1, i);
	}

	for(int i = 1; i <= n; i++){
		ll bonga = aux.queryMax(1, 0, INF, y[i], x[i] - 1);
		sweep.emplace_back(bonga, 2, i);
	}

	sort(sweep.begin(), sweep.end());

	SparseSegmentTree seg;
	ll ans = 0;

	for(Event cur : sweep){
		if(cur.type == 2){
			ll changes = seg.querySum(1, 0, INF, x[cur.id], INF);

			if(cur.x == 0){
				if((changes + changeOrder[cur.id]) % 2 == 0) ans += x[cur.id];
				else ans += y[cur.id];

			}else{
				if(changes % 2 == 0) ans += x[cur.id];
				else ans += y[cur.id];
			}

		}else seg.update(1, 0, INF, T[cur.id], 0);
	}

	cout << ans << '\n';

	exit(0);
}

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