oj.uz

답안 #997957

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
997957 2024-06-13T07:19:03 Z cnn008 Examination (JOI19_examination) C++17
20 / 100
 340 ms 27528 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,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;
}
/**  /\_/\
*   (= ._.)
*   / >💖 \>💕
**/

Compilation message

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

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6232 KB Output is correct
2 Correct 1 ms 6236 KB Output is correct
3 Correct 1 ms 6236 KB Output is correct
4 Correct 1 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 6716 KB Output is correct
8 Correct 9 ms 6744 KB Output is correct
9 Correct 9 ms 6748 KB Output is correct
10 Correct 8 ms 6748 KB Output is correct
11 Correct 7 ms 6848 KB Output is correct
12 Incorrect 6 ms 6912 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 290 ms 24696 KB Output is correct
2 Correct 293 ms 26228 KB Output is correct
3 Correct 307 ms 27004 KB Output is correct
4 Correct 256 ms 26184 KB Output is correct
5 Correct 202 ms 26488 KB Output is correct
6 Correct 159 ms 25800 KB Output is correct
7 Correct 275 ms 26128 KB Output is correct
8 Correct 283 ms 26784 KB Output is correct
9 Correct 269 ms 26020 KB Output is correct
10 Correct 182 ms 26232 KB Output is correct
11 Correct 231 ms 26052 KB Output is correct
12 Correct 151 ms 25940 KB Output is correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 290 ms 24696 KB Output is correct
2 Correct 293 ms 26228 KB Output is correct
3 Correct 307 ms 27004 KB Output is correct
4 Correct 256 ms 26184 KB Output is correct
5 Correct 202 ms 26488 KB Output is correct
6 Correct 159 ms 25800 KB Output is correct
7 Correct 275 ms 26128 KB Output is correct
8 Correct 283 ms 26784 KB Output is correct
9 Correct 269 ms 26020 KB Output is correct
10 Correct 182 ms 26232 KB Output is correct
11 Correct 231 ms 26052 KB Output is correct
12 Correct 151 ms 25940 KB Output is correct
13 Incorrect 340 ms 27528 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6232 KB Output is correct
2 Correct 1 ms 6236 KB Output is correct
3 Correct 1 ms 6236 KB Output is correct
4 Correct 1 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 6716 KB Output is correct
8 Correct 9 ms 6744 KB Output is correct
9 Correct 9 ms 6748 KB Output is correct
10 Correct 8 ms 6748 KB Output is correct
11 Correct 7 ms 6848 KB Output is correct
12 Incorrect 6 ms 6912 KB Output isn't correct
13 Halted 0 ms 0 KB -