Submission #720012

#	Time	Username	Problem	Language	Result	Execution time	Memory
720012		hello_there_123	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	0 / 100	177 ms	262144 KiB

fortune_telling2

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int ft[10000005];
int n;
int ls(int x){
	return (x&(-x));
}
int qry2(int p){
	p++;
	int sum = 0;
	for(;p;p-=ls(p)) sum+=ft[p];
	return sum;
}
void upd(int p ,int v){
	p++;
	for(;p<=n+1;p+=ls(p)) ft[p] += v;
}
struct node{
    int s,e,m;
    int val = 0;
    int lazy = 0;
    node *l , *r ;
    node(int S,int E){
        s = S, e = E, m = (s+e)/2;
        if(s!=e){
            l = new node(s,m);
            r = new node(m+1,e);
        }
    }
 
 
void propogate(){
    if(lazy == 0) return;
    val = lazy;
    if(s!=e){
        l->lazy = lazy;
        r->lazy = lazy;
        
    }
    lazy = 0;
}
 
void update(int i,int j, int k){
    if(i==s && j==e) lazy = k;
    else{
        if(j<=m) l->update(i,j,k);
        else if(i>m) r->update(i,j,k);
        else l->update(i,m,k), r->update(m+1,j,k);
        l->propogate(), r->propogate();
        val = max(l->val,r->val);
    }
}
int query(int a,int b){
    if(a>e || b<s) return -1e9;
    propogate();
    if(a==s && b==e ) return val;
    else{
        if(b<=m) return l-> query(a,b);
        else if(a>m) return r->query(a,b);
        else return max(l->query(a,m),r->query(m+1,b));
    }
}
}*root;
main(){
	n = 1e7 ;
	root = new node(0,n);
	int N,Q;
	cin>>N>>Q;
	map<int,int> mp,mp2;
	int left[N+3],right[N+3],qry[Q+3];
	bool flip[N+3];
	set<int>s;
	memset(flip,0,sizeof(flip));
	for(int i=0;i<N;i++){
		cin>>left[i]>>right[i];
		s.insert(left[i]);
		s.insert(right[i]);
		if(left[i]>right[i]){
			flip[i] = 1;
			swap(left[i],right[i]);
		}
	}
	int cnt = 1;
	for(int x:s){
		mp[x] = cnt;
		mp2[cnt] = x;
		cnt++;
	}
	for(int i=0;i<N;i++){
		left[i] = mp[left[i]];
		right[i] = mp[right[i]];
	}
	for(int i=0;i<Q;i++){
		cin>>qry[i];
		auto it = mp.upper_bound(qry[i]);
		if(it == mp.begin()) qry[i] = 0;
		else{
			it--;
			qry[i] = it->second;
		}
		root->update(qry[i],qry[i],i+1);
	}
	priority_queue<pair<int,int> >pq;
	for(int i=0;i<N;i++){
		int x = root->query(left[i],right[i]-1);
		pq.push(make_pair(x,i));
	}
	int ans = 0;
	for(int i=Q-1;i>=0;i--){
		while(!pq.empty() && pq.top().first-1 == i){
			int y = qry2(n) - qry2(right[pq.top().second]-1);
			if((y%2==0 && flip[pq.top().second] == 0) || (y%2==1 && flip[pq.top().second] == 1)){
				ans+=mp2[left[pq.top().second]];
			}
			else ans+=mp2[right[pq.top().second]];
			pq.pop();
		}
		upd(qry[i],1);
	}
	while(!pq.empty()){
		//cout<<pq.top().second;
		int y = qry2(n) - qry2(right[pq.top().second]-1);
		if((y%2==0 && flip[pq.top().second] == 0) || (y%2==1 && flip[pq.top().second] == 1)){
			ans+=mp2[left[pq.top().second]];
		}
		else ans+=mp2[right[pq.top().second]];
		pq.pop();
	}
	
	cout<<ans;
}

Compilation message (stderr)

fortune_telling2.cpp:65:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   65 | main(){
      | ^~~~

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