Submission #1095782

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095782		dosts	Holiday (IOI14_holiday)	C++17	100 / 100	598 ms	7000 KiB

holiday

//Dost SEFEROĞLU
#include <bits/stdc++.h>
#include"holiday.h"
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
using namespace std;
using lint  = long long;
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
const lint MOD = 1e9+7,inf = 2e18;
const int N = 1e5+50,Q = 2e5+50;
 
vector<lint> a(N),ans(N);
int M;
int L,R;
 
multiset<int> used,noused;
lint usum,nsum;
 
void del(int p) {
    if (!noused.empty() && *noused.rbegin() >= a[p]) {
        nsum-=a[p];
        assert(noused.find(a[p]) != noused.end());
        noused.erase(noused.find(a[p]));
    }
    else {
        assert(used.find(a[p]) != used.end());
        usum-=a[p];
        used.erase(used.find(a[p]));
    }
}
 
void ins(int p) {
    if (used.empty() || a[p] >= *used.begin()) {
        usum+=a[p];
        used.insert(a[p]);
    }
    else {
        nsum+=a[p];
        noused.insert(a[p]);
    }
}
 
lint ask(int x) {
    if (!x) return 0;
    while (used.size() < x && !noused.empty()) {
        used.insert(*noused.rbegin());
        usum+=*noused.rbegin();
        nsum-=*noused.rbegin();
        noused.erase(prev(noused.end()));
    }
    while (used.size() > x) {
        noused.insert(*used.begin());
        nsum+=*used.begin();
        usum-=*used.begin();
        used.erase(used.begin());
    }
    if (used.size() == x) return usum;
    return 0;
}
 
void fix(int l,int r) {
    while (L < l) del(L++);
    while (R > r) del(R--);
    while (L > l) ins(--L);
    while (R < r) ins(++R);
}
 
int D;
void dnc(int l,int r,int optl,int optr) {
    if (l > r) return;
    int m = (l+r) >> 1;
    lint best = 0,opt = optl;
    for (int i=optl;i<=optr;i++) {
        fix(m,i);
        int take = D-min(2*(M-L)+(R-M),2*(R-M)+(M-L));
      	take = min(take,R-L+1);
        take = max(take,0);
        if (ask(take) > best) {
            best = ask(take);
            opt = i;
        }
    }
    ans[m] = best;
    dnc(l,m-1,optl,opt),dnc(m+1,r,opt,optr);
}
 
lint findMaxAttraction(int n, int start, int d, int attraction[]) {
    for (int i=0;i<n;i++) a[i+1] = attraction[i];
    start++;
    D = d;
    M = start;
    ins(M);
    L = R = M;
    dnc(1,start,start,n);
    return *max_element(ans.begin()+1,ans.begin()+start+1);
}

Compilation message (stderr)

holiday.cpp: In function 'lint ask(int)':
holiday.cpp:49:24: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |     while (used.size() < x && !noused.empty()) {
      |            ~~~~~~~~~~~~^~~
holiday.cpp:55:24: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |     while (used.size() > x) {
      |            ~~~~~~~~~~~~^~~
holiday.cpp:61:21: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   61 |     if (used.size() == x) return usum;
      |         ~~~~~~~~~~~~^~~~

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