제출 #613212

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
613212		juggernaut	Examination (JOI19_examination)	C++14	100 / 100	1697 ms	206328 KiB

examination

#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef juggernaut
    #define printl(args...) printf(args)
#else
    #define printl(args...) 0
#endif
vector<array<int,4>>vec;
int ans[100005];
const int N=2e5;
struct SegmentTree{
	struct node{
		int lson,rson,sum;
		node(){
			lson=rson=sum=0;
		}
	};
	vector<node>tree={node(),node()};
	int timer=2;
	void update(int pos,int v=1,int l=1,int r=N){
		tree[v].sum++;
		if(l==r)return;
		int mid=(l+r)>>1;
		if(pos<=mid){
			if(!tree[v].lson){
				tree.push_back(node());
				tree[v].lson=timer++;
			}
			update(pos,tree[v].lson,l,mid);
		}else{
			if(!tree[v].rson){
				tree.push_back(node());
				tree[v].rson=timer++;
			}
			update(pos,tree[v].rson,mid+1,r);
		}
	}
	int get(int ql,int qr,int v=1,int l=1,int r=N){
		if(r<ql||qr<l||!v)return 0;
		if(ql<=l&&r<=qr)return tree[v].sum;
		int mid=(l+r)>>1;
		return get(ql,qr,tree[v].lson,l,mid)+get(ql,qr,tree[v].rson,mid+1,r);
	}
}fen[200005];
void add(int x,int y){
	x=N-x+1;
	for(;x<=N;x+=(x&-x))fen[x].update(y);
}
int sum(int x,int y){
	int ans=0;
	for(;x;x-=(x&-x))ans+=fen[x].get(y,N);
	return ans;
}
int gt(int x,int y){
	return sum(N-x+1,y);
}
int main(){
	int n,q;
	scanf("%d%d",&n,&q);
	vector<int>X,Y;
	for(int i=1;i<=n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		X.push_back(x);
		Y.push_back(y);
		vec.push_back({-x-y,0,x,y});
	}
	for(int i=1;i<=q;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		X.push_back(x);
		Y.push_back(y);
		vec.push_back({-z,i,x,y});
	}
	sort(vec.begin(),vec.end());
	sort(X.begin(),X.end());
	X.erase(unique(X.begin(),X.end()),X.end());
	sort(Y.begin(),Y.end());
	Y.erase(unique(Y.begin(),Y.end()),Y.end());
	map<int,int>idx,idy;
	int timer=1;
	for(int to:X)idx[to]=timer++;
	timer=1;
	for(int to:Y)idy[to]=timer++;
	for(auto query:vec){
		query[2]=idx[query[2]];
		query[3]=idy[query[3]];
		if(!query[1])add(query[2],query[3]);
		else ans[query[1]]=gt(query[2],query[3]);
	}
	for(int i=1;i<=q;i++)printf("%d\n",ans[i]);
}

컴파일 시 표준 에러 (stderr) 메시지

examination.cpp: In function 'int main()':
examination.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |  scanf("%d%d",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~
examination.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |   scanf("%d%d",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~
examination.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |   scanf("%d%d%d",&x,&y,&z);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57