oj.uz

답안 #953742

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
953742 2024-03-26T15:21:20 Z ByeWorld Examination (JOI19_examination) C++14
2 / 100
 2264 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";
		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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 48 ms 41672 KB Output is correct
8 Correct 49 ms 41504 KB Output is correct
9 Correct 49 ms 41208 KB Output is correct
10 Correct 12 ms 7772 KB Output is correct
11 Correct 45 ms 30804 KB Output is correct
12 Correct 4 ms 2648 KB Output is correct
13 Correct 31 ms 27220 KB Output is correct
14 Correct 31 ms 27288 KB Output is correct
15 Correct 31 ms 27476 KB Output is correct
16 Correct 20 ms 15960 KB Output is correct
17 Correct 6 ms 3164 KB Output is correct
18 Correct 3 ms 2652 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2264 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 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 48 ms 41672 KB Output is correct
8 Correct 49 ms 41504 KB Output is correct
9 Correct 49 ms 41208 KB Output is correct
10 Correct 12 ms 7772 KB Output is correct
11 Correct 45 ms 30804 KB Output is correct
12 Correct 4 ms 2648 KB Output is correct
13 Correct 31 ms 27220 KB Output is correct
14 Correct 31 ms 27288 KB Output is correct
15 Correct 31 ms 27476 KB Output is correct
16 Correct 20 ms 15960 KB Output is correct
17 Correct 6 ms 3164 KB Output is correct
18 Correct 3 ms 2652 KB Output is correct
19 Runtime error 2264 ms 1048576 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -