Submission #1057471

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057471		ArthuroWich	Holiday (IOI14_holiday)	C++17	0 / 100	5069 ms	14920 KiB

holiday

#include "holiday.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long int
int segl[4*100005], seglco[4*100005], segr[4*100005], segrco[4*100005];
void updatel(int n, int l, int r, int i, int v, int c) {
    if (l == r) {
        if (c == -1) {
            segl[n] = 0;
            seglco[n] = 0;
        } else {
            segl[n] = v;
            seglco[n] = 1;
        }
    } else {
        int m = (l+r)/2;
        if (l <= i && i <= m) {
            updatel(2*n, l, m, i, v, c);
        } else {
            updatel(2*n+1, m+1, r, i, v, c);
        }
        segl[n] = segl[2*n] + segl[2*n+1]; 
        seglco[n] = seglco[2*n] + seglco[2*n+1];
    }
} 
void updater(int n, int l, int r, int i, int v, int c) {
    if (l == r) {
        if (c == -1) {
            segr[n] = 0;
            segrco[n] = 0;
        } else {
            segr[n] = v;
            segrco[n] = 1;
        }
    } else {
        int m = (l+r)/2;
        if (l <= i && i <= m) {
            updater(2*n, l, m, i, v, c);
        } else {
            updater(2*n+1, m+1, r, i, v, c);
        }
        segr[n] = segr[2*n] + segr[2*n+1]; 
        segrco[n] = segrco[2*n] + segrco[2*n+1];
    }
} 
int queryl(int n, int l, int r, int k) {
    if (seglco[n] <= k) {
        return segl[n];
    } else {
        int m = (l+r)/2, v = 0;
        if (seglco[2*n+1] >= k) {
            return queryl(2*n+1, m+1, r, k);
        } else {
            v += queryl(2*n+1, m+1, r, seglco[2*n+1]);
            k -= seglco[2*n+1];
            v += queryl(2*n, l, m, k);
            return v;
        }
    }
}
int queryr(int n, int l, int r, int k) {
    if (segrco[n] <= k) {
        return segr[n];
    } else {
        int m = (l+r)/2, v = 0;
        if (segrco[2*n+1] >= k) {
            return queryr(2*n+1, m+1, r, k);
        } else {
            v += queryr(2*n+1, m+1, r, segrco[2*n+1]);
            k -= segrco[2*n+1];
            v += queryr(2*n, l, m, k);
            return v;
        }
    }
}
int n, d, st, l[200005], r[200005], at[200005];
pair<int, int> dpr[200005];
void calcr(int ld, int rd, int li, int ri) {
    int m = (ld+rd)/2;
    for (int i = li; i <= ri; i++) {
        if (m-(i-li) <= 0) {
            break;
        }
        updater(1, 0, n-1, r[i], at[i], 1);
        int v = queryr(1, 0, n-1, m-(i-li));
        if (v == dpr[m].first && dpr[m].second > i) {
            dpr[m].second = i;
        } else if (v > dpr[m].first) {
            dpr[m].first = v;
            dpr[m].second = i;
        }
    }
    for (int i = li; i <= ri; i++) {
        updater(1, 0, n-1, r[i], at[i], -1);
    }
    if (ld != rd) {
        calcr(ld, m, li, dpr[m].second);
        calcr(m+1, rd, li, ri);
    }
}
int findMaxAttraction(int32_t N, int32_t st, int32_t D, int32_t attraction[]) {
    int ans = 0;
    n = N;
    d = D;
    vector<pair<int, int>> lat, rat;
    for (int i = 0; i < n; i++) {
        at[i] = attraction[i];
    }
    for (int i = 0; i < st; i++) {
        lat.push_back({at[i], i});
    }
    for (int i = st; i < n; i++) {
        rat.push_back({at[i], i});
    }
    sort(lat.begin(), lat.end());
    sort(rat.begin(), rat.end());
    for (int i = 0; i < lat.size(); i++) {
        l[lat[i].second] = i;
    }
    for (int i = 0; i < rat.size(); i++) {
        r[rat[i].second] = i;
    }
    calcr(1, d, st, n-1);
    return dpr[d].first;
}

Compilation message (stderr)

holiday.cpp: In function 'long long int findMaxAttraction(int32_t, int32_t, int32_t, int32_t*)':
holiday.cpp:117:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |     for (int i = 0; i < lat.size(); i++) {
      |                     ~~^~~~~~~~~~~~
holiday.cpp:120:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for (int i = 0; i < rat.size(); i++) {
      |                     ~~^~~~~~~~~~~~
holiday.cpp:102:9: warning: unused variable 'ans' [-Wunused-variable]
  102 |     int ans = 0;
      |         ^~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 17
• Subtask 4: 0 / 53