oj.uz

Submission #393170

# Submission time Handle Problem Language Result Execution time Memory
393170 2021-04-22T21:51:06 Z ElyesChaabouni Index (COCI21_index) C++14
60 / 110
 2500 ms 74580 KB 
#include<bits/stdc++.h>
#define eps 1e-9
#define MOD1 998244353
#define MOD2 1000000007
#define INV_2 499122177
#define INF 1000000000
#define PI 3.14159265358979323846

using namespace std;

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n, q;
	cin >> n >> q;
	int a[n];
	for(int i = 0; i < n; i++)
		cin >> a[i];
	vector<pair<pair<int, int> , int> >v(q);
	for(int i = 0; i < q; i++)
	{
		cin >> v[i].first.second >> v[i].first.first;
		v[i].first.second--;
		v[i].first.first--;
		v[i].second=i;
	}
	sort(v.begin(), v.end());
	int p=1;
	while(p <= 200001)
		p*=2;
	vector<pair<int, int> >tree[2*p+1];
	for(int i = 0; i < 2*p+1; i++)
		tree[i].push_back(make_pair(-1, 0));
	int idx=0;
	int ans[q];
	int k=0;
	for(int i = 0; i < n; i++)
	{
		int x, y;
		//cout << "\n--------------\n";
		//cout << i << '\n';
		x=p+a[i];
		while(x >= 1)
		{
		    int nb=tree[x].back().second+1;
			tree[x].push_back(make_pair(i, nb));
			x/=2;
		}
		while(idx < q && v[idx].first.first == i)
		{
			int l = 0, r = 200000;
			while(l < r)
			{
				int med=(l+r)/2+1;
				int cu=0;
				x=p+med;
				y=p+200000;
				while(x <= y)
				{
					if(x%2==1)
					{
					    int xx = ((lower_bound(tree[x].begin(), tree[x].end(), make_pair(v[idx].first.second, 0))-tree[x].begin()));
						cu+=tree[x].back().second-tree[x][xx-1].second;
						x++;
					}
					if(y%2==0)
					{
					    int yy=((lower_bound(tree[y].begin(), tree[y].end(), make_pair(v[idx].first.second, 0))-tree[y].begin()));
						cu+=tree[y].back().second-tree[y][yy-1].second;
						y--;
					}
					x/=2;
					y/=2;
				}
				if(cu >= med)
					l=med;
				else
					r=med-1;
				/*k++;
				if(k > 1000)
				    return 0;*/
				//cout << v[idx].first.second << ' ' << v[idx].first.first << ' ' << med << ' ' << cu << '\n';
			}
			if(l==0)
			    l=-1;
			ans[v[idx].second]=l;
			idx++;
		}
	}
	for(int i = 0; i < q; i++)
		cout << ans[i] << '\n';
}	
//size

Compilation message

index.cpp: In function 'int main()':
index.cpp:36:6: warning: unused variable 'k' [-Wunused-variable]
   36 |  int k=0;
      |      ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 29340 KB Output is correct
2 Correct 42 ms 29184 KB Output is correct
3 Correct 42 ms 29220 KB Output is correct
4 Correct 42 ms 29124 KB Output is correct
5 Correct 44 ms 29232 KB Output is correct
6 Correct 42 ms 29240 KB Output is correct
7 Correct 44 ms 29236 KB Output is correct
8 Correct 42 ms 29204 KB Output is correct
9 Correct 42 ms 29252 KB Output is correct
10 Correct 43 ms 29256 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 29340 KB Output is correct
2 Correct 42 ms 29184 KB Output is correct
3 Correct 42 ms 29220 KB Output is correct
4 Correct 42 ms 29124 KB Output is correct
5 Correct 44 ms 29232 KB Output is correct
6 Correct 42 ms 29240 KB Output is correct
7 Correct 44 ms 29236 KB Output is correct
8 Correct 42 ms 29204 KB Output is correct
9 Correct 42 ms 29252 KB Output is correct
10 Correct 43 ms 29256 KB Output is correct
11 Correct 474 ms 40748 KB Output is correct
12 Correct 502 ms 40884 KB Output is correct
13 Correct 491 ms 40852 KB Output is correct
14 Correct 476 ms 40996 KB Output is correct
15 Correct 471 ms 41008 KB Output is correct
16 Correct 483 ms 40960 KB Output is correct
17 Correct 483 ms 41000 KB Output is correct
18 Correct 486 ms 40748 KB Output is correct
19 Correct 474 ms 40960 KB Output is correct
20 Correct 470 ms 41008 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 29340 KB Output is correct
2 Correct 42 ms 29184 KB Output is correct
3 Correct 42 ms 29220 KB Output is correct
4 Correct 42 ms 29124 KB Output is correct
5 Correct 44 ms 29232 KB Output is correct
6 Correct 42 ms 29240 KB Output is correct
7 Correct 44 ms 29236 KB Output is correct
8 Correct 42 ms 29204 KB Output is correct
9 Correct 42 ms 29252 KB Output is correct
10 Correct 43 ms 29256 KB Output is correct
11 Correct 474 ms 40748 KB Output is correct
12 Correct 502 ms 40884 KB Output is correct
13 Correct 491 ms 40852 KB Output is correct
14 Correct 476 ms 40996 KB Output is correct
15 Correct 471 ms 41008 KB Output is correct
16 Correct 483 ms 40960 KB Output is correct
17 Correct 483 ms 41000 KB Output is correct
18 Correct 486 ms 40748 KB Output is correct
19 Correct 474 ms 40960 KB Output is correct
20 Correct 470 ms 41008 KB Output is correct
21 Execution timed out 2586 ms 74580 KB Time limit exceeded
22 Halted 0 ms 0 KB -