oj.uz

Submission #1006357

# Submission time Handle Problem Language Result Execution time Memory
1006357 2024-06-23T20:37:47 Z AdamGS Examination (JOI19_examination) C++17
20 / 100
 136 ms 24352 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e5+7;
pair<ll,ll>T[LIM];
ll wynik[LIM];
pair<pair<ll,ll>,ll>pyt[LIM];
vector<pair<ll,pair<ll,ll>>>A;
vector<ll>skal;
map<ll,ll>mp;
ll tr[4*LIM], N=1, akt=0;
void upd(int v, ll x) {
	v+=N;
	while(v) {
		tr[v]+=x;
		v/=2;
	}
}
ll cnt(int l, int r) {
	if(l>r) return 0;
	l+=N; r+=N;
	ll ans=tr[l];
	if(l!=r) ans+=tr[r];
	while(l/2!=r/2) {
		if(l%2==0) ans+=tr[l+1];
		if(r%2==1) ans+=tr[r-1];
		l/=2; r/=2;
	}
	return ans;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, q;
	cin >> n >> q;
	rep(i, n) {
		cin >> T[i].st >> T[i].nd;
		A.pb({-T[i].st, {-1, T[i].nd}});
	}
	rep(i, q) {
		cin >> pyt[i].st.st >> pyt[i].st.nd >> pyt[i].nd;
		pyt[i].nd=max(pyt[i].nd, pyt[i].st.st+pyt[i].st.nd);
		A.pb({-max(pyt[i].st.st, pyt[i].nd-pyt[i].st.nd), {i, pyt[i].st.nd}});
	}
	for(auto i : A) 
		skal.pb(i.nd.nd);
	sort(all(skal));
	for(auto i : skal) 
		if(mp.find(i)==mp.end()) mp[i]=akt++;
	while(N<akt) N*=2;
	sort(all(A));
	for(auto i : A) {
		if(i.nd.st==-1) upd(mp[i.nd.nd], 1);
		else wynik[i.nd.st]+=cnt(mp[i.nd.nd], N-1);
	}
	rep(i, q) cout << wynik[i] << '\n';
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4484 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 125 ms 24352 KB Output is correct
2 Correct 133 ms 24196 KB Output is correct
3 Correct 120 ms 24244 KB Output is correct
4 Correct 47 ms 16568 KB Output is correct
5 Correct 131 ms 22708 KB Output is correct
6 Correct 42 ms 16196 KB Output is correct
7 Correct 128 ms 24248 KB Output is correct
8 Correct 115 ms 22196 KB Output is correct
9 Correct 108 ms 21940 KB Output is correct
10 Correct 121 ms 22196 KB Output is correct
11 Correct 43 ms 17856 KB Output is correct
12 Correct 36 ms 15484 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 24352 KB Output is correct
2 Correct 133 ms 24196 KB Output is correct
3 Correct 120 ms 24244 KB Output is correct
4 Correct 47 ms 16568 KB Output is correct
5 Correct 131 ms 22708 KB Output is correct
6 Correct 42 ms 16196 KB Output is correct
7 Correct 128 ms 24248 KB Output is correct
8 Correct 115 ms 22196 KB Output is correct
9 Correct 108 ms 21940 KB Output is correct
10 Correct 121 ms 22196 KB Output is correct
11 Correct 43 ms 17856 KB Output is correct
12 Correct 36 ms 15484 KB Output is correct
13 Incorrect 136 ms 23712 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 4484 KB Output isn't correct
2 Halted 0 ms 0 KB -