Submission #313598

#	Time	Username	Problem	Language	Result	Execution time	Memory
313598		colazcy	Grudanje (COCI19_grudanje)	C++17	70 / 70	1475 ms	13688 KiB

grudanje

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1e5 + 100;
struct Query{int l,r;}query[maxn];
int n,q,val[maxn];
char str[maxn];
struct BIT{
	int f[maxn];
	inline int lowbit(int x){return x & (-x);}
	inline void add(int pos,int v){
		while(pos < maxn){
			f[pos] += v;
			pos += lowbit(pos);
		}
	}
	inline int query(int pos){
		int res = 0;
		while(pos){
			res += f[pos];
			pos -= lowbit(pos);
		}
		return res;
	}
	inline int query(int a,int b){return query(b) - query(a - 1);}
}bit[26];
inline void init(){
	for(int i = 1;i <= n;i++)
		bit[str[i] - 'a'].add(i,1); 
}
inline bool check(int limit){
	bool res = true;
	for(int i = 1;i <= limit;i++)
		bit[str[val[i]] - 'a'].add(val[i],-1);
	for(int i = 1;i <= q && res;i++)
		for(int j = 0;j < 26;j++)
			if(bit[j].query(query[i].l,query[i].r) > 1){
				res = false;
				break;
			}
	for(int i = 1;i <= limit;i++)
		bit[str[val[i]] - 'a'].add(val[i],1);
	return res;
}
int main(){
	scanf("%s",str + 1);
	n = strlen(str + 1);
	scanf("%d",&q);
	for(int i = 1;i <= q;i++)scanf("%d %d",&query[i].l,&query[i].r);
	for(int i = 1;i <= n;i++)scanf("%d",val + i);
	init();
	int l = 0,r = n,ans = 0;
	while(l <= r){
		int mid = (l + r) >> 1;
		if(check(mid))ans = mid,r = mid - 1;
		else l = mid + 1;
	}
	printf("%d\n",ans);
	return 0;
}

Compilation message (stderr)

grudanje.cpp: In function 'int main()':
grudanje.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   46 |  scanf("%s",str + 1);
      |  ~~~~~^~~~~~~~~~~~~~
grudanje.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
grudanje.cpp:49:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |  for(int i = 1;i <= q;i++)scanf("%d %d",&query[i].l,&query[i].r);
      |                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
grudanje.cpp:50:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |  for(int i = 1;i <= n;i++)scanf("%d",val + i);
      |                           ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 7 / 7
• Subtask 5: 7 / 7
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 7 / 7
• Subtask 9: 7 / 7
• Subtask 10: 7 / 7