oj.uz

Submission #187160

# Submission time Handle Problem Language Result Execution time Memory
187160 2020-01-12T13:22:56 Z super_j6 Examination (JOI19_examination) C++14
0 / 100
 1309 ms 406972 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;
#define endl '\n'
#define pi pair<int, int>
#define pii pair<pi, pi>

struct segTree{
	int l, r;
	segTree *left = 0, *right = 0;
	long val;
	
	segTree(int a, int b){
		l = a;
		r = b;
	}
	
	void add(int x, int v){
		if(x < l || r < x) return;
		if(l == r){
			val += v;
			return;
		}
		
		int mid = (l + r) / 2;
		if(x <= mid){
			if(!left) left = new segTree(l, mid);
			left->add(x, v);
		}else{
			if(!right) right = new segTree(mid + 1, r);
			right->add(x, v);
		}
		
		val = (left ? left->val : 0) + (right ? right->val : 0);
	}
	
	long qry(int a, int b){
		if(r < a || b < l) return 0;
		if(a <= l && r <= b) return val;
		
		return (left ? left->qry(a, b) : 0) + (right ? right->qry(a, b) : 0);
	}
};

const int maxn = 100002;

struct BIT{
	segTree *bit[maxn];
	
	BIT(){
		memset(bit, 0, sizeof(bit));
	}
	
	void add(int x, int y, int v){
		for(x++; x < maxn; x += x & -x){
			if(!bit[x]) bit[x] = new segTree(0, 2 * maxn);
			bit[x]->add(y, v);
		}
	}
	
	int qry(int x, int y, int Y){
		int ret = 0;
		for(x++; x; x -= x & -x) if(bit[x]) ret += bit[x]->qry(y, Y);
		return ret;
	}
	
	int qry(int x, int X, int y, int Y){
		return qry(X, y, Y) - qry(x - 1, y, Y);
	}
};

int n, q;
pi a[maxn];
pii qry[maxn];
BIT bit;
int ans[maxn];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n >> q;
	
	for(int i = 0; i < n; i++) cin >> a[i].first >> a[i].second;
	for(int i = 0; i < q; i++){
		cin >> qry[i].first.first >> qry[i].second.first >> qry[i].second.second;
		qry[i].first.second = i;
	} 
	
	sort(a, a + n, greater<pi>());
	sort(qry, qry + q, greater<pii>());
	
	for(int i = 0, j = 0; i < q; i++){
		for(; j < n && a[j].first >= qry[i].first.first; j++) bit.add(a[j].second, a[j].first + a[j].second, 1);
		ans[qry[i].first.second] = bit.qry(qry[i].second.first, maxn - 1, qry[i].second.second, 2 * maxn);
	}
	
	for(int i = 0; i < q; i++) cout << ans[i] << endl;

	return 0;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1272 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 3 ms 1144 KB Output is correct
4 Runtime error 5 ms 2168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1309 ms 406972 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1309 ms 406972 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1272 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 3 ms 1144 KB Output is correct
4 Runtime error 5 ms 2168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -