제출 #954954

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
954954		ByeWorld	Examination (JOI19_examination)	C++14	100 / 100	263 ms	24936 KiB

examination

#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 = 3e5+10;
const ll INF = 2e18+10;
const ll LOG = 61;
const int MOD = 998244353;
 
struct fen {
	int st[2*MAXN];
    int que(int x){
        int te = 0;
        for(; x>=1; x-=(x&(-x))) te += st[x];
        return te;
    }
    void upd(int x, int p){
        for(; x<=2*MAXN-10; x+=(x&(-x))) st[x] += p;
    }
} A, B;
 
int n, q;
vector <pii> vec;
vector <pair<pii,pii>> que;
vector <int> cc1, cc2;
int x[MAXN], y[MAXN], z[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(X[i]); cc2.pb(Y[i]); 
		vec.pb({X[i]+Y[i], i});
	}
 
	for(int i=1; i<=q; i++){
		int a, b, c; cin >> a >> b >> c;
        c = max(c, a+b);
		que.pb({{c, i}, {a, b}});
		cc1.pb(a); cc2.pb(b);
	}
	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++){
		x[i] = lower_bound(cc1.begin(), cc1.end(), X[i]) - cc1.begin();
		y[i] = lower_bound(cc2.begin(), cc2.end(), Y[i]) - cc2.begin();
		// cout << i << ' ' << y[i] << ' ' << z[i] << " ins\n";
	}
	vec.pb({INF, INF}); // sort based on x[i]+y[i]
	sort(vec.rbegin(), vec.rend());
 
	int las = 1;
	for(int i=0; i<q; i++){
		int c = que[i].fi.fi, id = que[i].fi.se;
		int a = lower_bound(cc1.begin(), cc1.end(), que[i].se.fi) - cc1.begin();
		int b = lower_bound(cc2.begin(), cc2.end(), que[i].se.se) - cc2.begin();
		// cout << id << ' '<< b << ' ' << c << " que\n";
		while(las<=n && c <= vec[las].fi){
			int idx = vec[las].se;
			// cout << y[idx] << ' '<< z[idx] << " idxupd\n";
			A.upd(x[idx], 1);
            B.upd(y[idx], 1);
			las++;
		}
        int neg = A.que(a-1) + B.que(b-1); // negate yg di X, Y
		ans[id] = las-1 - neg; 
	}
 
	for(int i=1; i<=q; i++) cout << ans[i] << "\n"; //[i==q];
}

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57