oj.uz

Submission #172895

# Submission time Handle Problem Language Result Execution time Memory
172895 2020-01-02T17:46:31 Z ZwariowanyMarcin Examination (JOI19_examination) C++14
2 / 100
 1002 ms 361364 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define ll long long
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, n) for(int i = 0; i < n; ++i)

using namespace std;	

const int nax = 1e5 + 111;
const int pod = (1 << 17);

int n, q;
pair<int, int> t[nax];

struct gao {
	int x, y, z, id;
	bool operator <(gao a) const {
		return z < a.z;
	}
};

vector <gao> qu;

vector <int> val[2];

int daj(int x, int k) {
	return (int) (lower_bound(val[k].begin(), val[k].end(), x) - val[k].begin()) + 1;
}

struct nod {
	nod *l, *r;
	int sum;
};

nod T[40000000];
nod *wsk = T;

nod* aloc() {
	nod *r = wsk++;
	r->sum = 0;
	return r;
}

#define mak(x) x ? x : x = aloc()

void add(int x, nod *u, int l = 0, int r = pod - 1) {
	if(l == r) {
		u->sum++;
		return;
	}
	int m = (l + r) / 2;
	if(x <= m)	
		add(x, mak(u->l), l, m);
	else
		add(x, mak(u->r), m + 1, r);
	u->sum = (u->l ? u->l->sum : 0) + (u->r ? u->r->sum : 0);
}

int query(int x, int y, nod *u, int l = 0, int r = pod - 1) {
	if(!u) return 0;
	if(x <= l && r <= y) 
		return u->sum;
	int m = (l + r) / 2;
	int res = 0;
	if(x <= m)
		res += query(x, y, u->l, l, m);
	if(m < y)
		res += query(x, y, u->r, m + 1, r);
	return res;
}

nod *root[nax];
	
void addfen(int x, int y) {
	for(int i = x; i < nax; i += i & -i) 
		add(y, root[i]);
}

int queryfen(int x, int y) {
	int res = 0;
	for(int i = x; 0 < i; i -= i & -i)
		res += query(y, pod - 1, root[i]);
	return res;
}

int qq(int x, int y) {
	return queryfen(pod - 1, y) - queryfen(x - 1, y);
}	

int ans[nax];
			
int main() {
	scanf("%d %d", &n, &q);
	for(int i = 1; i <= n; ++i) {
		scanf("%d %d", &t[i].fi, &t[i].se);
		val[0].pb(t[i].fi);
		val[1].pb(t[i].se);
	}
	
	sort(t + 1, t + n + 1, [](pair<int,int> a, pair<int,int> b) {
		return a.fi + a.se < b.fi + b.se;
	});
	
	for(int i = 1; i <= q; ++i) {
		int x, y, z;
		scanf("%d %d %d", &x, &y, &z);
		qu.pb({x, y, z, i});
	}
	
	for(int i = 0; i < 2; ++i) {
		sort(val[i].begin(), val[i].end());
		val[i].erase(unique(val[i].begin(), val[i].end()), val[i].end());
	}
	
	sort(qu.begin(), qu.end());
		
	for(int i = 1; i < nax; ++i)
		root[i] = aloc();
		
	int wsk = n;
	
	for(int i = q - 1; 0 <= i; --i) {
		while(wsk >= 1 && qu[i].z <= t[wsk].fi + t[wsk].se) {
			addfen(daj(t[wsk].fi, 0), daj(t[wsk].se, 1));
			wsk--;
		}
		ans[qu[i].id] = qq(daj(qu[i].x, 0), daj(qu[i].y, 1));
	}
	
	for(int i = 1; i <= q; ++i)
		printf("%d\n", ans[i]);
	

	return 0;
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:97:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &q);
  ~~~~~^~~~~~~~~~~~~~~~~
examination.cpp:99:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &t[i].fi, &t[i].se);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &x, &y, &z);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3448 KB Output is correct
2 Correct 5 ms 3448 KB Output is correct
3 Correct 5 ms 3448 KB Output is correct
4 Correct 5 ms 3472 KB Output is correct
5 Correct 5 ms 3576 KB Output is correct
6 Correct 5 ms 3448 KB Output is correct
7 Correct 25 ms 7928 KB Output is correct
8 Correct 65 ms 7944 KB Output is correct
9 Correct 25 ms 8056 KB Output is correct
10 Correct 16 ms 5240 KB Output is correct
11 Correct 17 ms 6264 KB Output is correct
12 Correct 13 ms 3704 KB Output is correct
13 Correct 24 ms 8016 KB Output is correct
14 Correct 25 ms 7928 KB Output is correct
15 Correct 25 ms 8056 KB Output is correct
16 Correct 16 ms 6136 KB Output is correct
17 Correct 15 ms 4984 KB Output is correct
18 Correct 13 ms 3752 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1002 ms 361364 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 1002 ms 361364 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3448 KB Output is correct
2 Correct 5 ms 3448 KB Output is correct
3 Correct 5 ms 3448 KB Output is correct
4 Correct 5 ms 3472 KB Output is correct
5 Correct 5 ms 3576 KB Output is correct
6 Correct 5 ms 3448 KB Output is correct
7 Correct 25 ms 7928 KB Output is correct
8 Correct 65 ms 7944 KB Output is correct
9 Correct 25 ms 8056 KB Output is correct
10 Correct 16 ms 5240 KB Output is correct
11 Correct 17 ms 6264 KB Output is correct
12 Correct 13 ms 3704 KB Output is correct
13 Correct 24 ms 8016 KB Output is correct
14 Correct 25 ms 7928 KB Output is correct
15 Correct 25 ms 8056 KB Output is correct
16 Correct 16 ms 6136 KB Output is correct
17 Correct 15 ms 4984 KB Output is correct
18 Correct 13 ms 3752 KB Output is correct
19 Runtime error 1002 ms 361364 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -