Submission #340498

#	Time	Username	Problem	Language	Result	Execution time	Memory
340498		A_D	Grudanje (COCI19_grudanje)	C++14	35 / 70	2088 ms	66024 KiB

grudanje

/*
ID: antwand1
TASK: barn1
LANG: C++
*/
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define du long double
#define F first
#define S second
using namespace std;
const int N=1e5+1;
int mn[N],mx[N];
int l1[N];
int rr[N];
int p[N];
int segmn[4*N];
int segmx[4*N];
int lazymn[4*N];
int lazymx[4*N];
int seg[4*N][26];
string a;
int q,n;
void fix1(int p,int s,int e) {
	if(lazymn[p]!=1e18) {
		if(s!=e) {
			lazymn[2*p] = min(lazymn[2*p] ,lazymn[p]);
			lazymn[2*p+1] = min(lazymn[2*p+1] ,lazymn[p]);
		}
		else{
            mn[s]=min(mn[s],lazymn[p]);
		}
		lazymn[p] = 1e18;
	}
	if(lazymx[p]) {
		if(s!=e) {
			lazymx[2*p] = max(segmx[2*p] ,lazymx[p]);
			lazymx[2*p+1] = max(segmx[2*p+1] ,lazymx[p]);
		}
		else{
            mx[s]=max(mx[s],lazymx[p]);
		}
		lazymx[p] = 0;
	}
}
void update1(int p,int s,int e,int a,int b) {
	fix1(p,s,e);
	if(s>=a && e<=b) {
		lazymn[p] =min(lazymn[p], a);
		lazymx[p] =max(lazymx[p], b);
		fix1(p,s,e);
		return;
	}
	if(s>b || e<a)
		return;
	update1(2*p,s,(s+e)/2,a,b);
	update1(2*p+1,(s+e)/2+1,e,a,b);
}
void build1(int p,int s,int e) {
    fix1(p,s,e);
	if(s==e) {
		return;
	}
	build1(2*p,s,(s+e)/2);
	build1(2*p+1,(s+e)/2+1,e);
}
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(int i=1;i<=4*n;i++){
        segmn[i]=1e18;
        lazymn[i]=1e18;
    }
    for(int i=1;i<=n;i++){
        mn[i]=i;
        mx[i]=i;
        update1(1,1,n,i,i);
    }
    for(long i=1;i<=q;i++){
        int l,r;
        cin>>l>>r;
        update1(1,1,n,l,r);
        l1[i]=l;
        rr[i]=r;
    }
    build1(1,1,n);
    for(int i=0;i<26;i++){
        build(1,1,n,i);
    }
    for(int i=1;i<=n;i++){
        int h=a[i]-'a';
        int s=get(1,1,n,mn[i],mx[i],h);
        if(s!=1)r++;
    }
    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:115:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  115 | main()
      |      ^

• 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