oj.uz

Submission #259506

# Submission time Handle Problem Language Result Execution time Memory
259506 2020-08-07T23:47:24 Z ChrisT Examination (JOI19_examination) C++17
0 / 100
 320 ms 41820 KB 
#include <bits/stdc++.h>
using namespace std;
const int MN = 2e5 + 5;
int ans[MN], bit[MN];
vector<int> xs;
void getx (int &x) {x = lower_bound(xs.begin(),xs.end(),x) - xs.begin() + 1;}
void inc (int i) {
	for (i=MN-i;i<MN;i+=i&-i) ++bit[i];
}
void dec (int i) {
	for (i=MN-i;i<MN;i+=i&-i) --bit[i];
}
int query (int i) {
	int ret = 0;
	for (i=MN-i;i;i^=i&-i) ret += bit[i];
	return ret;
}
struct Event {
	int x,y,z,id;
};
void cdq (int l, int r, vector<Event> &events) { //over z
	if (events.empty()) return;
	vector<Event> lq,rq;
	int mid = (l + r) / 2;
	for (Event &e : events) {
		if (e.z > mid) {
			rq.push_back(e);
			if (e.id<0) inc(e.y);
		} else {
			lq.push_back(e);
			if (e.id>0) ans[e.id] += query(e.y);
		}
	}
	for (Event &e : rq) if (e.id<0) dec(e.y);
	if (l < r) {
		cdq(l,mid,lq);
		cdq(mid+1,r,rq);
	}
}
int main () {
	int n,q;
	scanf ("%d %d",&n,&q);
	vector<Event> events;
	for (int i = 1; i <= n; i++) {
		int s,t;
		scanf ("%d %d",&s,&t); xs.push_back(t);
		events.push_back({s,t,s+t,-i});
	}
	for (int i = 1; i <= q; i++) {
		int x,y,z;
		scanf ("%d %d %d",&x,&y,&z); xs.push_back(y);
		events.push_back({x,y,z,i});
	}
	sort(xs.begin(),xs.end()); xs.erase(unique(xs.begin(),xs.end()),xs.end());
	for (auto &au : events) getx(au.y);
	xs.clear();
	for (auto &au : events) xs.push_back(au.z);
	sort(xs.begin(),xs.end()); xs.erase(unique(xs.begin(),xs.end()),xs.end());
	for (auto &au : events) getx(au.z);
	sort(events.begin(),events.end(),[](const Event &a, const Event &b) {return a.x > b.x || (a.x == b.x && a.id < b.id);});
	cdq(1,xs.size(),events);
	for (int i = 1; i <= q; i++) printf ("%d\n",ans[i]);
	return 0;
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d %d",&n,&q);
  ~~~~~~^~~~~~~~~~~~~~~
examination.cpp:46:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d %d",&s,&t); xs.push_back(t);
   ~~~~~~^~~~~~~~~~~~~~~
examination.cpp:51:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d %d %d",&x,&y,&z); xs.push_back(y);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 10 ms 896 KB Output is correct
8 Correct 11 ms 896 KB Output is correct
9 Correct 12 ms 896 KB Output is correct
10 Correct 9 ms 768 KB Output is correct
11 Correct 10 ms 816 KB Output is correct
12 Incorrect 4 ms 768 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 41692 KB Output is correct
2 Correct 320 ms 41820 KB Output is correct
3 Correct 317 ms 41692 KB Output is correct
4 Correct 236 ms 39132 KB Output is correct
5 Correct 297 ms 39644 KB Output is correct
6 Incorrect 135 ms 20828 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 41692 KB Output is correct
2 Correct 320 ms 41820 KB Output is correct
3 Correct 317 ms 41692 KB Output is correct
4 Correct 236 ms 39132 KB Output is correct
5 Correct 297 ms 39644 KB Output is correct
6 Incorrect 135 ms 20828 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 10 ms 896 KB Output is correct
8 Correct 11 ms 896 KB Output is correct
9 Correct 12 ms 896 KB Output is correct
10 Correct 9 ms 768 KB Output is correct
11 Correct 10 ms 816 KB Output is correct
12 Incorrect 4 ms 768 KB Output isn't correct
13 Halted 0 ms 0 KB -