Submission #414381

#	Time	Username	Problem	Language	Result	Execution time	Memory
414381		mosiashvililuka	Meetings (IOI18_meetings)	C++17	36 / 100	675 ms	234844 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
const long long inf=99999999999999999LL;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,f[750009],pas,l,r,z,lft[100009],rgt[100009],F[400009];
long long sub3;
long long seg[400009],za;
pair <long long, long long> Q[750009];
vector <long long> ANS;
long long Lf[5003][5003],Rg[5003][5003];
void read(long long q, long long w, long long rr){
	if(q>r||w<l) return;
	if(q>=l&&w<=r){
		if(z<seg[rr]) z=seg[rr];
		return;
	}
	read(q,(q+w)/2,rr*2);
	read((q+w)/2+1,w,rr*2+1);
}
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    a=H.size();
    tes=L.size();
    for(i=1; i<=a; i++){
        f[i]=H[i-1];
    }
    for(t=1; t<=tes; t++){
        Q[t].first=L[t-1]+1;
        Q[t].second=R[t-1]+1;
    }
    sub3=0;
    for(i=1; i<=a; i++){
    	if(f[i]>2){
    		sub3=1;
    		break;
		}
	}
	if(sub3==0){
		lft[0]=0;
		for(i=1; i<=a; i++){
			if(f[i]==2){
				lft[i]=i;
			}else{
				lft[i]=lft[i-1];
			}
		}
		rgt[a+1]=a+1;
		for(i=a; i>=1; i--){
			if(f[i]==2){
				rgt[i]=i;
			}else{
				rgt[i]=rgt[i+1];
			}
		}
		for(i=1; i<=a; i++){
			F[i]=i-lft[i]+rgt[i]-i-1;
			if(F[i]<0) F[i]=0;
		}
		za=1;
		while(za<a) za*=2;
		for(i=za; i<za+a; i++){
			seg[i]=F[i-za+1];
		}
		for(i=za+a; i<=za*2; i++){
			seg[i]=0;
		}
		for(i=za-1; i>=1; i--){
			seg[i]=max(seg[i*2],seg[i*2+1]);
		}
		for(t=1; t<=tes; t++){
			c=rgt[Q[t].first];d=lft[Q[t].second];
			if(c>d){
				ANS.push_back(Q[t].second-Q[t].first+1);
				continue;
			}
			l=c;r=d;z=0;
			read(1,za,1);
			z=max(z,c-Q[t].first);
			z=max(z,Q[t].second-d);
			zx=z+(Q[t].second-Q[t].first+1-z)*2;
			ANS.push_back(zx);
		}
		return ANS;
	}
    if(a<=5000&&tes<=5000){
        for(i=1; i<=a; i++){
            zx=0;xc=0;
            for(j=i; j>=1; j--){
                if(xc<f[j]) xc=f[j];
                zx+=xc;
                Lf[i][j]=zx;
            }
        }
        for(i=1; i<=a; i++){
            zx=0;xc=0;
            for(j=i; j<=a; j++){
                if(xc<f[j]) xc=f[j];
                zx+=xc;
                Rg[i][j]=zx;
            }
        }
        for(t=1; t<=tes; t++){
            zx=inf;
            for(i=Q[t].first; i<=Q[t].second; i++){
                if(zx>Lf[i][Q[t].first]+Rg[i][Q[t].second]-f[i]){
                    zx=Lf[i][Q[t].first]+Rg[i][Q[t].second]-f[i];
                }
            }
            ANS.push_back(zx);
        }
        return ANS;
    }
    return ANS;
}
/*int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    vector <int> H,L,R;
    cin>>a>>tes;
    for(i=1; i<=a; i++){
        cin>>c;
        H.push_back(c);
    }
    for(t=1; t<=tes; t++){
        cin>>c>>d;
        L.push_back(c);
        R.push_back(d);
    }
    ANS=minimum_costs(H,L,R);
    for(t=0; t<ANS.size(); t++){
        cout<<ANS[t]<<" ";
    }
    return 0;
}*/

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40