oj.uz

Submission #355624

# Submission time Handle Problem Language Result Execution time Memory
355624 2021-01-22T21:19:33 Z thomas_li San (COCI17_san) C++17
120 / 120
 996 ms 43592 KB 
#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.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5736 KB Output is correct
2 Correct 5 ms 748 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 11172 KB Output is correct
2 Correct 24 ms 1152 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 996 ms 43592 KB Output is correct
2 Correct 126 ms 4328 KB Output is correct