oj.uz

답안 #414381

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
414381 2021-05-30T11:46:27 Z mosiashvililuka 모임들 (IOI18_meetings) C++17
36 / 100
 675 ms 234844 KB 
#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.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 51 ms 95048 KB Output is correct
3 Correct 55 ms 95068 KB Output is correct
4 Correct 60 ms 95132 KB Output is correct
5 Correct 56 ms 95140 KB Output is correct
6 Correct 52 ms 95136 KB Output is correct
7 Correct 57 ms 95044 KB Output is correct
8 Correct 51 ms 95052 KB Output is correct
9 Correct 55 ms 95112 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 51 ms 95048 KB Output is correct
3 Correct 55 ms 95068 KB Output is correct
4 Correct 60 ms 95132 KB Output is correct
5 Correct 56 ms 95140 KB Output is correct
6 Correct 52 ms 95136 KB Output is correct
7 Correct 57 ms 95044 KB Output is correct
8 Correct 51 ms 95052 KB Output is correct
9 Correct 55 ms 95112 KB Output is correct
10 Correct 349 ms 234724 KB Output is correct
11 Correct 675 ms 234768 KB Output is correct
12 Correct 313 ms 234732 KB Output is correct
13 Correct 665 ms 234844 KB Output is correct
14 Correct 325 ms 234828 KB Output is correct
15 Correct 333 ms 234776 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 40 ms 3976 KB Output is correct
3 Correct 102 ms 13104 KB Output is correct
4 Correct 103 ms 13076 KB Output is correct
5 Correct 70 ms 13064 KB Output is correct
6 Correct 84 ms 13048 KB Output is correct
7 Correct 88 ms 13088 KB Output is correct

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 40 ms 3976 KB Output is correct
3 Correct 102 ms 13104 KB Output is correct
4 Correct 103 ms 13076 KB Output is correct
5 Correct 70 ms 13064 KB Output is correct
6 Correct 84 ms 13048 KB Output is correct
7 Correct 88 ms 13088 KB Output is correct
8 Incorrect 39 ms 6952 KB Unexpected end of file - int64 expected
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 51 ms 95048 KB Output is correct
3 Correct 55 ms 95068 KB Output is correct
4 Correct 60 ms 95132 KB Output is correct
5 Correct 56 ms 95140 KB Output is correct
6 Correct 52 ms 95136 KB Output is correct
7 Correct 57 ms 95044 KB Output is correct
8 Correct 51 ms 95052 KB Output is correct
9 Correct 55 ms 95112 KB Output is correct
10 Correct 349 ms 234724 KB Output is correct
11 Correct 675 ms 234768 KB Output is correct
12 Correct 313 ms 234732 KB Output is correct
13 Correct 665 ms 234844 KB Output is correct
14 Correct 325 ms 234828 KB Output is correct
15 Correct 333 ms 234776 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 40 ms 3976 KB Output is correct
18 Correct 102 ms 13104 KB Output is correct
19 Correct 103 ms 13076 KB Output is correct
20 Correct 70 ms 13064 KB Output is correct
21 Correct 84 ms 13048 KB Output is correct
22 Correct 88 ms 13088 KB Output is correct
23 Incorrect 39 ms 6952 KB Unexpected end of file - int64 expected
24 Halted 0 ms 0 KB -