oj.uz

Submission #1048175

# Submission time Handle Problem Language Result Execution time Memory
1048175 2024-08-08T04:05:18 Z Minbaev Examination (JOI19_examination) C++17
20 / 100
 119 ms 12484 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;
	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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 9412 KB Output is correct
2 Correct 110 ms 9156 KB Output is correct
3 Correct 111 ms 9412 KB Output is correct
4 Correct 86 ms 9408 KB Output is correct
5 Correct 81 ms 9092 KB Output is correct
6 Correct 65 ms 9412 KB Output is correct
7 Correct 106 ms 9156 KB Output is correct
8 Correct 111 ms 9412 KB Output is correct
9 Correct 102 ms 9412 KB Output is correct
10 Correct 76 ms 9156 KB Output is correct
11 Correct 80 ms 10688 KB Output is correct
12 Correct 56 ms 9924 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 9412 KB Output is correct
2 Correct 110 ms 9156 KB Output is correct
3 Correct 111 ms 9412 KB Output is correct
4 Correct 86 ms 9408 KB Output is correct
5 Correct 81 ms 9092 KB Output is correct
6 Correct 65 ms 9412 KB Output is correct
7 Correct 106 ms 9156 KB Output is correct
8 Correct 111 ms 9412 KB Output is correct
9 Correct 102 ms 9412 KB Output is correct
10 Correct 76 ms 9156 KB Output is correct
11 Correct 80 ms 10688 KB Output is correct
12 Correct 56 ms 9924 KB Output is correct
13 Incorrect 117 ms 12484 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -