Submission #1273118

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273118		trinm01	Examination (JOI19_examination)	C++20	100 / 100	227 ms	25036 KiB

examination

// #pragma GCC optimize("O3")
// #pragma GCC optimization("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;

#define int long long 
#define ll long long
#define FOR(i, l, r) for (int i = (l); i <= (r); i++)
#define FOD(i, r, l) for (int i = (r); i >= (l); i--)
#define fi first
#define se second
#define pii pair<int, int>

const ll mod = 1e9 + 9;
const int MAXN = 1e5 + 5;
const ll oo = 1e9 + 7;  
const int base = 10;

int n, q;
struct node{
	int x, y, z, id;
};
vector<node> vec;
vector<int> nen;
int m;
int res[MAXN];

bool cmp(node a, node b){
	if(a.x==b.x){
		return a.id<b.id;
	}
	return a.x>b.x;
}

struct fenwick{
	int bit[2*MAXN];
	void update(int i, int val){
		if(i==0) return;
		while(i<=m){
			bit[i]+=val;
			i+=(i&(-i));
		}
	}
	int get(int i){
		int sum=0;
		while(i>0){
			sum+=bit[i];
			i-=(i&(-i));
		}
		return sum;
	}
	int sum(int l, int r){
		return get(r)-get(l-1);
	}
}cc;

void dnc(int l, int r){
	if(l>=r){
		return;
	}
	int mid=(l+r+1)/2;
	
	dnc(l, mid-1);
	dnc(mid, r);
	
	int lft=l, rgh=mid;
	vector<node> tmp;
	vector<int> hist;
	while(lft<=mid-1 && rgh<=r){
		if(vec[lft].y>=vec[rgh].y){
			
			if(vec[lft].id==0){
				cc.update(vec[lft].z, 1);
				hist.push_back(vec[lft].z);
			}
			
			tmp.push_back(vec[lft]);
			lft++;
		}	
		else{
			
			if(vec[rgh].id>0){
				res[vec[rgh].id]+=cc.sum(vec[rgh].z, m);
			}
			
			tmp.push_back(vec[rgh]);
			rgh++;
		}
	}
	while(lft<=mid-1){
		
		if(vec[lft].id==0){
			cc.update(vec[lft].z, 1);
			hist.push_back(vec[lft].z);
		}
		
		tmp.push_back(vec[lft]);
		lft++;
	}
	while(rgh<=r){
		
		if(vec[rgh].id>0){
			res[vec[rgh].id]+=cc.sum(vec[rgh].z, m);
		}
		
		tmp.push_back(vec[rgh]);
		rgh++;
	}
	
	FOR(i, l, r){
		vec[i]=tmp[i-l];
	}
	
	while(!hist.empty()){
		cc.update(hist.back(), -1);
		hist.pop_back();
	}
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    
	// freopen("test.txt", "r", stdin);
	// freopen("o2.out", "w", stdout);
	
	if(fopen(".inp", "r")){
	  freopen(".inp", "r", stdin);
	  freopen(".out", "w", stdout);
	}

	cin >> n >> q;
	FOR(i, 1, n){
		int x, y;
		cin >> x >> y;
		int z=x+y;
		vec.push_back({x, y, z, 0});
	}
	FOR(i, 1, q){
		int x, y, z;
		cin >> x >> y >> z;
		vec.push_back({x, y, z, i});
	}
    
	nen.clear();
	FOR(i, 0, (int)vec.size()-1){
		nen.push_back(vec[i].z);
	}
	sort(nen.begin(), nen.end());
	nen.erase(unique(nen.begin(), nen.end()), nen.end());
	m=max(m, (int)nen.size()+1);
    FOR(i, 0, (int)vec.size()-1){
    	vec[i].z=lower_bound(nen.begin(), nen.end(), vec[i].z)-nen.begin()+1;
    }
    
    sort(vec.begin(), vec.end(), cmp);
    
    dnc(0, (int)vec.size()-1);
    FOR(i, 1, q){
    	cout << res[i] << '\n';
    }
    
    return 0;
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:131:18: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |           freopen(".inp", "r", stdin);
      |           ~~~~~~~^~~~~~~~~~~~~~~~~~~~
examination.cpp:132:18: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |           freopen(".out", "w", stdout);
      |           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57