oj.uz

Submission #111147

# Submission time Handle Problem Language Result Execution time Memory
111147 2019-05-13T22:40:38 Z aleksami Examination (JOI19_examination) C++14
22 / 100
 3000 ms 632560 KB 
#include <bits/stdc++.h>

using namespace std;
#define MAXN 100001
#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;
	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;
int mp[MAXN];
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:113: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:131:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int lo=0,hi=n-1,mid=lo+hi>>1,r=n;
                       ~~^~~
examination.cpp:140: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 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 70 ms 30968 KB Output is correct
8 Correct 71 ms 31020 KB Output is correct
9 Correct 72 ms 30984 KB Output is correct
10 Correct 61 ms 30712 KB Output is correct
11 Correct 71 ms 25980 KB Output is correct
12 Correct 25 ms 7296 KB Output is correct
13 Correct 70 ms 31044 KB Output is correct
14 Correct 67 ms 30936 KB Output is correct
15 Correct 83 ms 30980 KB Output is correct
16 Correct 59 ms 26104 KB Output is correct
17 Correct 62 ms 30712 KB Output is correct
18 Correct 17 ms 6524 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2534 ms 629532 KB Output is correct
2 Correct 2603 ms 629376 KB Output is correct
3 Correct 2472 ms 629620 KB Output is correct
4 Correct 2063 ms 623540 KB Output is correct
5 Correct 1605 ms 293340 KB Output is correct
6 Correct 1098 ms 229852 KB Output is correct
7 Correct 2631 ms 629656 KB Output is correct
8 Correct 2744 ms 629604 KB Output is correct
9 Correct 2540 ms 629620 KB Output is correct
10 Correct 1478 ms 283876 KB Output is correct
11 Correct 2160 ms 623344 KB Output is correct
12 Correct 557 ms 206940 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2534 ms 629532 KB Output is correct
2 Correct 2603 ms 629376 KB Output is correct
3 Correct 2472 ms 629620 KB Output is correct
4 Correct 2063 ms 623540 KB Output is correct
5 Correct 1605 ms 293340 KB Output is correct
6 Correct 1098 ms 229852 KB Output is correct
7 Correct 2631 ms 629656 KB Output is correct
8 Correct 2744 ms 629604 KB Output is correct
9 Correct 2540 ms 629620 KB Output is correct
10 Correct 1478 ms 283876 KB Output is correct
11 Correct 2160 ms 623344 KB Output is correct
12 Correct 557 ms 206940 KB Output is correct
13 Correct 2941 ms 629504 KB Output is correct
14 Correct 2865 ms 632540 KB Output is correct
15 Correct 2629 ms 632116 KB Output is correct
16 Correct 2721 ms 625520 KB Output is correct
17 Correct 1874 ms 295596 KB Output is correct
18 Correct 1112 ms 230916 KB Output is correct
19 Execution timed out 3025 ms 632560 KB Time limit exceeded
20 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 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 70 ms 30968 KB Output is correct
8 Correct 71 ms 31020 KB Output is correct
9 Correct 72 ms 30984 KB Output is correct
10 Correct 61 ms 30712 KB Output is correct
11 Correct 71 ms 25980 KB Output is correct
12 Correct 25 ms 7296 KB Output is correct
13 Correct 70 ms 31044 KB Output is correct
14 Correct 67 ms 30936 KB Output is correct
15 Correct 83 ms 30980 KB Output is correct
16 Correct 59 ms 26104 KB Output is correct
17 Correct 62 ms 30712 KB Output is correct
18 Correct 17 ms 6524 KB Output is correct
19 Correct 2534 ms 629532 KB Output is correct
20 Correct 2603 ms 629376 KB Output is correct
21 Correct 2472 ms 629620 KB Output is correct
22 Correct 2063 ms 623540 KB Output is correct
23 Correct 1605 ms 293340 KB Output is correct
24 Correct 1098 ms 229852 KB Output is correct
25 Correct 2631 ms 629656 KB Output is correct
26 Correct 2744 ms 629604 KB Output is correct
27 Correct 2540 ms 629620 KB Output is correct
28 Correct 1478 ms 283876 KB Output is correct
29 Correct 2160 ms 623344 KB Output is correct
30 Correct 557 ms 206940 KB Output is correct
31 Correct 2941 ms 629504 KB Output is correct
32 Correct 2865 ms 632540 KB Output is correct
33 Correct 2629 ms 632116 KB Output is correct
34 Correct 2721 ms 625520 KB Output is correct
35 Correct 1874 ms 295596 KB Output is correct
36 Correct 1112 ms 230916 KB Output is correct
37 Execution timed out 3025 ms 632560 KB Time limit exceeded
38 Halted 0 ms 0 KB -