oj.uz

Submission #964680

# Submission time Handle Problem Language Result Execution time Memory
964680 2024-04-17T10:25:13 Z Ahmed57 Holiday (IOI14_holiday) C++17
100 / 100
 682 ms 6916 KB 
#include "holiday.h"
 
#include "bits/stdc++.h"
using namespace std;
int ST , D , N;
int L = -1 , R = -1;
long long cur = 0;
multiset<int> lrg,sml;
long long ARR[200001];
long long ma = -1e18;
void fix(int l,int r,int sz){
    if(L==-1&&R==-1){
        for(int i = l;i<=r;i++){
            lrg.insert(ARR[i]);
            cur+=ARR[i];
        }
        L = l;
        R = r;
    }else{
        while(L>l){
            L--;
            lrg.insert(ARR[L]);
            cur+=ARR[L];
        }
        while(R<r){
            R++;
            lrg.insert(ARR[R]);
            cur+=ARR[R];
        }
        while(L<l){
            auto it = lrg.lower_bound(ARR[L]);
            if(it!=lrg.end()&&(*it)==ARR[L]){
                cur-=ARR[L];
                lrg.erase(it);
            }else{
                sml.erase(sml.lower_bound(ARR[L]));
            }
            L++;
        }
        while(R>r){
            auto it = lrg.lower_bound(ARR[R]);
            if(it!=lrg.end()&&(*it)==ARR[R]){
                cur-=ARR[R];
                lrg.erase(it);
            }else{
                sml.erase(sml.lower_bound(ARR[R]));
            }
            R--;
        }
    }
    while(sml.size()&&lrg.size()&&*(lrg.begin())<*(--sml.end())){
        int a = (*lrg.begin()), b = *(--sml.end());
        cur+=b-a;
        lrg.erase(lrg.begin());
        sml.erase((--sml.end()));
        lrg.insert(b);
        sml.insert(a);
    }
    while(lrg.size()<sz&&sml.size()){
        cur+=*(--sml.end());
        lrg.insert(*(--sml.end()));
        sml.erase((--sml.end()));
    }
    while(lrg.size()>sz){
        cur-=(*lrg.begin());
        sml.insert(*(lrg.begin()));
        lrg.erase((lrg.begin()));
    }
}
void dc(int l,int r,int lq,int rq){
    if(l>r)return ;
    int mid = (l+r)/2;
    long long ans = -1e18 ;
    int pos = -1;
    for(int i = lq;i<=rq;i++){
        int di = D-min((ST-mid)*2+(i-ST),(i-ST)*2+(ST-mid));
        if(di>=0){
        fix(mid,i,di);
        if(ans<cur){
            ans = cur;
            pos = i;
        }
        }
    }
    ma = max(ma,ans);
    dc(l,mid-1,lq,min(rq,pos));
    dc(mid+1,r,max(lq,pos),rq);
}
long long findMaxAttraction(int n,int st,int d,int arr[]){
    for(int i = 0;i<n;i++)ARR[i] = arr[i];
    ST = st;
    D = d;
    N = n;
    dc(0,st,st,n);
    return ma;
}

Compilation message

holiday.cpp: In function 'void fix(int, int, int)':
holiday.cpp:59:21: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |     while(lrg.size()<sz&&sml.size()){
      |           ~~~~~~~~~~^~~
holiday.cpp:64:21: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |     while(lrg.size()>sz){
      |           ~~~~~~~~~~^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 760 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6476 KB Output is correct
2 Correct 23 ms 6492 KB Output is correct
3 Correct 23 ms 6348 KB Output is correct
4 Correct 32 ms 6392 KB Output is correct
5 Correct 32 ms 5976 KB Output is correct
6 Correct 7 ms 2452 KB Output is correct
7 Correct 14 ms 3672 KB Output is correct
8 Correct 22 ms 4188 KB Output is correct
9 Correct 5 ms 1884 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 2 ms 856 KB Output is correct
3 Correct 2 ms 864 KB Output is correct
4 Correct 8 ms 856 KB Output is correct
5 Correct 6 ms 852 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 3 ms 860 KB Output is correct
9 Correct 3 ms 860 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 6916 KB Output is correct
2 Correct 26 ms 6740 KB Output is correct
3 Correct 110 ms 2060 KB Output is correct
4 Correct 6 ms 860 KB Output is correct
5 Correct 2 ms 856 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 3 ms 860 KB Output is correct
8 Correct 682 ms 4760 KB Output is correct
9 Correct 678 ms 4768 KB Output is correct