oj.uz

Submission #932334

# Submission time Handle Problem Language Result Execution time Memory
932334 2024-02-23T08:22:26 Z Baizho Examination (JOI19_examination) C++14
100 / 100
 1563 ms 165124 KB 
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
  
#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
 
// #pragma GCC optimize("Ofast,unroll-loops,fast-math")
// #pragma GCC target("popcnt")
 
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
 
#define sz size()
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define pb push_back
 
const int mod = ll(1e9)+7; //(b + (a%b)) % b (to mod -1%(10^9+7) correctly in c++ its -1 but its suppose to be 10^9+6
const ll MOD = 998244353;  // (a%mod)*(binpow(b,mod-2,mod) = (a/b)%mod
const int N = ll(1e5)+100;
const int M = ll(2e5) + 100;
const long long inf = 5e18;
const long double eps = 1e-15L;
 
ll lcm(ll a, ll b) { return (a / __gcd(a,b))*b; }
 
ll binpow(ll a, ll b, ll m) { ll res=1; a %= m; while(b>0){ if(b&1)res=(res * a) % m; a=(a * a) % m; b/=2; } return res%m;}
 
void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
 
int n, q, ans[N], x[N], y[N], cy[N], a[N], b[N], cb[N], c[N], lim;
vector<int> qu[N];

ordered_set t[N * 8];

void update(int v, int tl, int tr, int p, int x) {
	t[v].insert(x);
	if(tl == tr) return;
	int tm = (tl + tr) / 2;
	if(p <= tm) update(v + v, tl, tm, p, x);
	else update(v + v + 1, tm + 1, tr, p, x);
}

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

void Baizho() {
	cin>>n>>q;
	vector<int> comp;
	vector<pair<int, int> > range;
	for(int i = 1; i <= n; i ++) {
		cin>>x[i]>>y[i];
		range.pb({x[i], y[i]});
		comp.pb(y[i]);
	}
	sort(all(range));
	for(int i = 1; i <= n; i ++) {
		x[i] = range[i - 1].ff, y[i] = range[i - 1].ss;
	}
	for(int i = 1; i <= q; i ++) {
		cin>>a[i]>>b[i]>>c[i];
		comp.pb(b[i]);
		if(x[n] < a[i]) continue;
		// find position j such that x_j >= a
		int l = 1, r = n;
		while(l <= r) {
			int mid = (l + r) / 2;
			if(a[i] <= x[mid]) r = mid - 1;
			else l = mid + 1;
		} r += 1;
		qu[r].pb(i);
	}
	sort(all(comp));
	comp.erase(unique(all(comp)), comp.end());
	lim = comp.size();
	for(int i = 1; i <= max(n, q); i ++) {
		if(i <= n) cy[i] = upper_bound(all(comp), y[i]) - comp.begin();
		if(i <= q) cb[i] = upper_bound(all(comp), b[i]) - comp.begin();
	}
	for(int i = n; i >= 1; i --) {
		// add this
		update(1, 1, lim, cy[i], x[i] + y[i]);
		for(auto p : qu[i]) {
			// how many positions from cb...lim that have values >= c[i]
//			cout<<i<<" "<<p<<endl;
			ans[p] = get(1, 1, lim, cb[p], lim, c[p]);
		}
	}
	for(int i = 1; i <= q; i ++) cout<<ans[i]<<"\n";
}
 
signed main() {		
// 	Freopen("nondec");
    ios_base::sync_with_stdio(false);   
    cin.tie(0);cout.tie(0); 
//   	precalc();
   	
    int ttt = 1;
//    cin>>ttt;
 
    for(int i=1; i<=ttt; i++) {Baizho(); }
}

Compilation message

examination.cpp: In function 'void Freopen(std::string)':
examination.cpp:35:34: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 | void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
      |                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:35:76: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 | void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
      |                                                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 66968 KB Output is correct
