제출 #542233

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
542233		wildturtle	팀들 (IOI15_teams)	C++17	100 / 100	3693 ms	166532 KiB

teams

#include "teams.h"
#include<bits/stdc++.h>
#define ll long long
#define f first
#define sc second
#define pb push_back
using namespace std;
int a[500005],b[500005],n,m;
int tree[40*500005],lef[40*500005],righ[40*500005];
int root[500005],k[500005],dp[500005];
int snode,prevroot;
set <int> st1;
set < pair <int,int> > st;
vector <int> v[500005];
inline void build(int node,int le,int ri) {
    if(le==ri) {
        tree[node]=0;
        return;
    }
    snode++;
    lef[node]=snode;
    build(snode,le,(le+ri)/2);
    snode++;
    righ[node]=snode;
    build(snode,(le+ri)/2+1,ri);
    tree[node]=tree[lef[node]]+tree[righ[node]];
}
inline void update(int node,int prevnode,int le,int ri,int idx) {
    if(ri<idx || le>idx) return;
    if(le==ri) {
        tree[node]=tree[prevnode]+1;
        return;
    }
    if(idx<=(le+ri)/2) { 
        snode++; lef[node]=snode; righ[node]=righ[prevnode];
        update(snode,lef[prevnode],le,(le+ri)/2,idx); 
    } else {
        snode++; righ[node]=snode; lef[node]=lef[prevnode];
        update(snode,righ[prevnode],(le+ri)/2+1,ri,idx);
    }
    tree[node]=tree[lef[node]]+tree[righ[node]];
    
}
inline int getans(int node,int start,int end,int le,int ri) {
    if(ri<start || le>end) return 0;
    if(start<=le && ri<=end) return tree[node];
return getans(lef[node],start,end,le,(le+ri)/2)+getans(righ[node],start,end,(le+ri)/2+1,ri);
}
inline int Z(int x,int y) {
    return getans(root[y],y,n,1,n)-getans(root[x],y,n,1,n);
}
inline int go(int x,int y) {
    int le=k[y]+1; 
    int ri=n;
    int ans=0;
    while(le<=ri) {
        int mid=(le+ri)/2;
        if(dp[x]-dp[y]< -(getans(root[k[y]],mid,n,1,n)-getans(root[k[x]],mid,n,1,n))) {
            ans=mid; ri=mid-1;
        } else le=mid+1;
    }
    return ans;
}
inline void add(int x) {
    st1.insert(x);
    if (!st1.size()) return;
    int pat = -1, did = -1;
    int tim;
    if (*st1.begin() < x) pat = *(--st1.lower_bound(x));
    if (st1.upper_bound(x) != st1.end()) did = *st1.upper_bound(x);
    if (pat != -1 && did != -1) {
        tim = go(pat, did);
        if (tim) st.erase({tim,did});
    }
    if (pat != -1) {
        tim = go(pat,x);
        if (tim) st.insert({tim,x});
    }
    if (did != -1) {
        tim = go(x, did);
        if (tim) st.insert({tim,did});
    }
}
inline void del(int x) {
    if(!st1.count(x)) return;
    st1.erase(x);
    if(!st1.size()) return;
    int pat=-1;
    int did=-1;
    if(*st1.begin()<x) pat=*(--st1.upper_bound(x));
    if(st1.upper_bound(x)!=st1.end()) did=*st1.upper_bound(x);
    int tim;
    if(did!=-1) {
        tim=go(x,did);
        if(tim) st.erase({tim,did});
    }
    if(pat!=-1) {
        tim=go(pat,x);
        if(tim) st.erase({tim,x});
    }
    if(did!=-1 && pat!=-1) {
        tim=go(pat,did);
        if(tim) st.insert({tim,did});
    }
}
int can(int M, int K[]) {
    st.clear();
    st1.clear();
    m=M;
    for(int i=1;i<=m;i++) {
        k[i]=K[i-1];
        dp[i]=0;
    }
    int sum=0;
	for(int i=1;i<=m;i++) {
	    sum+=k[i];
	}
	if(sum>n) return 0;
	sort(k+1,k+1+m);
	dp[0]=0;
	add(0);
	for(int i=1;i<=m;i++) dp[i]=1e9;
	for(int i=1;i<=m;i++) {
	    while(st.size()) {
	    	multiset < pair <int,int> > :: iterator it = st.begin();
	        if((*it).f<=k[i]) del((*it).sc);
	        else break;
	    }
	    int idx=*(--st1.end());
	    dp[i]=dp[idx]+Z(k[idx],k[i])-k[i];
	    if(dp[i]<0) return 0;
	    add(i);
	}
	return 1;
}
void init(int N, int A[], int B[]) {
    n=N;
    for(int i=1;i<=n;i++) {
        a[i]=A[i-1]; b[i]=B[i-1];
	    v[a[i]].pb(b[i]);
	}
	snode=1;
	root[0]=snode;
	build(1,1,n);
	for(int i=1;i<=n;i++) {
        prevroot=root[i-1];
        root[i]=root[i-1];
        for(int j=0;j<v[i].size();j++) {
            snode++;
            root[i]=snode;
            update(root[i],prevroot,1,n,v[i][j]);
            prevroot=root[i];
        }
	}
}

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

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:148:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |         for(int j=0;j<v[i].size();j++) {
      |                     ~^~~~~~~~~~~~

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