Submission #111164

#	Time	Username	Problem	Language	Result	Execution time	Memory
111164		aleksami	Examination (JOI19_examination)	C++14	100 / 100	1062 ms	50644 KiB

examination

#include <bits/stdc++.h>

using namespace std;
#define MAXN 100005
int s[MAXN];
int t[MAXN];
int pos[MAXN];
vector <int> order_a;
vector <int> order_b;

bool cmpb(int x,int y){return t[x]<t[y];}
bool cmpa(int x,int y){return s[x]<s[y];}

vector <int> mst[4*MAXN];

vector <int> merge(vector <int> a,vector <int> b)
{
	vector <int> ret;
	int i = 0;
	int j = 0;
	while(i < a.size() && j < b.size())
	{
		ret.push_back(min(a[i],b[j]));
		if(a[i]==min(a[i],b[j]))i++;
		else j++;
	}
	while(i < a.size())ret.push_back(a[i]),i++;
	while(j < b.size())ret.push_back(b[j]),j++;
	return ret;
}
vector <int> tree[4*MAXN];

void build(int node,int left,int right)
{
	if(left==right)
	{
		mst[node].push_back(s[order_b[left]]+t[order_b[left]]);
		tree[node].push_back(0);
		tree[node].push_back(0);
		return ;
	}
	if(left > right)return ;
	int mid=left+right>>1;
	build(node*2,left,mid);
	build(node*2+1,mid+1,right);
	mst[node]=merge(mst[node*2],mst[node*2+1]);
	mst[node].erase(unique(mst[node].begin(),mst[node].end()),mst[node].end());
	while(tree[node].size()!=mst[node].size())tree[node].push_back(0);
	tree[node].push_back(0);//fake
}

void update(int node,int idx,int val)
{
	while(idx > 0)
	{
		tree[node][idx]+=val;
		idx-=idx&(-idx);
	}
}
int query(int node,int idx)
{
	int ret=0;
	while(idx < tree[node].size())
	{
		ret += tree[node][idx];
		idx += idx&(-idx);
	}
	return ret;
}

void update(int node,int left,int right,int idx,int val)
{
	if(left <= idx && idx <= right)
	{
		int pos = lower_bound(mst[node].begin(),mst[node].end(),val)-mst[node].begin();
		update(node,pos+1,1);
	}
	else return;
	if(left==right)return ;
	int mid=left+right>>1;
	update(node*2,left,mid,idx,val);
	update(node*2+1,mid+1,right,idx,val);
}
int query(int node,int left,int right,int l,int r,int val)
{
	if(left > right || left > r || l > right || l > r)return 0;
	if(left >= l && right <= r)
	{
		int pos = lower_bound(mst[node].begin(),mst[node].end(),val)-mst[node].begin();
		return query(node,pos+1);
	}
	int mid=left+right>>1;
	return query(node*2,left,mid,l,r,val)+query(node*2+1,mid+1,right,l,r,val);
}

struct upit
{
	int x,y,z,id;
};

vector <upit> queries;
int ans[MAXN];

bool cmpq(upit x,upit y){return x.x<y.x;}

int main()
{
	ios_base::sync_with_stdio(false);
  	cin.tie(NULL);
  	cout.tie(NULL);
	int n,q;
	cin >> n >> q;
	for(int i = 0; i < n; i++)
	{
		cin >> s[i] >> t[i];
		order_b.push_back(i);
		order_a.push_back(i);
	}
	sort(order_a.begin(),order_a.end(),cmpa);
	sort(order_b.begin(),order_b.end(),cmpb);
	for(int i = 0; i < n; i++)pos[order_b[i]]=i;
	build(1,0,n-1);
	for(int i = 0; i < q; i++)
	{
		upit z;
		cin >> z.x >> z.y >> z.z;
		z.id=i;
		queries.push_back(z);
	}
	sort(queries.begin(),queries.end(),cmpq);
	int now=n;
	for(int i = q-1; i >= 0; i--)
	{
		while(now-1 >= 0 && s[order_a[now-1]]>=queries[i].x)
		{
			now--;
			//cout << "ADDING " << order_a[now] << " " << pos[order_a[now]] << " " << s[order_a[now]]+t[order_a[now]] << "\n";
			update(1,0,n-1,pos[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;
		}
		ans[queries[i].id]=query(1,0,n-1,r,n-1,queries[i].z); 
	}
	for(int i = 0; i < q; i++)cout << ans[i] << " "; 
	return 0;
}

Compilation message (stderr)

examination.cpp: In function 'std::vector<int> merge(std::vector<int>, std::vector<int>)':
examination.cpp:21:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i < a.size() && j < b.size())
        ~~^~~~~~~~~~
examination.cpp:21:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i < a.size() && j < b.size())
                        ~~^~~~~~~~~~
examination.cpp:27:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i < a.size())ret.push_back(a[i]),i++;
        ~~^~~~~~~~~~
examination.cpp:28:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(j < b.size())ret.push_back(b[j]),j++;
        ~~^~~~~~~~~~
examination.cpp: In function 'void build(int, int, int)':
examination.cpp:43:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=left+right>>1;
          ~~~~^~~~~~
examination.cpp: In function 'int query(int, int)':
examination.cpp:63:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(idx < tree[node].size())
        ~~~~^~~~~~~~~~~~~~~~~~~
examination.cpp: In function 'void update(int, int, int, int, int)':
examination.cpp:80:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=left+right>>1;
          ~~~~^~~~~~
examination.cpp: In function 'int query(int, int, int, int, int, int)':
examination.cpp:92:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=left+right>>1;
          ~~~~^~~~~~
examination.cpp: In function 'int main()':
examination.cpp:140:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int lo=0,hi=n-1,mid=lo+hi>>1,r=n;
                       ~~^~~
examination.cpp:149:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid=lo+hi>>1;
        ~~^~~

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