Submission #854012

#	Time	Username	Problem	Language	Result	Execution time	Memory
854012		serifefedartar	Examination (JOI19_examination)	C++17	2 / 100	3043 ms	10528 KiB

examination

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 998244353;
const ll LOGN = 20;
const ll MAXN = 1e5 + 5;

const int BLOCK = 500;
struct Query {
	int A, B, C, idx;
	bool operator< (Query y) {	
		return make_pair(A / BLOCK, B) < make_pair(y.A / BLOCK, y.B);
	}
};

vector<Query> Q;
int fen[MAXN], ans[MAXN], sumCoor[MAXN];
vector<int> S, T, cc;
vector<pair<int,int>> tt, ss;
map<int,int> cnt;

void update(int k, int val) {
	k++;
	while (k < MAXN) {
		fen[k] += val;
		k += k & -k;
	}
}

int get(int k) {
	k++;
	int res = 0;
	while (k >= 1) {
		res += fen[k];
		k -= k & -k;
	}
	return res;
}

int main() {
	fast
	int N, Qs;
	cin >> N >> Qs;

	S = vector<int>(N);
	T = vector<int>(N);
	for (int i = 0; i < N; i++) {
		cin >> S[i] >> T[i];
		ss.push_back({S[i], i});
		tt.push_back({T[i], i});
		cc.push_back(S[i] + T[i]);
	}

	sort(cc.begin(), cc.end());
	sort(ss.begin(), ss.end());
	sort(tt.begin(), tt.end());

	for (int i = 0; i < N; i++)
		sumCoor[i] = lower_bound(cc.begin(), cc.end(), S[i] + T[i]) - cc.begin();

	for (int i = 0; i < Qs; i++) {
		Query q;
		cin >> q.A >> q.B >> q.C;
		q.A = lower_bound(ss.begin(), ss.end(), make_pair(q.A, 0)) - ss.begin();
		q.B = lower_bound(tt.begin(), tt.end(), make_pair(q.B, 0)) - tt.begin();
		q.C = lower_bound(cc.begin(), cc.end(), q.C) - cc.begin();
		q.idx = i;
		Q.push_back(q);
	}
	sort(Q.begin(), Q.end());

	int s = N; // tamamen sağda
	int t = N;
	for (auto u : Q) {
		int new_s = u.A;
		int new_t = u.B;
		while (new_s < s) {
			cnt[ss[s-1].s]++;
			if (cnt[ss[s-1].s] == 2)
				update(sumCoor[ss[s-1].s], 1);				
			s--;
		}
		while (new_t < t) {
			cnt[tt[t-1].s]++;
			if (cnt[tt[t-1].s] == 2)
				update(sumCoor[tt[t-1].s], 1);
			t--;
		}
		while (new_s > s) {
			cnt[ss[s].s]--;
			if (cnt[ss[s].s] == 1)
				update(sumCoor[ss[s].s], -1);
			s++;
		}
		while (new_t > t) {
			cnt[tt[t].s]--;
			if (cnt[tt[t].s] == 1)
				update(sumCoor[tt[t].s], -1);
			t++;
		}

		ans[u.idx] = get(MAXN - 2) - get(u.C - 1);
	}

	for (int i = 0; i < Qs; i++)
		cout << ans[i] << "\n";
}

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