oj.uz

답안 #1048177

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1048177 2024-08-08T04:10:54 Z Minbaev Examination (JOI19_examination) C++17
22 / 100
 84 ms 9448 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
 
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")
 
using namespace std;
using namespace __gnu_pbds;
 
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define f first
#define s second
#define int long long
#define ll long long
#define pii pair<int,int>
#define ar array
 
template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}
 
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
 tree_order_statistics_node_update> ordered_set;
 
const int inf = 1e17 + 7;
const int mod = 1e9 + 7;
const int N = 3e5 + 5;
const int md = 998244353;
 
int binpow(int a, int b){
	if(b == 0)return 1;
	if(b % 2 == 0){
		int c = binpow(a,b/2);
		return (c*c)%mod;
	}
	return (binpow(a,b-1)*a)%mod;
}
 
int divi(int a, int b){
	return (a*(binpow(b,mod-2)))%mod;
}
 
int n,m,k;
int t[N*4];

void update(int tl, int tr, int v, int pos){
	if(tl == tr){
		t[v] = 1;
		//~ cout << tr << " " << v << "\n";
		//~ cout << "\n";
		return;
	}
	int tm = (tl+tr)/2;
	
	//~ cout << tl << " " << tr << " " << tm << " " << pos << "\n";
	if(pos <= tm)
		update(tl,tm,v*2,pos);
	else
		update(tm+1,tr,v*2+1,pos);
		
	t[v] = t[v*2] + t[v*2+1];
}

int get(int tl, int tr, int v, int l, int r){
	if(r < tl || tr < l)return 0;
	
	if(l <= tl && tr <= r){
		return t[v];
	}
	int tm = (tl+tr)/2;
	
	return get(tl,tm,v*2,l,r) + get(tm+1,tr,v*2+1,l,r);
}


void solve(){
	
	cin >> n >> m;
	
	vector<pii>v(n);
	for(auto &to:v)cin >> to.f >> to.s;
	
	if(n*m <= 9000000){
		while(m--){
			int a,b,c;
			cin >> a >> b >> c;
			
			int ans = 0;
			for(int i = 0;i<n;i++){
				if(v[i].f >= a && v[i].s >= b && v[i].f + v[i].s >= c)ans += 1;
			}
			
			cout << ans << "\n";
		}
		return;
	}
	
	sort(all(v));
	
	vector<pii>a;
	for(int i = 0;i<n;i++){
		a.pb({v[i].s, i});
	}
	
	sort(all(a));
	
	vector<pair<pii,int>>q(m);
	for(int i = 0;i<m;i++){
		int p;
		cin >> q[i].f.s >> q[i].f.f >> p;
		q[i].s = i;
	}
	
	
	vector<int>ans1(m);
	sort(rall(q));
	
	int cur = n - 1;
	for(int i = 0;i<m;i++){
		
		while(cur >= 0 && a[cur].f >= q[i].f.f){
			//~ cout << cur << " " << a[cur].s << "\n";
			update(0,n-1,1,a[cur].s);
			cur -= 1;
		}
		
		//~ cout << "\n";
		
		int l = 0, r = n-1, ans = -1;
		while(l<=r){
			int mid = (l+r)/2;
			
			if(v[mid].f < q[i].f.s){
				l = mid + 1;
			}
			else {
				ans = mid;
				r = mid - 1;
			}
		}
		if(ans == -1)ans1[q[i].s] = 0;
		else ans1[q[i].s] = get(0, n-1, 1, ans, n-1);
		//~ cout << ans << " " << n-1 << "\n";
	}
	
	for(auto to:ans1)cout << to << "\n";
	
	
	
	
	

}
/*
5 4
35 100
70 70
45 15
80 40
20 95
20 50 0
10 10 0
60 60 0
0 100 0
*/
 signed main()
{
//	freopen("seq.in", "r", stdin);
//  freopen("seq.out", "w", stdout);
	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	int tt=1;//cin>>tt;
	while(tt--)solve();
 
}

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 460 KB Output is correct
7 Correct 6 ms 604 KB Output is correct
8 Correct 6 ms 656 KB Output is correct
9 Correct 6 ms 604 KB Output is correct
10 Correct 6 ms 624 KB Output is correct
11 Correct 6 ms 600 KB Output is correct
12 Correct 5 ms 552 KB Output is correct
13 Correct 6 ms 628 KB Output is correct
14 Correct 6 ms 644 KB Output is correct
15 Correct 7 ms 604 KB Output is correct
16 Correct 6 ms 716 KB Output is correct
17 Correct 6 ms 472 KB Output is correct
18 Correct 6 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 9420 KB Output is correct
2 Correct 73 ms 9160 KB Output is correct
3 Correct 72 ms 9448 KB Output is correct
4 Correct 57 ms 9448 KB Output is correct
5 Correct 55 ms 9140 KB Output is correct
6 Correct 44 ms 9416 KB Output is correct
7 Correct 66 ms 9164 KB Output is correct
8 Correct 84 ms 9448 KB Output is correct
9 Correct 75 ms 9416 KB Output is correct
10 Correct 57 ms 9320 KB Output is correct
11 Correct 51 ms 9044 KB Output is correct
12 Correct 52 ms 9164 KB Output is correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 9420 KB Output is correct
2 Correct 73 ms 9160 KB Output is correct
3 Correct 72 ms 9448 KB Output is correct
4 Correct 57 ms 9448 KB Output is correct
5 Correct 55 ms 9140 KB Output is correct
6 Correct 44 ms 9416 KB Output is correct
7 Correct 66 ms 9164 KB Output is correct
8 Correct 84 ms 9448 KB Output is correct
9 Correct 75 ms 9416 KB Output is correct
10 Correct 57 ms 9320 KB Output is correct
11 Correct 51 ms 9044 KB Output is correct
12 Correct 52 ms 9164 KB Output is correct
13 Incorrect 73 ms 9420 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 460 KB Output is correct
7 Correct 6 ms 604 KB Output is correct
8 Correct 6 ms 656 KB Output is correct
9 Correct 6 ms 604 KB Output is correct
10 Correct 6 ms 624 KB Output is correct
11 Correct 6 ms 600 KB Output is correct
12 Correct 5 ms 552 KB Output is correct
13 Correct 6 ms 628 KB Output is correct
14 Correct 6 ms 644 KB Output is correct
15 Correct 7 ms 604 KB Output is correct
16 Correct 6 ms 716 KB Output is correct
17 Correct 6 ms 472 KB Output is correct
18 Correct 6 ms 348 KB Output is correct
19 Correct 76 ms 9420 KB Output is correct
20 Correct 73 ms 9160 KB Output is correct
21 Correct 72 ms 9448 KB Output is correct
22 Correct 57 ms 9448 KB Output is correct
23 Correct 55 ms 9140 KB Output is correct
24 Correct 44 ms 9416 KB Output is correct
25 Correct 66 ms 9164 KB Output is correct
26 Correct 84 ms 9448 KB Output is correct
27 Correct 75 ms 9416 KB Output is correct
28 Correct 57 ms 9320 KB Output is correct
29 Correct 51 ms 9044 KB Output is correct
30 Correct 52 ms 9164 KB Output is correct
31 Incorrect 73 ms 9420 KB Output isn't correct
32 Halted 0 ms 0 KB -