Submission #1362582

#	Time	Username	Problem	Language	Result	Execution time	Memory
1362582		jbn8	CERN (COI24_cern)	C++20	0 / 100	4094 ms	21932 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);
    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<range> ranges(Q);
    vector<range> rangesT(Q);
    for(int i=0; i<Q; i++){
        scanf("%d%d", &ranges[i].start, &ranges[i].end);
        ranges[i].start--;
        ranges[i].id = i;
        rangesT[i] = ranges[i];
    }
    sort(ranges.begin(), ranges.end(), [&](range a, range b){return a.start < 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++){
        if(res[ranges[i].id] != -1)continue;
        lastrange = updatesubtree(rangesT, types, heatmap, nbTypes, maxi, res, lastrange, ranges[i].id);
    }
    for(int i=0; i<Q; i++){
        printf("%d\n", res[i]);
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     scanf("%d %d\n", &N, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         scanf("%d", &types[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         scanf("%d%d", &ranges[i].start, &ranges[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