oj.uz

답안 #997936

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
997936 2024-06-13T06:56:38 Z cnn008 Examination (JOI19_examination) C++17
0 / 100
 327 ms 25680 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),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,i,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,n+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=n+1; i<=n+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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6236 KB Output is correct
2 Correct 2 ms 6216 KB Output is correct
3 Correct 2 ms 6236 KB Output is correct
4 Correct 1 ms 6424 KB Output is correct
5 Correct 1 ms 6236 KB Output is correct
6 Correct 1 ms 6236 KB Output is correct
7 Correct 9 ms 6756 KB Output is correct
8 Correct 9 ms 6876 KB Output is correct
9 Correct 9 ms 6748 KB Output is correct
10 Correct 9 ms 6744 KB Output is correct
11 Correct 8 ms 6800 KB Output is correct
12 Incorrect 7 ms 6748 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 282 ms 24836 KB Output is correct
2 Correct 298 ms 24732 KB Output is correct
3 Correct 327 ms 25680 KB Output is correct
4 Correct 241 ms 25212 KB Output is correct
5 Correct 241 ms 25356 KB Output is correct
6 Incorrect 233 ms 25464 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 282 ms 24836 KB Output is correct
2 Correct 298 ms 24732 KB Output is correct
3 Correct 327 ms 25680 KB Output is correct
4 Correct 241 ms 25212 KB Output is correct
5 Correct 241 ms 25356 KB Output is correct
6 Incorrect 233 ms 25464 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6236 KB Output is correct
2 Correct 2 ms 6216 KB Output is correct
3 Correct 2 ms 6236 KB Output is correct
4 Correct 1 ms 6424 KB Output is correct
5 Correct 1 ms 6236 KB Output is correct
6 Correct 1 ms 6236 KB Output is correct
7 Correct 9 ms 6756 KB Output is correct
8 Correct 9 ms 6876 KB Output is correct
9 Correct 9 ms 6748 KB Output is correct
10 Correct 9 ms 6744 KB Output is correct
11 Correct 8 ms 6800 KB Output is correct
12 Incorrect 7 ms 6748 KB Output isn't correct
13 Halted 0 ms 0 KB -