oj.uz

답안 #913896

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
913896 2024-01-20T12:29:49 Z Trisanu_Das 모임들 (IOI18_meetings) C++17
36 / 100
 259 ms 199256 KB 
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
long long rsq[5005][5005];
int cnt[100005];
int idx[100005];
vector<int>highs;
vector<int>nhighs;
int st[100005][20];
int query(int l,int r){
	if(l>r) return 0;
	int m=log2(r-l+1);
	//cout<<l<<" "<<r<<": "<<max(st[l][m],st[r-(1<<m)+1][m])<<endl;
	return max(st[l][m],st[r-(1<<m)+1][m]);
}
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
	vector<long long>ret;
	int N=H.size();
	if(N<=5000){
		memset(rsq,0,sizeof rsq);
		for(int i=0;i<N;i++){
			int maxi=H[i];
			rsq[i][i]=H[i];
			for(int j=i-1;j>=0;j--){
				maxi=max(maxi,H[j]);
				rsq[i][j]=rsq[i][j+1]+maxi;
			}
			maxi=H[i];
			for(int j=i+1;j<N;j++){
				maxi=max(maxi,H[j]);
				rsq[i][j]=rsq[i][j-1]+maxi;
			}
		}
		for(int q=0;q<L.size();q++){
			int l=L[q],r=R[q];
			long long res=LONG_LONG_MAX;
			for(int i=l;i<=r;i++){
				res=min(res,rsq[i][l]+rsq[i][r]-H[i]);
			}
			ret.push_back(res);
		}
	}
	else{
		int last=-1;
		cnt[0]=0;
		for(int i=0;i<N;i++){
			if(i>0) cnt[i]=cnt[i-1];
			if(H[i]==2){
				idx[i]=highs.size();
				cnt[i]++;
				highs.push_back(i);
				nhighs.push_back(-i);
			}
		}
		highs.push_back(N);
		int M=cnt[N-1];
		for(int i=0;i<M;i++){
			st[i][0]=highs[i+1]-highs[i];
		}
		for(int j=1;j<20;j++){
			for(int i=0;i<=M-(1<<j);i++){
				st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
			}
		}
		for(int q=0;q<L.size();q++){
			int l=L[q],r=R[q];
			if(cnt[r]-cnt[l]+(int)(H[l]==2)==0){
				ret.push_back(r-l+1);
			}
			else{
				int l1=*lower_bound(highs.begin(),highs.end(),l);
				int l2=*lower_bound(nhighs.rbegin(),nhighs.rend(),-r);
				l2*=-1;
				int ans=max(l1-l,r-l2);
				if(l1!=l2){
					int idx1=idx[l1],idx2=idx[l2]-1;
					ans=max(query(idx1,idx2)-1,ans);
				}
				ret.push_back(2*(r-l+1)-ans);
			}
			hell:;
		}
	}
	return ret;
}

Compilation message

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:34:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for(int q=0;q<L.size();q++){
      |               ~^~~~~~~~~
meetings.cpp:65:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for(int q=0;q<L.size();q++){
      |               ~^~~~~~~~~
meetings.cpp:44:7: warning: unused variable 'last' [-Wunused-variable]
   44 |   int last=-1;
      |       ^~~~
meetings.cpp:81:4: warning: label 'hell' defined but not used [-Wunused-label]
   81 |    hell:;
      |    ^~~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 198740 KB Output is correct
2 Correct 51 ms 198740 KB Output is correct
3 Correct 52 ms 198676 KB Output is correct
4 Correct 52 ms 198840 KB Output is correct
5 Correct 50 ms 199000 KB Output is correct
6 Correct 51 ms 198740 KB Output is correct
7 Correct 52 ms 198736 KB Output is correct
8 Correct 52 ms 198836 KB Output is correct
9 Correct 51 ms 198820 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 198740 KB Output is correct
2 Correct 51 ms 198740 KB Output is correct
3 Correct 52 ms 198676 KB Output is correct
4 Correct 52 ms 198840 KB Output is correct
5 Correct 50 ms 199000 KB Output is correct
6 Correct 51 ms 198740 KB Output is correct
7 Correct 52 ms 198736 KB Output is correct
8 Correct 52 ms 198836 KB Output is correct
9 Correct 51 ms 198820 KB Output is correct
10 Correct 257 ms 199256 KB Output is correct
11 Correct 130 ms 199144 KB Output is correct
12 Correct 235 ms 199020 KB Output is correct
13 Correct 141 ms 199116 KB Output is correct
14 Correct 245 ms 198988 KB Output is correct
15 Correct 259 ms 199108 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 198740 KB Output is correct
2 Correct 20 ms 6632 KB Output is correct
3 Correct 55 ms 14664 KB Output is correct
4 Correct 41 ms 9932 KB Output is correct
5 Correct 48 ms 14856 KB Output is correct
6 Correct 51 ms 16804 KB Output is correct
7 Correct 49 ms 14664 KB Output is correct

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 198740 KB Output is correct
2 Correct 20 ms 6632 KB Output is correct
3 Correct 55 ms 14664 KB Output is correct
4 Correct 41 ms 9932 KB Output is correct
5 Correct 48 ms 14856 KB Output is correct
6 Correct 51 ms 16804 KB Output is correct
7 Correct 49 ms 14664 KB Output is correct
8 Incorrect 48 ms 12244 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 198740 KB Output is correct
2 Correct 51 ms 198740 KB Output is correct
3 Correct 52 ms 198676 KB Output is correct
4 Correct 52 ms 198840 KB Output is correct
5 Correct 50 ms 199000 KB Output is correct
6 Correct 51 ms 198740 KB Output is correct
7 Correct 52 ms 198736 KB Output is correct
8 Correct 52 ms 198836 KB Output is correct
9 Correct 51 ms 198820 KB Output is correct
10 Correct 257 ms 199256 KB Output is correct
11 Correct 130 ms 199144 KB Output is correct
12 Correct 235 ms 199020 KB Output is correct
13 Correct 141 ms 199116 KB Output is correct
14 Correct 245 ms 198988 KB Output is correct
15 Correct 259 ms 199108 KB Output is correct
16 Correct 32 ms 198740 KB Output is correct
17 Correct 20 ms 6632 KB Output is correct
18 Correct 55 ms 14664 KB Output is correct
19 Correct 41 ms 9932 KB Output is correct
20 Correct 48 ms 14856 KB Output is correct
21 Correct 51 ms 16804 KB Output is correct
22 Correct 49 ms 14664 KB Output is correct
23 Incorrect 48 ms 12244 KB Output isn't correct
24 Halted 0 ms 0 KB -