Submission #1112418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112418		thelegendary08	Meetings (IOI18_meetings)	C++14	21 / 100	71 ms	8128 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
#define vi vector<int>
#define vb vector<bool>
#define vpii vector<pair<int,int>>
#define pb push_back
#define vvi vector<vector<int>>
#define ll long long int
#define f0r(i,n) for(int i = 0; i<n; i++)
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<'\n';
#define pii pair<int,int>
#define FOR(i,k,n) for(int i = k; i<n; i++)
using namespace std;
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
	int q = L.size();
	std::vector<long long> ans(q);
	vi v = H;
	int n = v.size();
	//n <= 3000 && q <= 10
	if(n <= 3000 && q <= 10){
		f0r(i, q){
			int l = L[i];
			int r = R[i];
			ll cur = 4e18;
			for(int j = l; j <= r; j++){
				ll s = 0;
				int runmx = v[j];
				
				for(int k = j; k >= l; k--){
					runmx = max(runmx, v[k]);
					s += runmx;
				}
				runmx = v[j];
				for(int k = j+1; k<=r; k++){
					runmx = max(runmx, v[k]);
					s += runmx;
				}
				cur = min(cur,s);
				//cout<<s<<'\n';
			}
			ans[i] = cur;
		}
	}
	else{
		vpii s;
		int cnt = 0;
		f0r(i, n){
			if(v[i] == 1){
				cnt++;
			}
			else{
				if(cnt > 0){
					s.pb({cnt, i - cnt});
					cnt = 0;
				}
			}
		}
		if(cnt > 0){
			s.pb({cnt, n - cnt});
		}
		vi dexes;
		f0r(i, s.size())dexes.pb(s[i].second);
		vi nums;
		f0r(i,s.size())nums.pb(s[i].first);
		//vout(dexes);
		//vout(nums);
		int spt[nums.size()][17];
		f0r(i, nums.size()){
			spt[i][0] = nums[i];
		}
		//cout<<nums.size()<<'\n';
		FOR(i, 1, 17){
			//if(i >2)cout<<(int)nums.size() - (1 << i) + 1<<'\n';
			//else{
				f0r(j, (int)nums.size() - (1 << i) + 1){
					spt[j][i] = max(spt[j][i-1], spt[j + (1 << (i-1))][i-1]);
				}
			//}
			
		}
		//vout(dexes);
		f0r(i, q){
			int l = L[i];
			int r = R[i];
			int fb = lower_bound(dexes.begin(), dexes.end(), l) - dexes.begin() - 1;
			int mx = 0;
			bool in1 = 0;
			if(fb >= 0 && s[fb].first + s[fb].second - 1 >= l){
				mx = max(mx, min(r,s[fb].first + s[fb].second - 1) - l + 1);
				in1 = 1;
			}
			int lastone = upper_bound(dexes.begin(), dexes.end(), r) - dexes.begin() - 1;
			//cout<<mx<<'\n';
			if(lastone >= 0 && s[lastone].first + s[lastone].second - 1 > r){
				mx = max(mx, r - max(s[lastone].second, l) + 1);
				int left = fb + 1;
				int right = lastone - 1;
				//cout<<left<<' '<<right<<'\n';
				if(left <= right){
					int msb = floor(log2(right - left + 1));
					mx = max(mx, max(spt[left][msb], spt[right - (1 << msb) + 1][msb]));
				}
			}
			else{
				int left = fb + 1;
				int right = lastone;
				//cout<<left<<' '<<right<<'\n';
				if(left <= right){
					int msb = floor(log2(right - left + 1));
					mx = max(mx, max(spt[left][msb], spt[right - (1 << msb) + 1][msb]));
				}
			}
			//cout<<mx<<" S"<<'\n';
			//cout<<lastone<<' '<<fb<<'\n';
			if(false){
				ans[i] = r - l + 1;
			}
			else{
				ans[i] = (2 * (r - l + 1) - mx);
			}
		}
		
	}
	
	return ans;
}

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:9:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define f0r(i,n) for(int i = 0; i<n; i++)
......
   63 |   f0r(i, s.size())dexes.pb(s[i].second);
      |       ~~~~~~~~~~~                 
meetings.cpp:63:3: note: in expansion of macro 'f0r'
   63 |   f0r(i, s.size())dexes.pb(s[i].second);
      |   ^~~
meetings.cpp:9:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define f0r(i,n) for(int i = 0; i<n; i++)
......
   65 |   f0r(i,s.size())nums.pb(s[i].first);
      |       ~~~~~~~~~~                  
meetings.cpp:65:3: note: in expansion of macro 'f0r'
   65 |   f0r(i,s.size())nums.pb(s[i].first);
      |   ^~~
meetings.cpp:9:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define f0r(i,n) for(int i = 0; i<n; i++)
......
   69 |   f0r(i, nums.size()){
      |       ~~~~~~~~~~~~~~              
meetings.cpp:69:3: note: in expansion of macro 'f0r'
   69 |   f0r(i, nums.size()){
      |   ^~~
meetings.cpp:88:9: warning: variable 'in1' set but not used [-Wunused-but-set-variable]
   88 |    bool in1 = 0;
      |         ^~~

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