제출 #402906

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
402906		keta_tsimakuridze	Examination (JOI19_examination)	C++14	100 / 100	2420 ms	213596 KiB

examination

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>  
#include <functional>
#define f first
#define s second
#define int long long
#define pii pair<int,int> 
using namespace __gnu_pbds; 
using namespace std;
const int N=2e5+5,mod=1e9+7;
int t,n,Q,ans[N];
pair<int,int>p[N];
vector<int> x;
pair<pair<int,int>,pair<int,int> >q[N];
map<int,int>ind;

 
typedef tree<pii, null_type, less<pii>, rb_tree_tag,  
            tree_order_statistics_node_update>  
    ordered_set;  
  ordered_set s[4*N];

void update(int u,int ind,int l,int r,int val,int idx){
	if(l>ind || r<ind) return;
	if(l==r) {
		s[u].insert({val,idx});
		return;
	}
	s[u].insert({val,idx});
	int mid=(l+r)/2;
	update(2*u,ind,l,mid,val,idx);
	update(2*u+1,ind,mid+1,r,val,idx);
}
int getans(int u,int start,int end,int l,int r,int val){
	if(l>end || r<start) return 0;
	if(start<=l&& r<=end) {
		return s[u].size() - s[u].order_of_key({val,0});
	}
	int mid=(l+r)/2;
	return getans(2*u,start,end,l,mid,val)+getans(2*u+1,start,end,mid+1,r,val);
}
 main(){
 	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	// t=1;
	cin>>n>>Q;
	for(int i=1;i<=n;i++){
		cin>>p[i].f>>p[i].s;
		x.push_back(p[i].s);
	}
	for(int i=1;i<=Q;i++){
		cin>>q[i].f.f>>q[i].f.s>>q[i].s.f;
		q[i].s.s=i;
		x.push_back(q[i].f.s);
	}
	sort(x.begin(),x.end());
	int idx=0;
	for(int i=0;i<x.size();i++){
		if(!i || x[i]!=x[i-1]) idx++;
		ind[x[i]] = idx;
	}
	sort(q+1,q+Q+1);
	sort(p+1,p+n+1);
	reverse(q+1,q+Q+1);
	reverse(p+1,p+n+1);
	int L=0;
	for(int i=1;i<=Q;i++){
		while(L<n && p[L+1].f>=q[i].f.f) L++,update(1,ind[p[L].s],1,idx,p[L].f+p[L].s,L);
		ans[q[i].s.s] = getans(1,ind[q[i].f.s],idx,1,idx,q[i].s.f);
	}
	for(int i=1;i<=Q;i++) cout<<ans[i]<<" ";
}

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

examination.cpp:43:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   43 |  main(){
      |  ^~~~
examination.cpp: In function 'int main()':
examination.cpp:58:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(int i=0;i<x.size();i++){
      |              ~^~~~~~~~~

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