Submission #222369

#	Time	Username	Problem	Language	Result	Execution time	Memory
222369		errorgorn	Grudanje (COCI19_grudanje)	C++14	70 / 70	351 ms	15528 KiB

grudanje

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ll,ii>
#define endl '\n'

string s;
int q;
vector<ii> v;
int snow[100005];

bool arr[26][100005];
int pre[26][100005];

bool check(){
	for (int x=0;x<26;x++){
		for (int y=1;y<s.size();y++){
			pre[x][y]=pre[x][y-1]+arr[x][y];
		}
	}
	
	for (auto &it:v){
		for (int x=0;x<26;x++){
			if (pre[x][it.second]-pre[x][it.first-1]>1) return false;
		}
	}
	return true;
}

int main(){
	ios::sync_with_stdio(0);
    cin.tie(0);
	
	cin>>s;
	
	cin>>q;
	int a,b;
	for (int x=0;x<q;x++){
		cin>>a>>b;
		v.push_back(ii(a,b));
	}
	
	for (int x=0;x<s.size();x++){
		cin>>snow[x];
	}
	
	s='$'+s;
	
	int curr=0;
	for (int x=1;x<s.size();x++){
		arr[s[x]-'a'][x]=true;
	}
	
	if (check()){
		cout<<0;
		return 0;
	}
	
	int lo=0,hi=s.size(),mi;
	
	while (hi-lo>1){
		mi=hi+lo>>1;
		
		while (curr<mi){
			arr[s[snow[curr]]-'a'][snow[curr]]=false;
			curr++;
		}
		
		while (curr>mi){
			curr--;
			arr[s[snow[curr]]-'a'][snow[curr]]=true;
		}
		
		if (check()) hi=mi;
		else lo=mi;
	}
	
	cout<<hi<<endl;
	
}

Compilation message (stderr)

grudanje.cpp: In function 'bool check()':
grudanje.cpp:18:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int y=1;y<s.size();y++){
                ~^~~~~~~~~
grudanje.cpp: In function 'int main()':
grudanje.cpp:44:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int x=0;x<s.size();x++){
               ~^~~~~~~~~
grudanje.cpp:51:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int x=1;x<s.size();x++){
               ~^~~~~~~~~
grudanje.cpp:63:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mi=hi+lo>>1;
      ~~^~~

• 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