oj.uz

Submission #1086236

# Submission time Handle Problem Language Result Execution time Memory
1086236 2024-09-09T19:52:51 Z 4QT0R Examination (JOI19_examination) C++17
0 / 100
 198 ms 19980 KB 
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>

struct event{
	int x;
	int x2;
	int y;
	int y2;
	int typ;
};

event pts[400003];

void init(int &n, int &q){
	cin >> n >> q;
	set<int> s;
	map<int,int> mp;
	for (int i = 1; i<=n; i++){
		cin >> pts[i].x >> pts[i].y;
		pts[i].x2=pts[i].x+pts[i].y;
		s.insert(pts[i].y);
	}
	for (int i = n+1; i<=n+q; i++){
		cin >> pts[i].x >> pts[i].y >> pts[i].y2;
		pts[i].x2=pts[i].y2;
		pts[i].y2=max(pts[i].y,pts[i].y2-pts[i].x);
		pts[i].typ=1;
		s.insert(pts[i].y);
		s.insert(pts[i].y2);
	}
	int iter=0;
	for (auto u : s)mp[u]=iter++;
	for (int i = 1; i<=n; i++)pts[i].y=mp[pts[i].y];
	for (int i = n+1; i<=n+q; i++){
		pts[i].y=mp[pts[i].y];
		pts[i].y2=mp[pts[i].y2];
	}
}

int ans[100002];
vector<pii> zap;

const int base=1<<19;
int tree[2*base];
void change(int v){
	v+=base;
	while(v){
		tree[v]++;
		v>>=1;
	}
}
int sum(int a, int b){
	if (a>b)return 0;
	a+=base-1;
	b+=base+1;
	int wyn=0;
	while(a/2!=b/2){
		if (!(a&1))wyn+=tree[a+1];
		if (b&1)wyn+=tree[b-1];
		a>>=1;
		b>>=1;
	}
	return wyn;
}

bool sorting(pii a, pii b){
	if (a.first==b.first)return a.second<b.second;
	return a.first>b.first;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n,q;
	init(n,q);
	for (int i = 1; i<=n+q; i++){
		zap.push_back({pts[i].x,i});
	}
	sort(zap.begin(),zap.end(),sorting);
	for (auto [x0,ind] : zap){
		if (pts[ind].typ==0)change(pts[ind].y);
		else ans[ind-n]+=sum(pts[ind].y2+1,base-1);
	}
	fill(tree,tree+2*base,0);
	zap.clear();
	for (int i = 1; i<=n+q; i++){
		zap.push_back({pts[i].x2,i});
	}
	sort(zap.begin(),zap.end(),sorting);
	for (auto [x0,ind] : zap){
		if (pts[ind].typ==0)change(pts[ind].y);
		else ans[ind-n]+=sum(pts[ind].y,pts[ind].y2);
	}
	for (int i = 1; i<=q; i++)cout << ans[i] << '\n';
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 3 ms 4444 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 7 ms 5468 KB Output is correct
8 Correct 7 ms 5468 KB Output is correct
9 Correct 10 ms 5464 KB Output is correct
10 Incorrect 5 ms 4956 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 198 ms 19980 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 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 3 ms 4444 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 7 ms 5468 KB Output is correct
8 Correct 7 ms 5468 KB Output is correct
9 Correct 10 ms 5464 KB Output is correct
10 Incorrect 5 ms 4956 KB Output isn't correct
11 Halted 0 ms 0 KB -