oj.uz

답안 #1099106

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1099106 2024-10-10T14:46:15 Z Nurislam Examination (JOI19_examination) C++17
0 / 100
 135 ms 17688 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp> 
//#include <ext/pb_ds/tree_policy.hpp>  
using namespace std;
//using namespace __gnu_pbds;z
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
//#define ordst tree<pair<int,int>,  null_type,  less<pair<int,int>>,  rb_tree_tag ,  tree_order_statistics_node_update >
//#define double long double 
template <class F, class _S>
bool chmin(F &u, const _S &v){
	bool flag = false;
	if ( u > v ){
		u = v; flag |= true;
	}
	return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
	bool flag = false;
	if ( u < v ){
		u = v; flag |= true;
	}
	return flag;
}

const int N = (1<<18) +1, inf = 1e18+200;
//int mod = 998244353;
//int mod = 1000000007;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#define rnd(l, r) uniform_int_distribution <int> (l, r)(rng)

struct segtree{
	vector<int> t;
	
	segtree(){
		t.resize(N*4);
	};
	
	void upd(int ps, int i = 1, int l = 1, int r = N){
		if(l == r){
			t[i] = 1;
			return;
		}
		int m = (l+r)>>1;
		if(ps <= m)upd(ps, i*2, l, m);
		else upd(ps, i*2+1, m+1, r);
		t[i] = t[i*2] + t[i*2+1];
	};
	
	int get(int tl, int tr, int i = 1, int l = 1, int r = N){
		if(l > tr || r < tl)return 0;
		if(tl <= l && r <= tr)return t[i];
		int m = (l+r)>>1;
		return get(tl, tr, i*2, l, m)+get(tl, tr, i*2+1, m+1, r);
	};
};
void solve(){
	int n, q;
	cin >> n >> q;
	vector<array<int, 2>> v(n);
	for(auto&[i, j]:v)cin >> i >> j;
	sort(rall(v));
	vector<array<int,3>> que;
	for(int i = 0; i < q; i++){
		int a, b, c;
		cin >> a >> b >> c;
		que.pb({a, b, i});
	}
	sort(rall(que));
	
	auto compr = [&]()->void{
		vector<int> vv;
		for(auto [i, j]:v)vv.pb(i),vv.pb(j);
		for(auto [i, j, k]:que)vv.pb(i), vv.pb(j);
		sort(all(vv));
		vv.erase(unique(all(vv)), vv.end());
		//for(auto i:vv)cout << i << ' ';
		//cout << '\n';
		for(auto &[i, j]:v){
			i = lower_bound(all(vv), i)-vv.begin();
			j = lower_bound(all(vv), j)-vv.begin();
		}
		for(auto &[i, j, k]:que){
			i = lower_bound(all(vv), i)-vv.begin();
			j = lower_bound(all(vv), j)-vv.begin();
		}
		
	};compr();
	
	
	//for(auto [i, j]:v)cout << i << ' ' << j << '\n';
	//for(auto [i, j, k]:que)cout << i << ' ' << j << ' ' << k << '\n';
	
	vector<int> ans(q);
	int it = 0;
	segtree t;
	for(int i = 0; i < q; i++){
		int a = que[i][0], b = que[i][1], id = que[i][2];
		//cout << a << ' ' << b << ' ' << id << '\n';
		while(it < n && v[it][0] >= a){
			t.upd(v[it][1]);
			it++;
		}
		ans[id] = t.get(b, N);
	}
	
	for(int i:ans)cout << i << '\n';
	
}

 
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int tt = 1;
	//cin >> tt;
	while(tt--){
		solve();
	}
}

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 8540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 135 ms 17688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 135 ms 17688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 8540 KB Output isn't correct
2 Halted 0 ms 0 KB -