Submission #340499

#	Time	Username	Problem	Language	Result	Execution time	Memory
340499		A_D	Grudanje (COCI19_grudanje)	C++14	35 / 70	2081 ms	28648 KiB

grudanje

/*
ID: antwand1
TASK: barn1
LANG: C++
*/
#include <bits/stdc++.h>
#define ll int
#define du long double
#define F first
#define S second
using namespace std;
const int N=1e5+1;
int l1[N];
int rr[N];
int p[N];
int seg[4*N][26];
string a;
int q,n;
void build(int p,int s,int e,int &num)
{
    if(s==e) {
		if(a[s]-'a'==num)seg[p][num]=1;
		return;
	}
	build(2*p,s,(s+e)/2,num);
	build(2*p+1,(s+e)/2+1,e,num);
	seg[p][num] = seg[2*p][num] + seg[2*p+1][num];
}
void update(int p,int s,int e,int&i,int&r,int v) {
	if(s==e) {
		seg[p][r] = v;
		return;
	}
	if(i <= (s+e)/2)
		update(2*p,s,(s+e)/2,i,r,v);
	else update(2*p+1,(s+e)/2+1,e,i,r,v);
	seg[p][r] = seg[2*p][r] + seg[2*p+1][r];
}
int get(int p,int s,int e,int a, int b,int&i) {
	if(s>=a && e<=b)
		return seg[p][i];
	if(s>b || e<a)
		return 0;
	return get(2*p,s,(s+e)/2,a,b,i) + get(2*p+1,(s+e)/2+1,e,a,b,i);
}
bool ok()
{
    for(int i=1;i<=q;i++){
        for(int j=0;j<26;j++){
            if(get(1,1,n,l1[i],rr[i],j)>1)return 0;
        }
    }
    return 1;
}
bool o(int mid)
{
    for(int i=1;i<=n;i++){
        int q=a[p[i]]-'a';
        if(i<=mid){
            update(1,1,n,p[i],q,0);
        }
        else update(1,1,n,p[i],q,1);
    }
    return ok();
}
main()
{
    //freopen("barn1.in","r",stdin);freopen("barn1.out","w",stdout);
    cin>>a;
    int r=0;
    n=a.size();
    a="#"+a;
    cin>>q;
    for(long i=1;i<=q;i++){
        int l,r;
        cin>>l>>r;
        l1[i]=l;
        rr[i]=r;
    }
    for(int i=0;i<26;i++){
        build(1,1,n,i);
    }
    for(int i=1;i<=n;i++)cin>>p[i];
    if(ok()){
        cout<<0<<endl;
        return 0;
    }
    int lef=1,righ=n,ans=0;
    while(lef<=righ){
        int mid=(lef+righ)/2;
        if(o(mid)){
            ans=mid;
            righ=mid-1;
        }
        else{
            lef=mid+1;
        }
    }
    cout<<ans<<endl;
}

Compilation message (stderr)

grudanje.cpp:66:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   66 | main()
      |      ^
grudanje.cpp: In function 'int main()':
grudanje.cpp:70:9: warning: unused variable 'r' [-Wunused-variable]
   70 |     int r=0;
      |         ^

• 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