oj.uz

Submission #755050

# Submission time Handle Problem Language Result Execution time Memory
755050 2023-06-09T10:53:49 Z Dan4Life Examination (JOI19_examination) C++17
0 / 100
 416 ms 20496 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define all(a) begin(a),end(a)

const int mxN = (int)6e5+10;
int n, q, fen[mxN], ans[mxN/6];
struct Query{ int x, y, z, i, t; } A[mxN];
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<Query> v; v.clear();
	for(int i = l; i <= r; i++){
		if(i<=mid and !A[i].t) v.pb({0,A[i].y,A[i].z,A[i].i,A[i].t});
		if(i>mid and A[i].t) v.pb({0,A[i].y,A[i].z,A[i].i,A[i].t});
	}
	sort(all(v), [&](Query a, Query b){
		return mp(a.y,-a.t)>mp(b.y,-b.t);
	});
	vector<int> xd; xd.clear();
	for(auto [x,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+q; i++){
		cin >> x >> y; z = x+y;
		if(i>=n) cin >> z;
		A[i]={x,y,z,i-n,i>=n};
		v.pb(x), v.pb(y), v.pb(z);
	}
	sort(all(v)); v.erase(unique(all(v)),end(v));
	for(auto &[x,y,z,i,t] : A){
		x = lb(all(v),x)-begin(v)+1;
		y = lb(all(v),y)-begin(v)+1;
		z = lb(all(v),z)-begin(v)+1;
	}
	sort(all(A),[&](Query a, Query b){ 
		return mp(a.x,-a.t)>mp(b.x,-b.t);
	}); 
	CDQ_Dnc(0,n+q-1);
	for(int i = 0; i < q; i++) cout << ans[i] << "\n";
}

Compilation message

examination.cpp: In function 'void CDQ_Dnc(int, int)':
examination.cpp:16:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   16 |  if(l==r) return; int mid = (l+r)>>1;
      |  ^~
examination.cpp:16:19: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   16 |  if(l==r) return; int mid = (l+r)>>1;
      |                   ^~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 11988 KB Output is correct
2 Correct 37 ms 12056 KB Output is correct
3 Correct 38 ms 12116 KB Output is correct
4 Incorrect 36 ms 11988 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 20468 KB Output is correct
2 Incorrect 416 ms 20496 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 20468 KB Output is correct
2 Incorrect 416 ms 20496 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 11988 KB Output is correct
2 Correct 37 ms 12056 KB Output is correct
3 Correct 38 ms 12116 KB Output is correct
4 Incorrect 36 ms 11988 KB Output isn't correct
5 Halted 0 ms 0 KB -