oj.uz

Submission #111144

# Submission time Handle Problem Language Result Execution time Memory
111144 2019-05-13T22:34:45 Z aleksami Examination (JOI19_examination) C++14
22 / 100
 3000 ms 634204 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 62 ms 31080 KB Output is correct
8 Correct 66 ms 31100 KB Output is correct
9 Correct 70 ms 31096 KB Output is correct
10 Correct 68 ms 30816 KB Output is correct
11 Correct 67 ms 26100 KB Output is correct
12 Correct 24 ms 7336 KB Output is correct
13 Correct 61 ms 31224 KB Output is correct
14 Correct 62 ms 31096 KB Output is correct
15 Correct 62 ms 31096 KB Output is correct
16 Correct 57 ms 26232 KB Output is correct
17 Correct 58 ms 30840 KB Output is correct
18 Correct 17 ms 6784 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2634 ms 634012 KB Output is correct
2 Correct 2775 ms 633620 KB Output is correct
3 Correct 2718 ms 633972 KB Output is correct
4 Correct 2437 ms 627500 KB Output is correct
5 Correct 1913 ms 297636 KB Output is correct
6 Correct 1206 ms 234112 KB Output is correct
7 Correct 2931 ms 634204 KB Output is correct
8 Correct 2911 ms 633864 KB Output is correct
9 Correct 2629 ms 633784 KB Output is correct
10 Correct 1637 ms 288228 KB Output is correct
11 Correct 2197 ms 627556 KB Output is correct
12 Correct 528 ms 211312 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2634 ms 634012 KB Output is correct
2 Correct 2775 ms 633620 KB Output is correct
3 Correct 2718 ms 633972 KB Output is correct
4 Correct 2437 ms 627500 KB Output is correct
5 Correct 1913 ms 297636 KB Output is correct
6 Correct 1206 ms 234112 KB Output is correct
7 Correct 2931 ms 634204 KB Output is correct
8 Correct 2911 ms 633864 KB Output is correct
9 Correct 2629 ms 633784 KB Output is correct
10 Correct 1637 ms 288228 KB Output is correct
11 Correct 2197 ms 627556 KB Output is correct
12 Correct 528 ms 211312 KB Output is correct
13 Execution timed out 3075 ms 606444 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 62 ms 31080 KB Output is correct
8 Correct 66 ms 31100 KB Output is correct
9 Correct 70 ms 31096 KB Output is correct
10 Correct 68 ms 30816 KB Output is correct
11 Correct 67 ms 26100 KB Output is correct
12 Correct 24 ms 7336 KB Output is correct
13 Correct 61 ms 31224 KB Output is correct
14 Correct 62 ms 31096 KB Output is correct
15 Correct 62 ms 31096 KB Output is correct
16 Correct 57 ms 26232 KB Output is correct
17 Correct 58 ms 30840 KB Output is correct
18 Correct 17 ms 6784 KB Output is correct
19 Correct 2634 ms 634012 KB Output is correct
20 Correct 2775 ms 633620 KB Output is correct
21 Correct 2718 ms 633972 KB Output is correct
22 Correct 2437 ms 627500 KB Output is correct
23 Correct 1913 ms 297636 KB Output is correct
24 Correct 1206 ms 234112 KB Output is correct
25 Correct 2931 ms 634204 KB Output is correct
26 Correct 2911 ms 633864 KB Output is correct
27 Correct 2629 ms 633784 KB Output is correct
28 Correct 1637 ms 288228 KB Output is correct
29 Correct 2197 ms 627556 KB Output is correct
30 Correct 528 ms 211312 KB Output is correct
31 Execution timed out 3075 ms 606444 KB Time limit exceeded
32 Halted 0 ms 0 KB -