oj.uz

Submission #997938

# Submission time Handle Problem Language Result Execution time Memory
997938 2024-06-13T06:57:39 Z cnn008 Examination (JOI19_examination) C++17
0 / 100
 415 ms 47396 KB 
#include "bits/stdc++.h"
using namespace std;
 
#ifdef N_N_C
#include "debug.h"
#else
#define cebug(...) "Arya"
#endif
 
#define int 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),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),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,-y,-z,i,0});
		compress.push_back(-x);
		compress.push_back(-y);
		compress.push_back(-z);
	}
	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;
}
/**  /\_/\
*   (= ._.)
*   / >💖 \>💕
**/

Compilation message

examination.cpp:112:9: warning: "/*" within comment [-Wcomment]
  112 | /**  /\_/\
      |

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10332 KB Output is correct
3 Correct 2 ms 10332 KB Output is correct
4 Correct 2 ms 10332 KB Output is correct
5 Correct 2 ms 10332 KB Output is correct
6 Correct 2 ms 10332 KB Output is correct
7 Correct 11 ms 11140 KB Output is correct
8 Correct 11 ms 11144 KB Output is correct
9 Correct 11 ms 11140 KB Output is correct
10 Correct 10 ms 11144 KB Output is correct
11 Correct 10 ms 11140 KB Output is correct
12 Incorrect 10 ms 11144 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 47396 KB Output is correct
2 Correct 359 ms 46220 KB Output is correct
3 Correct 355 ms 44064 KB Output is correct
4 Correct 284 ms 45672 KB Output is correct
5 Correct 277 ms 45600 KB Output is correct
6 Incorrect 318 ms 43596 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 47396 KB Output is correct
2 Correct 359 ms 46220 KB Output is correct
3 Correct 355 ms 44064 KB Output is correct
4 Correct 284 ms 45672 KB Output is correct
5 Correct 277 ms 45600 KB Output is correct
6 Incorrect 318 ms 43596 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10332 KB Output is correct
3 Correct 2 ms 10332 KB Output is correct
4 Correct 2 ms 10332 KB Output is correct
5 Correct 2 ms 10332 KB Output is correct
6 Correct 2 ms 10332 KB Output is correct
7 Correct 11 ms 11140 KB Output is correct
8 Correct 11 ms 11144 KB Output is correct
9 Correct 11 ms 11140 KB Output is correct
10 Correct 10 ms 11144 KB Output is correct
11 Correct 10 ms 11140 KB Output is correct
12 Incorrect 10 ms 11144 KB Output isn't correct
13 Halted 0 ms 0 KB -