Submission #448081

#	Time	Username	Problem	Language	Result	Execution time	Memory
448081		keta_tsimakuridze	Index (COCI21_index)	C++14	110 / 110	677 ms	53516 KiB

index

#include<bits/stdc++.h>
#define f first
#define s second
#define pii pair<pair<int,int>,int> 
using namespace std;
const int N=2e5+5,mod=1e9+7;
int tree[N],n,q,x,ans[N];
vector<int> c[N];
vector<pair<int,int> > st[N];
void upd(int ind,int val) {
	for(ind;ind<=n;ind+=(-ind)&ind) {
		tree[ind] += val;
	}
}
int get(int ind) {
	int ans = 0;
	for(ind;ind>=1;ind-=(-ind)&ind) ans += tree[ind];
	return ans;
}
void solve(int l,int r,vector<pii> v) {
	if(l > r) return;
	if(l==r) {
		for(int i=0;i<c[l].size();i++) {
			upd(c[l][i],1);
		}
		for(int i=0;i<v.size();i++) {
			int L = v[i].f.f, r = v[i].f.s;
			if(get(r) - get(L-1) >=l ) ans[v[i].s] = l;
		}
		for(int i=0;i<c[l].size();i++) {
			upd(c[l][i],-1);
		}
		return ;
	}
	int mid = (l+r)/2;
	for(int i=mid; i<=r; i++) {
		for(int j=0;j<c[i].size();j++) {
			upd(c[i][j],1);
		}
	}
	vector<pii> x,y;
	for(int i=0;i<v.size();i++) {
		int l = v[i].f.f, r = v[i].f.s;
		if(get(r) - get(l-1) >=mid ) { 
			ans[v[i].s] = mid;
			x.push_back(v[i]);	
		}
		else y.push_back(v[i]);
	}
	solve(l,mid-1,y);
	for(int i=mid; i<=r; i++) {
		for(int j=0;j<c[i].size();j++) {
			upd(c[i][j],-1);
		}
	}	
	solve(mid+1,r,x);
}
 main(){
	cin>>n>>q;
	x = 0;
	for(int i=1;i<=n;i++){
		int a;
		cin>>a;
		c[a].push_back(i);
		x = max(x,a);
	}
	vector<pii> all;
	for(int i=1;i<=q;i++) {
		int l,r;
		cin >> l >> r;
		
		all.push_back({{l,r},i});
		st[l].push_back({r,i});
	}
	
	solve(1,x,all);
	for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
}

Compilation message (stderr)

index.cpp: In function 'void upd(int, int)':
index.cpp:11:6: warning: statement has no effect [-Wunused-value]
   11 |  for(ind;ind<=n;ind+=(-ind)&ind) {
      |      ^~~
index.cpp: In function 'int get(int)':
index.cpp:17:6: warning: statement has no effect [-Wunused-value]
   17 |  for(ind;ind>=1;ind-=(-ind)&ind) ans += tree[ind];
      |      ^~~
index.cpp: In function 'void solve(int, int, std::vector<std::pair<std::pair<int, int>, int> >)':
index.cpp:23:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   for(int i=0;i<c[l].size();i++) {
      |               ~^~~~~~~~~~~~
index.cpp:26:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   for(int i=0;i<v.size();i++) {
      |               ~^~~~~~~~~
index.cpp:30:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   for(int i=0;i<c[l].size();i++) {
      |               ~^~~~~~~~~~~~
index.cpp:37:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   for(int j=0;j<c[i].size();j++) {
      |               ~^~~~~~~~~~~~
index.cpp:42:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for(int i=0;i<v.size();i++) {
      |              ~^~~~~~~~~
index.cpp:52:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for(int j=0;j<c[i].size();j++) {
      |               ~^~~~~~~~~~~~
index.cpp: At global scope:
index.cpp:58:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   58 |  main(){
      |  ^~~~

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50