oj.uz

Submission #997967

# Submission time Handle Problem Language Result Execution time Memory
997967 2024-06-13T07:21:50 Z vjudge1 Examination (JOI19_examination) C++17
100 / 100
 388 ms 25972 KB 
#include "bits/stdc++.h"
using namespace std;
 
#ifdef N_N_C
#include "debug.h"
#else
#define cebug(...) "Arya"
#endif
 
#define ll long long
 
const int N=1e6+5;
const int mod=1e9+7;
 
struct Point{
	int x,y,z,id,v;
	bool operator < (const Point &o){
		if(x==o.x){
			if(y==o.y) return z>o.z;
			return y>o.y;
		}
		return x<o.x;
	}
};
vector <Point> v,v1;
int n,q,ans[N],ans1[N];
vector <int> compress;
int f(int x){
	return lower_bound(compress.begin(),compress.end(),x)-compress.begin()+1;
}
struct BIT{
	#define gb(x) (x&(-x))
   	int n;
   	vector <int> bit;
   	void init(int _n){
   		bit.resize(_n,0);
   		n=_n;
   	}
   	void update(int pos, int val){
   		int i=pos;
      	for (; i<n; i+=gb(i)) bit[i]+=val;
   	}
   	int get(int pos){
    	int ans=0,i=pos;
      	for (; i; i-=gb(i)) ans+=bit[i];
      	return ans;
   	}
}fw;
void cdq(int l, int r){
	if(l+1==r) return;
	int mid=(l+r)>>1;
	cdq(l,mid);
	cdq(mid,r);
	vector <Point> tmp;
	vector <int> record;
	int a=l,b=mid;
	while(a<mid and b<r){
		if(v[a].y<v[b].y) fw.update(v[a].z,v[a].v),record.push_back(a),tmp.push_back(v[a++]);
		else ans[v[b].id]+=fw.get(v[b].z-1),tmp.push_back(v[b++]); 
	}
	while(a<mid) tmp.push_back(v[a++]);
	while(b<r) ans[v[b].id]+=fw.get(v[b].z-1),tmp.push_back(v[b++]);
	for(auto a:record) fw.update(v[a].z,-v[a].v);
	for(int i=l; i<r; i++) v[i]=tmp[i-l];
	vector <int> ().swap(record);
	vector <Point> ().swap(tmp);
}
void sol(){
	// count pair i j : i_x<j_x, i_x<j_y, i_z<j_z
	fw.init(N);
	cin>>n>>q;
	for(int i=1; i<=n; i++){
		int x,y;
		cin>>x>>y;
		v.push_back({-x,-y,-x-y,0,1});
		compress.push_back(-x);
		compress.push_back(-y);
		compress.push_back(-x-y);
	}
	for(int i=1; i<=q; i++){
		int x,y,z;
		cin>>x>>y>>z;
		v.push_back({-x+1,-y+1,-z+1,i,0});
		compress.push_back(-x+1);
		compress.push_back(-y+1);
		compress.push_back(-z+1);
	}
	sort(compress.begin(),compress.end());
	compress.erase(unique(compress.begin(),compress.end()),compress.end());
	for(auto &[x,y,z,i,v]:v){
		x=f(x);
		y=f(y);
		z=f(z);
	}
	sort(v.begin(),v.end());
	cdq(0,(int)v.size());
	for(int i=1; i<=q; i++) cout<<ans[i]<<"\n";
}
signed main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen(".inp", "r", stdin);
    // freopen(".out", "w", stdout);
    int tt=1;
    //cin>>tt; 
    while(tt--){
    	sol();
    }
    cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6232 KB Output is correct
