oj.uz

Submission #111163

# Submission time Handle Problem Language Result Execution time Memory
111163 2019-05-14T00:43:17 Z aleksami Examination (JOI19_examination) C++14
100 / 100
 1063 ms 55456 KB 
#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);
	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

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:138:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int lo=0,hi=n-1,mid=lo+hi>>1,r=n;
                       ~~^~~
examination.cpp:147:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid=lo+hi>>1;
        ~~^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19200 KB Output is correct
2 Correct 20 ms 19200 KB Output is correct
3 Correct 20 ms 19072 KB Output is correct
4 Correct 19 ms 19200 KB Output is correct
5 Correct 18 ms 19072 KB Output is correct
6 Correct 19 ms 19200 KB Output is correct
7 Correct 30 ms 20088 KB Output is correct
8 Correct 29 ms 19992 KB Output is correct
9 Correct 32 ms 20096 KB Output is correct
10 Correct 33 ms 19968 KB Output is correct
11 Correct 28 ms 19968 KB Output is correct
12 Correct 26 ms 19840 KB Output is correct
13 Correct 31 ms 20088 KB Output is correct
14 Correct 28 ms 19968 KB Output is correct
15 Correct 28 ms 20096 KB Output is correct
16 Correct 28 ms 19960 KB Output is correct
17 Correct 28 ms 20092 KB Output is correct
18 Correct 24 ms 19840 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 812 ms 50024 KB Output is correct
2 Correct 814 ms 49988 KB Output is correct
3 Correct 880 ms 50112 KB Output is correct
4 Correct 671 ms 50016 KB Output is correct
5 Correct 832 ms 46000 KB Output is correct
6 Correct 377 ms 38496 KB Output is correct
7 Correct 793 ms 50208 KB Output is correct
8 Correct 830 ms 50116 KB Output is correct
9 Correct 724 ms 50112 KB Output is correct
10 Correct 735 ms 45168 KB Output is correct
11 Correct 546 ms 49868 KB Output is correct
12 Correct 174 ms 35940 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 812 ms 50024 KB Output is correct
2 Correct 814 ms 49988 KB Output is correct
3 Correct 880 ms 50112 KB Output is correct
4 Correct 671 ms 50016 KB Output is correct
5 Correct 832 ms 46000 KB Output is correct
6 Correct 377 ms 38496 KB Output is correct
7 Correct 793 ms 50208 KB Output is correct
8 Correct 830 ms 50116 KB Output is correct
9 Correct 724 ms 50112 KB Output is correct
10 Correct 735 ms 45168 KB Output is correct
11 Correct 546 ms 49868 KB Output is correct
12 Correct 174 ms 35940 KB Output is correct
13 Correct 939 ms 49920 KB Output is correct
14 Correct 825 ms 50072 KB Output is correct
15 Correct 794 ms 50024 KB Output is correct
16 Correct 737 ms 49916 KB Output is correct
17 Correct 811 ms 46056 KB Output is correct
18 Correct 374 ms 38540 KB Output is correct
19 Correct 977 ms 50112 KB Output is correct
20 Correct 903 ms 52804 KB Output is correct
21 Correct 932 ms 53140 KB Output is correct
22 Correct 829 ms 46944 KB Output is correct
23 Correct 689 ms 51536 KB Output is correct
24 Correct 196 ms 36836 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19200 KB Output is correct
2 Correct 20 ms 19200 KB Output is correct
3 Correct 20 ms 19072 KB Output is correct
4 Correct 19 ms 19200 KB Output is correct
5 Correct 18 ms 19072 KB Output is correct
6 Correct 19 ms 19200 KB Output is correct
7 Correct 30 ms 20088 KB Output is correct
8 Correct 29 ms 19992 KB Output is correct
9 Correct 32 ms 20096 KB Output is correct
10 Correct 33 ms 19968 KB Output is correct
11 Correct 28 ms 19968 KB Output is correct
12 Correct 26 ms 19840 KB Output is correct
13 Correct 31 ms 20088 KB Output is correct
14 Correct 28 ms 19968 KB Output is correct
15 Correct 28 ms 20096 KB Output is correct
16 Correct 28 ms 19960 KB Output is correct
17 Correct 28 ms 20092 KB Output is correct
18 Correct 24 ms 19840 KB Output is correct
19 Correct 812 ms 50024 KB Output is correct
20 Correct 814 ms 49988 KB Output is correct
21 Correct 880 ms 50112 KB Output is correct
22 Correct 671 ms 50016 KB Output is correct
23 Correct 832 ms 46000 KB Output is correct
24 Correct 377 ms 38496 KB Output is correct
25 Correct 793 ms 50208 KB Output is correct
26 Correct 830 ms 50116 KB Output is correct
27 Correct 724 ms 50112 KB Output is correct
28 Correct 735 ms 45168 KB Output is correct
29 Correct 546 ms 49868 KB Output is correct
30 Correct 174 ms 35940 KB Output is correct
31 Correct 939 ms 49920 KB Output is correct
32 Correct 825 ms 50072 KB Output is correct
33 Correct 794 ms 50024 KB Output is correct
34 Correct 737 ms 49916 KB Output is correct
35 Correct 811 ms 46056 KB Output is correct
36 Correct 374 ms 38540 KB Output is correct
37 Correct 977 ms 50112 KB Output is correct
38 Correct 903 ms 52804 KB Output is correct
39 Correct 932 ms 53140 KB Output is correct
40 Correct 829 ms 46944 KB Output is correct
41 Correct 689 ms 51536 KB Output is correct
42 Correct 196 ms 36836 KB Output is correct
43 Correct 1063 ms 55376 KB Output is correct
44 Correct 1000 ms 55456 KB Output is correct
45 Correct 991 ms 55244 KB Output is correct
46 Correct 792 ms 53664 KB Output is correct
47 Correct 932 ms 53816 KB Output is correct
48 Correct 419 ms 39260 KB Output is correct
49 Correct 895 ms 55328 KB Output is correct
50 Correct 983 ms 55244 KB Output is correct
51 Correct 844 ms 55048 KB Output is correct
52 Correct 1012 ms 53516 KB Output is correct
53 Correct 641 ms 52864 KB Output is correct