oj.uz

Submission #755041

# Submission time Handle Problem Language Result Execution time Memory
755041 2023-06-09T10:33:35 Z Dan4Life Examination (JOI19_examination) C++17
0 / 100
 183 ms 20520 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(a) begin(a),end(a)

const int mxN = (int)7e5+10;
int n, q, fen[mxN], ans[mxN/7];
struct Query{ int x, y, z, i, t; };
struct Query2{ int y, z, i, t; };

vector<Query> A;

void upd(int x, int v){ for(; x<mxN; x+=x&-x) fen[x]+=v; }
int sum(int x){ int s=0;for(; x; x-=x&-x) s+=fen[x]; return s; }
int sum(int a, int b){ return (a<=b)*(sum(b)-sum(a-1)); }

void CDQ_Dnc(int l, int r){
	if(l==r) return;
	int mid = (l+r)>>1;
	vector<Query2> v; v.clear();
	for(int i = l; i <= r; i++){
		if(i<=mid and !A[i].t) v.pb({A[i].y,A[i].z,A[i].i,A[i].t});
		if(i>mid and A[i].t) v.pb({A[i].y,A[i].z,A[i].i,A[i].t});
	}
	sort(all(v), [&](Query2 a, Query2 b){return a.y>b.y;});
	vector<int> xd; xd.clear();
	for(auto [y,z,i,t] : v){
		if(!t) upd(z,1),xd.pb(z);
		else ans[i]+=sum(z,mxN-1);
	}
	for(auto u : xd) upd(u,-1);
	CDQ_Dnc(l,mid), CDQ_Dnc(mid+1,r);
}

int32_t main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> q; int x, y, z;
	vector<int> v; v.clear();
	for(int i = 0; i < n; i++){
		cin >> x >> y; z = x+y;
		v.pb(x), v.pb(y), v.pb(z);
		A.pb({x,y,z,i,0});
	}
	for(int i = 0; i < q; i++){
		cin >> x >> y >> z;
		v.pb(x), v.pb(y), v.pb(z);
		A.pb({x,y,z,i,1});
	}
	sort(all(v)); v.erase(unique(all(v)),end(v));
	for(auto &[x,y,z,i,t] : A){
		x = lower_bound(all(v),x)-begin(v);
		y = lower_bound(all(v),y)-begin(v);
		z = lower_bound(all(v),z)-begin(v);
	}
	sort(all(A),[&](Query a, Query b){return a.x>b.x;}); CDQ_Dnc(0,n+q-1);
	for(int i = 0; i < q; i++) cout << ans[i] << "\n";
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Runtime error 1 ms 468 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 183 ms 20520 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 183 ms 20520 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Runtime error 1 ms 468 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -