Submission #355624

#	Time	Username	Problem	Language	Result	Execution time	Memory
355624		thomas_li	San (COCI17_san)	C++17	120 / 120	996 ms	43592 KiB

san

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
const int MM = 41;
int n,h[MM],g[MM]; ll need;

using namespace std;
typedef __gnu_pbds::tree<pair<ll,int>, __gnu_pbds::null_type, less<pair<ll,int>>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> bbst;
bbst s; int inc;
int main(){ 
	cin.tie(0)->sync_with_stdio(0); 
	cin >> n >> need;
	for(int i = 0; i < n; i++) cin >> h[i] >> g[i];
	int lft = n/2, rit = n - lft;
	map<int,vector<ll>> lmp,rmp;
	for(int msk = 1; msk < (1<<lft); msk++){
		ll sum = 0; int lst = -1;
		bool bad = 0;
		for(int i = 0; i < lft; i++){
			if(!(msk & 1 << i)) continue;
			if(lst != -1 && lst > h[i]){
				bad = 1;
				break;
			}
			lst = h[i]; sum += g[i];
		}
		if(bad) continue;
		lmp[lst].emplace_back(sum);
	}
	for(int msk = 1; msk < (1<<rit); msk++){
		ll sum = 0; int lst = -1,fst = -1; 
		bool bad = 0; 
		for(int i = 0; i < rit; i++){
			if(!(msk & 1 << i)) continue;
			if(lst != -1 && lst > h[i+lft]){
				bad = 1;
				break;
			}
			if(fst == -1) fst = h[i+lft];
			lst = h[i+lft]; sum += g[i+lft];
		}
		if(bad) continue;
		rmp[fst].emplace_back(sum);
	}
	ll ans = 0;
	
	vector<pair<int,vector<ll>>> b(rmp.begin(),rmp.end()); int ptr = 0;
	//sort(a.begin(),a.end(),[](const pair<int,vector<ll>>& lhs, const pair<int,vector<ll>>& rhs){return lhs.first < rhs.first; });
	//sort(b.begin(),b.end(),[](const pair<int,vector<ll>>& lhs, const pair<int,vector<ll>>& rhs){return lhs.first < rhs.first; });
	for(int i = 0; i < (int)b.size(); i++){
		for(ll x : b[i].second) s.insert({x,inc++}), ans += x >= need;
	}	
	for(auto&[k,vec]:lmp){
		for(ll v : vec){
			if(v >= need) ans++;
			while(ptr < (int)b.size() && k > b[ptr].first){
				for(ll x : b[ptr].second) s.erase(s.lower_bound({x,-1}));
				ptr++;
			}
			ans += s.size() - s.order_of_key({need - v,0});
		}
	}

	cout << ans << "\n";
}

• Subtask 1: 24 / 24
• Subtask 2: 24 / 24
• Subtask 3: 24 / 24
• Subtask 4: 24 / 24
• Subtask 5: 24 / 24