Submission #222389

#	Time	Username	Problem	Language	Result	Execution time	Memory
222389		jamielim	Grudanje (COCI19_grudanje)	C++14	70 / 70	79 ms	4220 KiB

grudanje

#include <bits/stdc++.h>
using namespace std;

int main(){
	char str[100005];
	scanf("%s",str);
	int n=(int)strlen(str),q;
	scanf("%d",&q);
	pair<int,int> qu[q];
	for(int i=0;i<q;i++){
		scanf("%d%d",&qu[i].first,&qu[i].second);
		qu[i].first--;qu[i].second--;
	}
	sort(qu,qu+q);
	int pmax[n],smin[n];
	int ptr=0;
	for(int i=0;i<n;i++){
		if(i==0)pmax[i]=-1;
		else pmax[i]=pmax[i-1];
		while(ptr<q&&qu[ptr].first==i){
			pmax[i]=max(pmax[i],qu[ptr].second);
			ptr++;
		}
	}
	for(int i=0;i<q;i++){swap(qu[i].first,qu[i].second);}
	sort(qu,qu+q);
	ptr=q-1;
	for(int i=n-1;i>=0;i--){
		if(i==n-1)smin[i]=n;
		else smin[i]=smin[i+1];
		while(ptr>=0&&qu[ptr].first==i){
			smin[i]=min(smin[i],qu[ptr].second);
			ptr--;
		}
	}
	int p[n];
	for(int i=0;i<n;i++){scanf("%d",&p[i]);p[i]--;}
	set<int> s[26];
	for(int i=n-1;i>=0;i--){
		int k=str[p[i]]-'a';
		auto it=s[k].upper_bound(p[i]);
		if(it!=s[k].end()){
			int y=(*it);
			if(pmax[p[i]]>=y){
				printf("%d",i+1);
				return 0;
			}
		}
		if(it!=s[k].begin()){
			--it; int x=(*it);
			if(smin[p[i]]<=x){
				printf("%d",i+1);
				return 0;
			}
		}
		s[k].insert(p[i]);
	}
	printf("0");
}

Compilation message (stderr)

grudanje.cpp: In function 'int main()':
grudanje.cpp:6:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",str);
  ~~~~~^~~~~~~~~~
grudanje.cpp:8:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
grudanje.cpp:11:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&qu[i].first,&qu[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
grudanje.cpp:37:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<n;i++){scanf("%d",&p[i]);p[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