oj.uz

Submission #111164

# Submission time Handle Problem Language Result Execution time Memory
111164 2019-05-14T00:46:15 Z aleksami Examination (JOI19_examination) C++14
100 / 100
 1062 ms 50644 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);
  	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

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 19200 KB Output is correct
2 Correct 20 ms 19072 KB Output is correct
3 Correct 22 ms 19200 KB Output is correct
4 Correct 20 ms 19072 KB Output is correct
5 Correct 21 ms 19248 KB Output is correct
6 Correct 19 ms 19192 KB Output is correct
7 Correct 29 ms 20088 KB Output is correct
8 Correct 32 ms 20088 KB Output is correct
9 Correct 30 ms 20088 KB Output is correct
10 Correct 32 ms 20096 KB Output is correct
11 Correct 29 ms 20096 KB Output is correct
12 Correct 25 ms 19840 KB Output is correct
13 Correct 29 ms 19960 KB Output is correct
14 Correct 34 ms 19960 KB Output is correct
15 Correct 29 ms 20096 KB Output is correct
16 Correct 28 ms 19968 KB Output is correct
17 Correct 26 ms 20088 KB Output is correct
18 Correct 28 ms 19772 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 816 ms 50000 KB Output is correct
2 Correct 913 ms 49972 KB Output is correct
3 Correct 912 ms 49988 KB Output is correct
4 Correct 687 ms 50068 KB Output is correct
5 Correct 865 ms 45924 KB Output is correct
6 Correct 407 ms 38600 KB Output is correct
7 Correct 827 ms 50116 KB Output is correct
8 Correct 826 ms 50192 KB Output is correct
9 Correct 768 ms 49992 KB Output is correct
10 Correct 833 ms 45028 KB Output is correct
11 Correct 586 ms 49856 KB Output is correct
12 Correct 182 ms 35940 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 816 ms 50000 KB Output is correct
2 Correct 913 ms 49972 KB Output is correct
3 Correct 912 ms 49988 KB Output is correct
4 Correct 687 ms 50068 KB Output is correct
5 Correct 865 ms 45924 KB Output is correct
6 Correct 407 ms 38600 KB Output is correct
7 Correct 827 ms 50116 KB Output is correct
8 Correct 826 ms 50192 KB Output is correct
9 Correct 768 ms 49992 KB Output is correct
10 Correct 833 ms 45028 KB Output is correct
11 Correct 586 ms 49856 KB Output is correct
12 Correct 182 ms 35940 KB Output is correct
13 Correct 1043 ms 49960 KB Output is correct
14 Correct 935 ms 49976 KB Output is correct
15 Correct 832 ms 49988 KB Output is correct
16 Correct 697 ms 50024 KB Output is correct
17 Correct 815 ms 46080 KB Output is correct
18 Correct 380 ms 38440 KB Output is correct
19 Correct 930 ms 50004 KB Output is correct
20 Correct 901 ms 49996 KB Output is correct
21 Correct 1062 ms 49992 KB Output is correct
22 Correct 828 ms 45144 KB Output is correct
23 Correct 581 ms 49744 KB Output is correct
24 Correct 176 ms 36032 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 19200 KB Output is correct
2 Correct 20 ms 19072 KB Output is correct
3 Correct 22 ms 19200 KB Output is correct
4 Correct 20 ms 19072 KB Output is correct
5 Correct 21 ms 19248 KB Output is correct
6 Correct 19 ms 19192 KB Output is correct
7 Correct 29 ms 20088 KB Output is correct
8 Correct 32 ms 20088 KB Output is correct
9 Correct 30 ms 20088 KB Output is correct
10 Correct 32 ms 20096 KB Output is correct
11 Correct 29 ms 20096 KB Output is correct
12 Correct 25 ms 19840 KB Output is correct
13 Correct 29 ms 19960 KB Output is correct
14 Correct 34 ms 19960 KB Output is correct
15 Correct 29 ms 20096 KB Output is correct
16 Correct 28 ms 19968 KB Output is correct
17 Correct 26 ms 20088 KB Output is correct
18 Correct 28 ms 19772 KB Output is correct
19 Correct 816 ms 50000 KB Output is correct
20 Correct 913 ms 49972 KB Output is correct
21 Correct 912 ms 49988 KB Output is correct
22 Correct 687 ms 50068 KB Output is correct
23 Correct 865 ms 45924 KB Output is correct
24 Correct 407 ms 38600 KB Output is correct
25 Correct 827 ms 50116 KB Output is correct
26 Correct 826 ms 50192 KB Output is correct
27 Correct 768 ms 49992 KB Output is correct
28 Correct 833 ms 45028 KB Output is correct
29 Correct 586 ms 49856 KB Output is correct
30 Correct 182 ms 35940 KB Output is correct
31 Correct 1043 ms 49960 KB Output is correct
32 Correct 935 ms 49976 KB Output is correct
33 Correct 832 ms 49988 KB Output is correct
34 Correct 697 ms 50024 KB Output is correct
35 Correct 815 ms 46080 KB Output is correct
36 Correct 380 ms 38440 KB Output is correct
37 Correct 930 ms 50004 KB Output is correct
38 Correct 901 ms 49996 KB Output is correct
39 Correct 1062 ms 49992 KB Output is correct
40 Correct 828 ms 45144 KB Output is correct
41 Correct 581 ms 49744 KB Output is correct
42 Correct 176 ms 36032 KB Output is correct
43 Correct 952 ms 50512 KB Output is correct
44 Correct 867 ms 50588 KB Output is correct
45 Correct 848 ms 50600 KB Output is correct
46 Correct 742 ms 50556 KB Output is correct
47 Correct 905 ms 50436 KB Output is correct
48 Correct 356 ms 38244 KB Output is correct
49 Correct 900 ms 50644 KB Output is correct
50 Correct 815 ms 50460 KB Output is correct
51 Correct 840 ms 50464 KB Output is correct
52 Correct 912 ms 50344 KB Output is correct
53 Correct 585 ms 50332 KB Output is correct