oj.uz

답안 #953735

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
953735 2024-03-26T15:12:11 Z ByeWorld Examination (JOI19_examination) C++14
2 / 100
 2267 ms 1048576 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";
		bnc();
		if(a<=l && r<=b) return val;
		if(r<a || b<l) return 0;
		return le->que(a, b) + ri->que(a, b);
	}
	int upd(int a, int p){
		bnc();
		if(l==r && l==a){
			val += p;
		// cout << l << ' '<< r << ' ' << val << " upd\n";
			return val;
		}
		if(a<l || r<a) return val;
		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;
	}
	void bnc(){
		if(le==NULL){
			le = new seg();
			le->bd(l, mid);
		}
		if(ri==NULL){
			ri = new seg();
			ri->bd(mid+1, r);
		}
		if(val==NULL){
			val = new row();
			val->bd(1, maxz);
		}
	}
	int que(int x, int y, int a, int b){
		bnc();
		if(x<=l && r<=y) return val->que(a, b);
		if(r<x || y<l) return 0;
		// 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){
		bnc();
		if(l==r && l==x){
		// cout << l << ' '<< r << " lr_x\n";
			val->upd(a, p);
			return;
		}
		if(x<l || r<x) return;
		// 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2492 KB Output is correct
3 Correct 2 ms 2392 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 82 ms 80868 KB Output is correct
8 Correct 82 ms 80828 KB Output is correct
9 Correct 79 ms 80208 KB Output is correct
10 Correct 16 ms 12636 KB Output is correct
11 Correct 63 ms 59356 KB Output is correct
12 Correct 5 ms 2652 KB Output is correct
13 Correct 53 ms 52456 KB Output is correct
14 Correct 50 ms 52196 KB Output is correct
15 Correct 50 ms 52560 KB Output is correct
16 Correct 34 ms 29528 KB Output is correct
17 Correct 7 ms 3932 KB Output is correct
18 Correct 3 ms 2868 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2267 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2267 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2492 KB Output is correct
3 Correct 2 ms 2392 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 82 ms 80868 KB Output is correct
8 Correct 82 ms 80828 KB Output is correct
9 Correct 79 ms 80208 KB Output is correct
10 Correct 16 ms 12636 KB Output is correct
11 Correct 63 ms 59356 KB Output is correct
12 Correct 5 ms 2652 KB Output is correct
13 Correct 53 ms 52456 KB Output is correct
14 Correct 50 ms 52196 KB Output is correct
15 Correct 50 ms 52560 KB Output is correct
16 Correct 34 ms 29528 KB Output is correct
17 Correct 7 ms 3932 KB Output is correct
18 Correct 3 ms 2868 KB Output is correct
19 Runtime error 2267 ms 1048576 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -