oj.uz

Submission #374541

# Submission time Handle Problem Language Result Execution time Memory
374541 2021-03-07T11:25:04 Z Atill83 San (COCI17_san) C++14
120 / 120
 184 ms 13084 KB 
#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[100], bit[100];



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;
            if(x >= k)
                ans++;
        }
        //cerr<<endl;

    }   

    cout<<ans<<endl;
    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

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 15 ms 1940 KB Output is correct
2 Correct 3 ms 492 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2948 KB Output is correct
2 Correct 18 ms 1160 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 13084 KB Output is correct
2 Correct 96 ms 4324 KB Output is correct