제출 #1362555

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1362555		jbn8	CERN (COI24_cern)	C++20	0 / 100	4098 ms	236088 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){
    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, const vector<vector<int>> tree, 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 > size/2){
        res[id] = 1;
    }else{
        res[id] = nb2p;
        if(size%2 == 1)
            res[id] += nb1;
    }
    currange = rangesT[id];
    for(int nei:tree[id]){
        currange = updatesubtree(rangesT, types, tree, heatmap, nbTypes, maxi, res, currange, nei);
    }
    return currange;
}


int main(){
    scanf("%d %d\n", &N, &Q);
    vector<int> types(N);
    for(int i=0; i<N; i++){
        scanf("%d", &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<vector<int>> tree(Q);
    vector<int> res(Q, -1);
    int id=-1, lastend=-1;
    for(int i=0; i<Q; i++){
        if(ranges[i].end > lastend){
            lastend = ranges[i].end;
            id = ranges[i].id;
        }else{
            int cur = id;
            do{
                if(tree[cur].empty()){
                    tree[cur].push_back(ranges[i].id);
                    break;
                }else{
                    if(rangesT[tree[cur].back()].end > ranges[i].end){
                        cur = tree[cur].back();
                    }else{
                        tree[cur].push_back(ranges[i].id);
                        break;
                    }
                }
            }while(1);
        }
    }
    range lastrange = {0, 0, -1};
    vector<int> nbTypes(N);
    int nb2p = 0;
    int nb1 = 0;
    vector<int> heatmap(N);
    heatmap[0] = N;
    int maxi = 0;
    for(int i=0; i<Q; i++){
        if(res[ranges[i].id] != -1)continue;
        lastrange = updatesubtree(rangesT, types, tree, heatmap, nbTypes, maxi, res, lastrange, ranges[i].id);
    }
    for(int i=0; i<Q; i++){
        printf("%d\n", res[i]);
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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

• 서브태스크 0: 0 / 0
• 서브태스크 1: 0 / 13
• 서브태스크 2: 0 / 19
• 서브태스크 3: 0 / 17
• 서브태스크 4: 0 / 19
• 서브태스크 5: 0 / 32