Submission #1362597

#	Time	Username	Problem	Language	Result	Execution time	Memory
1362597		jbn8	CERN (COI24_cern)	C++20	0 / 100	4093 ms	18020 KiB

Main

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int N, Q;

struct range{
    int start, end;
    int id;
};

template<int add>
void update1(const vector<int>& types, vector<int>& heatmap, vector<int>& nbTypes, int& maxi, int index){
    heatmap[nbTypes[types[index]]]--;
    nbTypes[types[index]] += add;
    heatmap[nbTypes[types[index]]]++;
    if constexpr(add == 1){
        if(heatmap[maxi+1])maxi++;
    }else{
        if(!heatmap[maxi])maxi--;
    }
}

void update(const vector<int>& types, vector<int>& heatmap, vector<int>& nbTypes, int& maxi, range currange, range nextrange){
    //printf("%d %d -> %d %d\n", currange.start, currange.end, nextrange.start, nextrange.end);
    if(currange.end > nextrange.end)swap(currange.end, nextrange.end);
    for(int i=currange.end; i<nextrange.end; i++){
        update1<1>(types, heatmap, nbTypes, maxi, i);
    }
    for(int i=currange.start; i<nextrange.start; i++){
        update1<-1>(types, heatmap, nbTypes, maxi, i);
    }
}

range updatesubtree(const vector<range>& rangesT, const vector<int>& types, vector<int>& heatmap, vector<int>& nbTypes, int& maxi, vector<int>& res, range currange, int id){
    update(types, heatmap, nbTypes, maxi, currange, rangesT[id]);
    int nb1 = heatmap[1];
    int nb2p = N-heatmap[0]-heatmap[1];
    int size = rangesT[id].end-rangesT[id].start;
    if(maxi*2 >= size){
        res[id] = 1;
    }else{
        res[id] = nb2p;
        if(size%2 == 1)
            res[id] += nb1;
    }
    return rangesT[id];
}


int main(){
    scanf("%d %d\n", &N, &Q);
    vector<int> types(N);
    for(int i=0; i<N; i++){
        scanf("%d", &types[i]);
        types[i]--;
    }
    vector<int> sortedIds(Q);
    vector<range> rangesT(Q);
    for(int i=0; i<Q; i++){
        scanf("%d%d", &rangesT[i].start, &rangesT[i].end);
        rangesT[i].start--;
        sortedIds[i] = i;
    }
    sort(sortedIds.begin(), sortedIds.end(), [&](int a, int b){return rangesT[a].start < rangesT[b].start;});
    vector<int> res(Q, -1);
    range lastrange = {0, 0, -1};
    vector<int> nbTypes(N);
    int nb2p = 0;
    int nb1 = 0;
    vector<int> heatmap(N*2+1);
    heatmap[0] = N;
    int maxi = 0;
    for(int i=0; i<Q; i++){
        lastrange = updatesubtree(rangesT, types, heatmap, nbTypes, maxi, res, lastrange, sortedIds[i]);
    }
    for(int i=0; i<Q; i++){
        printf("%d\n", res[i]);
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |     scanf("%d %d\n", &N, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         scanf("%d", &types[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         scanf("%d%d", &rangesT[i].start, &rangesT[i].end);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 0 / 13
• Subtask 2: 0 / 19
• Subtask 3: 0 / 17
• Subtask 4: 0 / 19
• Subtask 5: 0 / 32