oj.uz

Submission #115437

# Submission time Handle Problem Language Result Execution time Memory
115437 2019-06-07T13:28:36 Z dsjong Meetings (IOI18_meetings) C++14
36 / 100
 684 ms 196736 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 between signed and unsigned integer expressions [-Wsign-compare]
   for(int q=0;q<L.size();q++){
               ~^~~~~~~~~
meetings.cpp:65:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int q=0;q<L.size();q++){
               ~^~~~~~~~~
meetings.cpp:44:7: warning: unused variable 'last' [-Wunused-variable]
   int last=-1;
       ^~~~
meetings.cpp:81:4: warning: label 'hell' defined but not used [-Wunused-label]
    hell:;
    ^~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 196448 KB Output is correct
2 Correct 185 ms 196420 KB Output is correct
3 Correct 182 ms 196376 KB Output is correct
4 Correct 183 ms 196372 KB Output is correct
5 Correct 187 ms 196460 KB Output is correct
6 Correct 183 ms 196452 KB Output is correct
7 Correct 183 ms 196432 KB Output is correct
8 Correct 183 ms 196480 KB Output is correct
9 Correct 187 ms 196444 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 196448 KB Output is correct
2 Correct 185 ms 196420 KB Output is correct
3 Correct 182 ms 196376 KB Output is correct
4 Correct 183 ms 196372 KB Output is correct
5 Correct 187 ms 196460 KB Output is correct
6 Correct 183 ms 196452 KB Output is correct
7 Correct 183 ms 196432 KB Output is correct
8 Correct 183 ms 196480 KB Output is correct
9 Correct 187 ms 196444 KB Output is correct
10 Correct 495 ms 196724 KB Output is correct
11 Correct 684 ms 196728 KB Output is correct
12 Correct 493 ms 196660 KB Output is correct
13 Correct 681 ms 196708 KB Output is correct
14 Correct 502 ms 196720 KB Output is correct
15 Correct 503 ms 196736 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 196468 KB Output is correct
2 Correct 35 ms 2232 KB Output is correct
3 Correct 103 ms 8944 KB Output is correct
4 Correct 79 ms 4616 KB Output is correct
5 Correct 85 ms 9000 KB Output is correct
6 Correct 94 ms 9368 KB Output is correct
7 Correct 94 ms 8728 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 196468 KB Output is correct
2 Correct 35 ms 2232 KB Output is correct
3 Correct 103 ms 8944 KB Output is correct
4 Correct 79 ms 4616 KB Output is correct
5 Correct 85 ms 9000 KB Output is correct
6 Correct 94 ms 9368 KB Output is correct
7 Correct 94 ms 8728 KB Output is correct
8 Incorrect 85 ms 5096 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 196448 KB Output is correct
2 Correct 185 ms 196420 KB Output is correct
3 Correct 182 ms 196376 KB Output is correct
4 Correct 183 ms 196372 KB Output is correct
5 Correct 187 ms 196460 KB Output is correct
6 Correct 183 ms 196452 KB Output is correct
7 Correct 183 ms 196432 KB Output is correct
8 Correct 183 ms 196480 KB Output is correct
9 Correct 187 ms 196444 KB Output is correct
10 Correct 495 ms 196724 KB Output is correct
11 Correct 684 ms 196728 KB Output is correct
12 Correct 493 ms 196660 KB Output is correct
13 Correct 681 ms 196708 KB Output is correct
14 Correct 502 ms 196720 KB Output is correct
15 Correct 503 ms 196736 KB Output is correct
16 Correct 163 ms 196468 KB Output is correct
17 Correct 35 ms 2232 KB Output is correct
18 Correct 103 ms 8944 KB Output is correct
19 Correct 79 ms 4616 KB Output is correct
20 Correct 85 ms 9000 KB Output is correct
21 Correct 94 ms 9368 KB Output is correct
22 Correct 94 ms 8728 KB Output is correct
23 Incorrect 85 ms 5096 KB Output isn't correct
24 Halted 0 ms 0 KB -