oj.uz

Submission #954945

# Submission time Handle Problem Language Result Execution time Memory
954945 2024-03-28T23:55:41 Z ByeWorld Examination (JOI19_examination) C++14
2 / 100
 3000 ms 886692 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define md ((l+r)>>1)
#define lf (id<<1)
#define rg ((id<<1)|1)
using namespace std;
typedef pair<ll,ll> pii;
typedef pair<pii,ll> ipii;
const int MAXN = 2e5+10;
const ll INF = 2e18+10;
const ll LOG = 61;
const int MOD = 998244353;

int maxy, maxz;

struct row {
	int l, r, mid, val;
	row *le, *ri;
	void bd(int l2, int r2){
		l = l2; r = r2; mid = md;
		le = NULL; ri = NULL;
	}
	void bnc(){
		if(le==NULL){
			le = new row();
			le->bd(l, mid);
		}
		if(ri==NULL){
			ri = new row();
			ri->bd(mid+1, r);
		}
	}
	int que(int a, int b){
		// cout << l << ' '<< r << ' ' << " que\n";
		if(a<=l && r<=b) return val;
		if(r<a || b<l) return 0;
		bnc();
		return le->que(a, b) + ri->que(a, b);
	}
	int upd(int a, int p){
		if(l==r && l==a){
			val += p;
		// cout << l << ' '<< r << ' ' << val << " upd\n";
			return val;
		}
		if(a<l || r<a) return val;
		bnc();
		return val = le->upd(a, p) + ri->upd(a, p);
	}
};
struct seg {
	int l, r, mid;
	row *val;
	seg *le, *ri;
	void bd(int l2, int r2){
		l = l2; r = r2; mid = md;
		val = new row();
		val->bd(1, maxz);
	}
	void bnc(){
		if(le==NULL){
			le = new seg();
			le->bd(l, mid);
		}
		if(ri==NULL){
			ri = new seg();
			ri->bd(mid+1, r);
		}
	}
	int que(int x, int y, int a, int b){
		if(x<=l && r<=y) return val->que(a, b);
		if(r<x || y<l) return 0;
		bnc();
		// cout << l << ' '<< r << " queluar\n";
		return le->que(x, y, a, b) + ri->que(x, y, a, b);
	}
	void upd(int x, int a, int p){
		if(l==r && l==x){
		// cout << l << ' '<< r << " lr_x\n";
			val->upd(a, p);
			return;
		}
		if(x<l || r<x) return;
		bnc();
		// cout << l << ' '<< r << " lr_x\n";
		val->upd(a, p); // segtree parentnya juga kena
		le->upd(x, a, p); ri->upd(x, a, p);
		return;
	}
} A;

int n, q;
vector <pii> vec;
vector <pair<pii,pii>> que;
vector <int> cc1, cc2;
int z[MAXN], y[MAXN], X[MAXN], Y[MAXN];
int ans[MAXN];

signed main() {
	cin >> n >> q;
	for(int i=1; i<=n; i++){
		cin >> X[i] >> Y[i];
		cc1.pb(Y[i]); cc2.pb(X[i]+Y[i]);
	}

	for(int i=1; i<=q; i++){
		int a, b, c; cin >> a >> b >> c;
		que.pb({{a, b}, {c, i}});
		// cc1.pb(b); cc2.pb(c);
	}
	sort(que.rbegin(), que.rend());

	cc1.pb(-1);
	sort(cc1.begin(), cc1.end());
	cc1.resize( unique(cc1.begin(), cc1.end()) - cc1.begin() );
	cc2.pb(-1);
	sort(cc2.begin(), cc2.end());
	cc2.resize( unique(cc2.begin(), cc2.end()) - cc2.begin() );

	for(int i=1; i<=n; i++){
		y[i] = lower_bound(cc1.begin(), cc1.end(), Y[i]) - cc1.begin();
		z[i] = lower_bound(cc2.begin(), cc2.end(), X[i]+Y[i]) - cc2.begin();
		vec.pb({X[i], i});
		maxy = max(maxy, y[i]);
		maxz = max(maxz, z[i]);
		// cout << i << ' ' << y[i] << ' ' << z[i] << " ins\n";
	}
	vec.pb({INF, INF});
	sort(vec.rbegin(), vec.rend());

	A.bd(1, maxy);
	int las = 1;
	for(int i=0; i<q; i++){
		int a = que[i].fi.fi, id = que[i].se.se;
		int b = lower_bound(cc1.begin(), cc1.end(), que[i].fi.se) - cc1.begin();
		int c = lower_bound(cc2.begin(), cc2.end(), que[i].se.fi) - cc2.begin();
		// cout << id << ' '<< b << ' ' << c << " que\n";
		while(las<=n && a <= vec[las].fi){
			int idx = vec[las].se;
			// cout << y[idx] << ' '<< z[idx] << " idxupd\n";
			A.upd(y[idx], z[idx], 1);
			las++;
		}
		ans[id] = A.que(b, maxy, c, maxz);
	}

	for(int i=1; i<=q; i++) cout << ans[i] << "\n"; //[i==q];
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 1 ms 2492 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 39 ms 30536 KB Output is correct
8 Correct 39 ms 30808 KB Output is correct
9 Correct 46 ms 30584 KB Output is correct
10 Correct 13 ms 6236 KB Output is correct
11 Correct 35 ms 20564 KB Output is correct
12 Correct 4 ms 2648 KB Output is correct
13 Correct 30 ms 23664 KB Output is correct
14 Correct 29 ms 23792 KB Output is correct
15 Correct 28 ms 23892 KB Output is correct
16 Correct 17 ms 12380 KB Output is correct
17 Correct 8 ms 2908 KB Output is correct
18 Correct 4 ms 2652 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3065 ms 886692 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3065 ms 886692 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 1 ms 2492 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 39 ms 30536 KB Output is correct
8 Correct 39 ms 30808 KB Output is correct
9 Correct 46 ms 30584 KB Output is correct
10 Correct 13 ms 6236 KB Output is correct
11 Correct 35 ms 20564 KB Output is correct
12 Correct 4 ms 2648 KB Output is correct
13 Correct 30 ms 23664 KB Output is correct
14 Correct 29 ms 23792 KB Output is correct
15 Correct 28 ms 23892 KB Output is correct
16 Correct 17 ms 12380 KB Output is correct
17 Correct 8 ms 2908 KB Output is correct
18 Correct 4 ms 2652 KB Output is correct
19 Execution timed out 3065 ms 886692 KB Time limit exceeded
20 Halted 0 ms 0 KB -