2 Correct 2 ms 6236 KB Output is correct
3 Correct 2 ms 6236 KB Output is correct
4 Correct 2 ms 6236 KB Output is correct
5 Correct 2 ms 6236 KB Output is correct
6 Correct 1 ms 6236 KB Output is correct
7 Correct 9 ms 6748 KB Output is correct
8 Correct 9 ms 6936 KB Output is correct
9 Correct 9 ms 6748 KB Output is correct
10 Correct 9 ms 6748 KB Output is correct
11 Correct 7 ms 6748 KB Output is correct
12 Correct 6 ms 6748 KB Output is correct
13 Correct 8 ms 6748 KB Output is correct
14 Correct 8 ms 6748 KB Output is correct
15 Correct 8 ms 6748 KB Output is correct
16 Correct 6 ms 6748 KB Output is correct
17 Correct 9 ms 6748 KB Output is correct
18 Correct 4 ms 6748 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 24788 KB Output is correct
2 Correct 291 ms 25044 KB Output is correct
3 Correct 291 ms 25456 KB Output is correct
4 Correct 247 ms 24952 KB Output is correct
5 Correct 187 ms 25364 KB Output is correct
6 Correct 138 ms 25456 KB Output is correct
7 Correct 258 ms 25284 KB Output is correct
8 Correct 286 ms 25212 KB Output is correct
9 Correct 278 ms 25720 KB Output is correct
10 Correct 165 ms 25972 KB Output is correct
11 Correct 219 ms 24908 KB Output is correct
12 Correct 110 ms 24776 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 24788 KB Output is correct
2 Correct 291 ms 25044 KB Output is correct
3 Correct 291 ms 25456 KB Output is correct
4 Correct 247 ms 24952 KB Output is correct
5 Correct 187 ms 25364 KB Output is correct
6 Correct 138 ms 25456 KB Output is correct
7 Correct 258 ms 25284 KB Output is correct
8 Correct 286 ms 25212 KB Output is correct
9 Correct 278 ms 25720 KB Output is correct
10 Correct 165 ms 25972 KB Output is correct
11 Correct 219 ms 24908 KB Output is correct
12 Correct 110 ms 24776 KB Output is correct
13 Correct 345 ms 25200 KB Output is correct
14 Correct 316 ms 25012 KB Output is correct
15 Correct 345 ms 25720 KB Output is correct
16 Correct 281 ms 24724 KB Output is correct
17 Correct 224 ms 24800 KB Output is correct
18 Correct 158 ms 25484 KB Output is correct
19 Correct 321 ms 24436 KB Output is correct
20 Correct 318 ms 24436 KB Output is correct
21 Correct 318 ms 25228 KB Output is correct
22 Correct 176 ms 24952 KB Output is correct
23 Correct 224 ms 25008 KB Output is correct
24 Correct 111 ms 25720 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6232 KB Output is correct
2 Correct 2 ms 6236 KB Output is correct
3 Correct 2 ms 6236 KB Output is correct
4 Correct 2 ms 6236 KB Output is correct
5 Correct 2 ms 6236 KB Output is correct
6 Correct 1 ms 6236 KB Output is correct
7 Correct 9 ms 6748 KB Output is correct
8 Correct 9 ms 6936 KB Output is correct
9 Correct 9 ms 6748 KB Output is correct
10 Correct 9 ms 6748 KB Output is correct
11 Correct 7 ms 6748 KB Output is correct
12 Correct 6 ms 6748 KB Output is correct
13 Correct 8 ms 6748 KB Output is correct
14 Correct 8 ms 6748 KB Output is correct
15 Correct 8 ms 6748 KB Output is correct
16 Correct 6 ms 6748 KB Output is correct
17 Correct 9 ms 6748 KB Output is correct
18 Correct 4 ms 6748 KB Output is correct
19 Correct 305 ms 24788 KB Output is correct
20 Correct 291 ms 25044 KB Output is correct
21 Correct 291 ms 25456 KB Output is correct
22 Correct 247 ms 24952 KB Output is correct
23 Correct 187 ms 25364 KB Output is correct
24 Correct 138 ms 25456 KB Output is correct
25 Correct 258 ms 25284 KB Output is correct
26 Correct 286 ms 25212 KB Output is correct
27 Correct 278 ms 25720 KB Output is correct
28 Correct 165 ms 25972 KB Output is correct
29 Correct 219 ms 24908 KB Output is correct
30 Correct 110 ms 24776 KB Output is correct
31 Correct 345 ms 25200 KB Output is correct
32 Correct 316 ms 25012 KB Output is correct
33 Correct 345 ms 25720 KB Output is correct
34 Correct 281 ms 24724 KB Output is correct
35 Correct 224 ms 24800 KB Output is correct
36 Correct 158 ms 25484 KB Output is correct
37 Correct 321 ms 24436 KB Output is correct
38 Correct 318 ms 24436 KB Output is correct
39 Correct 318 ms 25228 KB Output is correct
40 Correct 176 ms 24952 KB Output is correct
41 Correct 224 ms 25008 KB Output is correct
42 Correct 111 ms 25720 KB Output is correct
43 Correct 361 ms 24772 KB Output is correct
44 Correct 371 ms 25324 KB Output is correct
45 Correct 367 ms 25464 KB Output is correct
46 Correct 300 ms 25464 KB Output is correct
47 Correct 245 ms 24948 KB Output is correct
48 Correct 159 ms 25648 KB Output is correct
49 Correct 348 ms 24696 KB Output is correct
50 Correct 388 ms 25564 KB Output is correct
51 Correct 369 ms 25464 KB Output is correct
52 Correct 211 ms 24716 KB Output is correct
53 Correct 217 ms 25440 KB Output is correct