Submission #222365

#	Time	Username	Problem	Language	Result	Execution time	Memory
222365		errorgorn	Grudanje (COCI19_grudanje)	C++14	35 / 70	2112 ms	246924 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];

struct node{
	int s,e,m;
	int val=0;
	node *l,*r;
	
	node(int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
		
	void update(int i,int j){
		val+=j;
		if (s==e) return;
		else if (i<=m) l->update(i,j);
		else r->update(i,j);
	}
	
	int query(int i,int j){
		if (s==i && e==j) return val;
		else if (j<=m) return l->query(i,j);
		else if (m<i) return r->query(i,j);
		else return l->query(i,m)+r->query(m+1,j);
	}
}*root[26];

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

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

Compilation message (stderr)

grudanje.cpp: In constructor 'node::node(int, int)':
grudanje.cpp:19:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   s=_s,e=_e,m=s+e>>1;
               ~^~
grudanje.cpp: In function 'int main()':
grudanje.cpp:67:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int x=0;x<s.size();x++){
               ~^~~~~~~~~
grudanje.cpp:73:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int x=0;x<s.size();x++){
               ~^~~~~~~~~
grudanje.cpp:85: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: 0 / 7
• Subtask 7: 0 / 7
• Subtask 8: 0 / 7
• Subtask 9: 0 / 7
• Subtask 10: 0 / 7