2 Correct 34 ms 66900 KB Output is correct
3 Correct 36 ms 66816 KB Output is correct
4 Correct 36 ms 66812 KB Output is correct
5 Correct 45 ms 66780 KB Output is correct
6 Correct 53 ms 66896 KB Output is correct
7 Correct 47 ms 69056 KB Output is correct
8 Correct 49 ms 68960 KB Output is correct
9 Correct 47 ms 68944 KB Output is correct
10 Correct 41 ms 67664 KB Output is correct
11 Correct 74 ms 69020 KB Output is correct
12 Correct 46 ms 67672 KB Output is correct
13 Correct 50 ms 68920 KB Output is correct
14 Correct 60 ms 68944 KB Output is correct
15 Correct 48 ms 68892 KB Output is correct
16 Correct 65 ms 68964 KB Output is correct
17 Correct 38 ms 67420 KB Output is correct
18 Correct 43 ms 67508 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1337 ms 154144 KB Output is correct
2 Correct 1385 ms 154372 KB Output is correct
3 Correct 1345 ms 154360 KB Output is correct
4 Correct 273 ms 93528 KB Output is correct
5 Correct 1008 ms 153396 KB Output is correct
6 Correct 229 ms 92752 KB Output is correct
7 Correct 1381 ms 153432 KB Output is correct
8 Correct 1248 ms 152320 KB Output is correct
9 Correct 1169 ms 151444 KB Output is correct
10 Correct 812 ms 152764 KB Output is correct
11 Correct 144 ms 81352 KB Output is correct
12 Correct 273 ms 84612 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1337 ms 154144 KB Output is correct
2 Correct 1385 ms 154372 KB Output is correct
3 Correct 1345 ms 154360 KB Output is correct
4 Correct 273 ms 93528 KB Output is correct
5 Correct 1008 ms 153396 KB Output is correct
6 Correct 229 ms 92752 KB Output is correct
7 Correct 1381 ms 153432 KB Output is correct
8 Correct 1248 ms 152320 KB Output is correct
9 Correct 1169 ms 151444 KB Output is correct
10 Correct 812 ms 152764 KB Output is correct
11 Correct 144 ms 81352 KB Output is correct
12 Correct 273 ms 84612 KB Output is correct
13 Correct 1517 ms 154308 KB Output is correct
14 Correct 1379 ms 154504 KB Output is correct
15 Correct 1375 ms 154184 KB Output is correct
16 Correct 315 ms 93584 KB Output is correct
17 Correct 1043 ms 153448 KB Output is correct
18 Correct 246 ms 92828 KB Output is correct
19 Correct 1471 ms 154236 KB Output is correct
20 Correct 1400 ms 154260 KB Output is correct
21 Correct 1516 ms 153092 KB Output is correct
22 Correct 822 ms 152848 KB Output is correct
23 Correct 155 ms 81360 KB Output is correct
24 Correct 253 ms 84616 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 66968 KB Output is correct
2 Correct 34 ms 66900 KB Output is correct
3 Correct 36 ms 66816 KB Output is correct
4 Correct 36 ms 66812 KB Output is correct
5 Correct 45 ms 66780 KB Output is correct
6 Correct 53 ms 66896 KB Output is correct
7 Correct 47 ms 69056 KB Output is correct
8 Correct 49 ms 68960 KB Output is correct
9 Correct 47 ms 68944 KB Output is correct
10 Correct 41 ms 67664 KB Output is correct
11 Correct 74 ms 69020 KB Output is correct
12 Correct 46 ms 67672 KB Output is correct
13 Correct 50 ms 68920 KB Output is correct
14 Correct 60 ms 68944 KB Output is correct
15 Correct 48 ms 68892 KB Output is correct
16 Correct 65 ms 68964 KB Output is correct
17 Correct 38 ms 67420 KB Output is correct
18 Correct 43 ms 67508 KB Output is correct
19 Correct 1337 ms 154144 KB Output is correct
20 Correct 1385 ms 154372 KB Output is correct
21 Correct 1345 ms 154360 KB Output is correct
22 Correct 273 ms 93528 KB Output is correct
23 Correct 1008 ms 153396 KB Output is correct
24 Correct 229 ms 92752 KB Output is correct
25 Correct 1381 ms 153432 KB Output is correct
26 Correct 1248 ms 152320 KB Output is correct
27 Correct 1169 ms 151444 KB Output is correct
28 Correct 812 ms 152764 KB Output is correct
29 Correct 144 ms 81352 KB Output is correct
30 Correct 273 ms 84612 KB Output is correct
31 Correct 1517 ms 154308 KB Output is correct
32 Correct 1379 ms 154504 KB Output is correct
33 Correct 1375 ms 154184 KB Output is correct
34 Correct 315 ms 93584 KB Output is correct
35 Correct 1043 ms 153448 KB Output is correct
36 Correct 246 ms 92828 KB Output is correct
37 Correct 1471 ms 154236 KB Output is correct
38 Correct 1400 ms 154260 KB Output is correct
39 Correct 1516 ms 153092 KB Output is correct
40 Correct 822 ms 152848 KB Output is correct
41 Correct 155 ms 81360 KB Output is correct
42 Correct 253 ms 84616 KB Output is correct
43 Correct 1553 ms 160032 KB Output is correct
44 Correct 1563 ms 165100 KB Output is correct
45 Correct 1443 ms 165024 KB Output is correct
46 Correct 330 ms 96872 KB Output is correct
47 Correct 1152 ms 162536 KB Output is correct
48 Correct 243 ms 93656 KB Output is correct
49 Correct 1547 ms 164000 KB Output is correct
50 Correct 1518 ms 165124 KB Output is correct
51 Correct 1448 ms 163744 KB Output is correct
52 Correct 888 ms 161728 KB Output is correct
53 Correct 235 ms 83912 KB Output is correct