Submission #374539

#TimeUsernameProblemLanguageResultExecution timeMemory
374539Atill83San (COCI17_san)C++14
0 / 120
180 ms13240 KiB
#include <bits/stdc++.h> #define ff first #define ss second #define endl '\n' using namespace std; const long long INF = (long long) 1e18; const int mod = (int) 1e9+7; const int MAXN = (int) 3e5+5; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; ll n, k; int h[MAXN]; ll g[MAXN]; vector<ll> bas[21], bit[41]; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr); #ifdef Local freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin); freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout); #endif cin>>n>>k; for(int i = 1; i <= n; i++) cin>>h[i]>>g[i]; ll ans = 0; int s1 = n / 2, s2 = n - n / 2; for(int i = 0; i < (1<<s1); i++){ int prev = -1; ll toplam = 0; bool valid = 1; for(int j = 0; j < s1; j++){ if(((1<<j) & i) == 0) continue; if(h[1 + prev] > h[1 + j]){ toplam = 0; valid = 0; break; } toplam += g[1 + j]; prev = j; } if(!valid) continue; bas[1 + prev].push_back(toplam); if(toplam >= k) ans++; } for(int i = 0; i < (1<<s2); i++){ int st = 0, prev = -1; ll toplam = 0; bool valid = 1; for(int j = 0; j < s2; j++){ if(((1<<j) & i) == 0) continue; if(h[1 + prev] > h[1 + s1 + j]){ toplam = 0; valid = 0; break; } if(st == 0) st = 1 + s1 + j; toplam += g[1 + s1 + j]; prev = s1 + j; } if(!valid) continue; bit[st].push_back(toplam); } vector<int> v1(s1), v2(s2); for(int i = 0; i < s1; i++){ v1[i] = 1 + i; sort(bas[1 + i].begin(), bas[1 + i].end()); } for(int i = 0; i < s2; i++){ v2[i] = 1 + s1 + i; sort(bit[1 + s1 + i].begin(), bit[1 + s1 + i].end()); } sort(v1.begin(), v1.end(), [](int a, int b){ return h[a] < h[b]; }); sort(v2.begin(), v2.end(), [](int a, int b){ return h[a] < h[b]; }); vector<ll> range; int idx = -1; for(int j: v2){ while(idx + 1 < s1 && h[v1[idx + 1]] <= h[j]){ idx++; vector<ll> nw(range.size() + bas[v1[idx]].size()); merge(range.begin(), range.end(), bas[v1[idx]].begin(), bas[v1[idx]].end(), nw.begin()); range = nw; } int idx2 = (int) range.size(); //cerr<<j<<":"<<endl; for(ll x: bit[j]){ while(idx2 > 0 && range[idx2 - 1] + x >= k) idx2--; //cerr<<x<<" "<<idx2<<endl; ans += (int) range.size() - idx2; } //cerr<<endl; if(g[j] >= k) ans++; } cout<<ans<<endl; #ifdef Local cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds "; #endif }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...