제출 #1015330

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1015330		HuyAT	팀들 (IOI15_teams)	C++14	0 / 100	290 ms	56788 KiB

teams

#include "teams.h"
#include<bits/stdc++.h>
#define newl '\n'

const int N = 5e5 + 10;

struct SegmentTree{
    std::vector<int> st;
    SegmentTree(){

    }
    void expand(int n){
        st.resize(n * 4 + 10,N);
    }
    void update(int l,int r,int pos,int val,int id = 1){
        if(l > pos || r < pos){
            return;
        }
        if(l == r){
            st[id] = val;
            return;
        }
        int mid = (l + r) / 2;
        update(l,mid,pos,val,id << 1);
        update(mid + 1,r,pos,val,id << 1 | 1);
        st[id] = std::min(st[id << 1],st[id << 1 | 1]);
    }
    int walk(int l,int r,int pos,int val,int id = 1){
        if(st[id] > val || r < pos){
            return -1;
        }
        if(l == r){
            return l;
        }
        int mid = (l + r) / 2;
        if(st[id << 1] <= val){
            int it = walk(l,mid,pos,val,id << 1);
            if(it != -1){
                return it;
            }
        }
        return walk(mid + 1,r,pos,val,id << 1 | 1);
    }
};
int n,a[N + 1],b[N + 1],k[N + 1];

struct cmp{
    bool operator ()(int id,int id1){
        return a[id] > a[id1];
    }
};
std::vector<int> idx;
SegmentTree st;
std::priority_queue<int,std::vector<int>,cmp> pq[N + 1];

void init(int N, int A[], int B[]) {
    n = N;
    st.expand(n);
    a[n + 1] = 5e5 + 10;
    for(int i = 1;i <= n;++i){
        a[i] = A[i - 1];
        b[i] = B[i - 1];
        pq[i].push(n + 1);
        pq[b[i]].push(i);
    }
    for(int i = 1;i <= n;++i){
        st.update(1,n,b[i],a[pq[i].top()]);
    }
}

int can(int M, int K[]) {
    while(!idx.empty()){
        pq[b[idx.back()]].push(idx.back());
        st.update(1,n,b[idx.back()],a[idx.back()]);
        idx.pop_back();
    }
//    std::cout << st.getMin(1,n,1) << newl;
    for(int i = 1;i <= M;++i){
        k[i] = K[i - 1];
    }
    std::sort(k + 1,k + M + 1);
    for(int i = 1;i <= M;++i){
        int it = st.walk(1,n,k[i],k[i]);
        if(it == -1){
            return 0;
        }
        idx.emplace_back(it);
        pq[it].pop();
        st.update(1,n,b[it],a[pq[it].top()]);
    }
	return 1;
}

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

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:56:15: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   56 | void init(int N, int A[], int B[]) {
      |           ~~~~^
teams.cpp:5:11: note: shadowed declaration is here
    5 | const int N = 5e5 + 10;
      |           ^

• Subtask 1: 0 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23