Submission #577697

#	Time	Username	Problem	Language	Result	Execution time	Memory
577697		SlavicG	Holiday (IOI14_holiday)	C++17	0 / 100	37 ms	9308 KiB

holiday

#include "bits/stdc++.h"
#include"holiday.h"
using namespace std;

#define ll long long

const int N = 2e5 + 10;
ll c[N], sum[N], cnt[N];

ll query(int i, int l, int r, int k) {
    if(k <= 0) return 0;
    if(cnt[i] <= k) return sum[i];
    int mid = l + r >> 1;
    if(cnt[2 * i] > k) return query(2 * i, l, mid, k);
    return sum[2 * i] + query(2 * i + 1, mid + 1, r, k - cnt[2 * i]);
}

void modif(int i, int l, int r, int pos, bool b) {
    if(l > pos || r < pos) return;
    if(l == pos && r == pos) {
        sum[i] = (b ? c[i] : 0);
        cnt[i] = b;
        return;
    }
    int mid = l + r >> 1;
    modif(2 * i, l, mid, pos, b);
    modif(2 * i + 1, mid + 1, r, pos, b);
    sum[i] = sum[2 * i] + sum[2 * i + 1];
    cnt[i] = cnt[2 * i] + cnt[2 * i + 1];
}

long long int findMaxAttraction(int n, int start, int d, int a[]) {
    vector<pair<int, int>> x;
    for(int i = 0; i < n; ++i) x.push_back({a[i], i});
    sort(x.rbegin(), x.rend());
    map<pair<int, int>, int> mp;
    for(int i = 0; i < n; ++i) {
        c[i] = x[i].first;
        mp[{x[i].first, x[i].second}] = i;
    }
    ll ans = 0;
    for(int i = 0; i < n; ++i) {
        ans = max(ans, query(1, 0, n - 1, d));
        --d;
    }
    return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'long long int query(int, int, int, int)':
holiday.cpp:13:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 |     int mid = l + r >> 1;
      |               ~~^~~
holiday.cpp: In function 'void modif(int, int, int, int, bool)':
holiday.cpp:25:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |     int mid = l + r >> 1;
      |               ~~^~~

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