Submission #111142

#	Time	Username	Problem	Language	Result	Execution time	Memory
111142		aleksami	Examination (JOI19_examination)	C++14	22 / 100	3076 ms	636432 KiB

examination

#include <bits/stdc++.h>

using namespace std;
#define MAXN 100005
#define MAXBIT 31
typedef pair<int,int> pii;

struct node {node* nula;node* kec;int cnt;};
void update(node* root,int val)
{
	node* now = root;
	root->cnt++;
	for(int i = MAXBIT-1; i >= 0; i--)
	{
		if(val & (1<<i))
		{
			if(now->kec == NULL)now->kec=new node();
			now=now->kec;
		}
		else 
		{
			if(now->nula == NULL)now->nula=new node();
			now=now->nula;
		}
		now->cnt++;
	}
}
int query(node* root,int val)
{
	int ret=0;
	node* now = root;
	if(val==0)return root->cnt;
	for(int i = MAXBIT-1; i >= 0; i--)
	{
		if(val & (1<<i))
		{
			if(now->kec == NULL)return ret;
			now=now->kec;
		}
		else 
		{
			if(now->kec != NULL)ret += now->kec->cnt;
			if(now->nula == NULL)return ret;
			now=now->nula;
		}
	}
	ret += now->cnt;
	return ret;
}

node* tree[4*MAXN];

void update(int nod,int left,int right,int idx,int val)
{
	if(left <= idx && idx <= right)
	{
		if(tree[nod]==NULL)tree[nod]=new node();
		//if(val==1)cout << nod << " " << left << " " << right << " " << idx << "\n";
		update(tree[nod],val);
	}
	else return;
	if(left==right)return ;
	int mid=(left+right)>>1;
	update(nod*2,left,mid,idx,val);
	update(nod*2+1,mid+1,right,idx,val);
}
int query(int nod,int left,int right,int l,int r,int x)
{
	if(left > right || left > r || l > right || l > r)return 0;
	if(left >= l && right <= r)
	{
		if(tree[nod]==NULL)return 0;
		if(x==0)return tree[nod]->cnt;
		return query(tree[nod],x);
	}
	int mid=(left+right)>>1;
	return query(nod*2,left,mid,l,r,x)+query(nod*2+1,mid+1,right,l,r,x);
}

vector <int> order_a;
vector <int> order_b;
map <int,int> mp;
int ans[MAXN];
int s[MAXN];
int t[MAXN];
bool cmp(int x,int y){return s[x] < s[y];}
bool cmp0(int x,int y){return t[x] < t[y];}

struct upit
{
	int x,y,z,id;
};
bool cmp2(upit x,upit y)
{
	return x.x<y.x;
}
vector <upit> queries;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,q;
	cin >> n >> q;
	for(int i = 1; i <= n; i++)
	{
		cin >> s[i] >> t[i];
		order_a.push_back(i);
		order_b.push_back(i);
	}
	sort(order_a.begin(),order_a.end(),cmp);
	sort(order_b.begin(),order_b.end(),cmp0);
	for(int i = 0; i < order_b.size(); i++)mp[order_b[i]]=i+1;
	for(int i = 0; i < q; i++)
	{
		int x,y,z;
		cin >> x >> y >> z;
		upit u;
		u.x=x;u.y=y;u.z=z;u.id=i;
		queries.push_back(u);
	}
	sort(queries.begin(),queries.end(),cmp2);
	int now=n;
	for(int i = q-1; i >= 0; i--)
	{
		while(now-1 >= 0 && s[order_a[now-1]] >= queries[i].x)
		{
			now--;
			update(1,1,n,mp[order_a[now]],s[order_a[now]]+t[order_a[now]]);
		}
		int lo=0,hi=n-1,mid=lo+hi>>1,r=n;
		while(lo<=hi)
		{
			if(t[order_b[mid]]>=queries[i].y)
			{
				r=mid;
				hi=mid-1;
			}
			else lo=mid+1;
			mid=lo+hi>>1;
		}
		r++;
		if(r>n)continue;
		ans[queries[i].id]=query(1,1,n,r,n,queries[i].z);
	}
	for(int i = 0; i < q; i++)
	{
		cout << ans[i] << " ";
	}
	return 0;
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:114:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < order_b.size(); i++)mp[order_b[i]]=i+1;
                 ~~^~~~~~~~~~~~~~~~
examination.cpp:132:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int lo=0,hi=n-1,mid=lo+hi>>1,r=n;
                       ~~^~~
examination.cpp:141:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid=lo+hi>>1;
        ~~^~~

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