제출 #669658

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
669658		victor_gao	팀들 (IOI15_teams)	C++17	13 / 100	4104 ms	274116 KiB

teams

#include <bits/stdc++.h>
#define pii pair<int,int>
#define x first
#define y second
#define MAXN 500005
using namespace std;
pii stud[MAXN];
vector<pair<pii,int> >md_seg;
int n;
struct segtree{
    vector<pii>seg[4*MAXN];
    vector<int>cnt[4*MAXN];
    int out[4*MAXN];
    bool era[4*MAXN];
    int count(int i,int can){
        int p=(upper_bound(seg[i].begin(),seg[i].end(),make_pair(can,2))-seg[i].begin())-out[i];
        return max(p,0);
    }
    void build(int l,int r,int i){
        era[i]=0; out[i]=0;
        if (!seg[i].empty()){
            sort(seg[i].begin(),seg[i].end());
            cnt[i].resize(seg[i].size()+2,0);
            cnt[i][0]=seg[i][0].y;
            for (int j=1;j<(int)(seg[i].size());j++)
                cnt[i][j]=cnt[i][j-1]+seg[i][j].y;
        }
        if (l==r)
            return;
        int mid=(l+r)>>1;
        build(l,mid,2*i);
        build(mid+1,r,2*i+1);
    }
    void add(int l,int r,int i,int p,int c){
        if (l==r){
            seg[i].push_back({c,0});
            return;
        }
        int mid=(l+r)>>1;
        if (p<=mid){
            seg[i].push_back({c,0});
            add(l,mid,2*i,p,c);
        } 
        else {
            seg[i].push_back({c,1});
            add(mid+1,r,2*i+1,p,c);
        }
    }
    void push(int i){
        if (era[i]){
            era[2*i]=1; era[2*i+1]=1;
            out[2*i]=0; out[2*i+1]=0;
            era[i]=0;
        }
        if (out[i]!=out[2*i]+out[2*i+1]&&out[i]){
            int val=seg[i][out[i]-1].x;
            out[2*i]=count(2*i,val-1);
            out[2*i+1]=count(2*i+1,val-1);
            int last=out[i]-out[2*i]-out[2*i+1];
            int cl=count(2*i,val);
            out[2*i]+=cl; last-=cl;
            out[2*i+1]+=max(last,0); 
        }
    }
    void init(){ out[1]=0; era[1]=1; }
    void cut(int l,int r,int i,int ll,int rr){
        if (ll<=l&&rr>=r){
            md_seg.push_back({{l,r},i});
            if (l<r) push(i);
            return;
        }
        int mid=(l+r)>>1; push(i);
        if (rr<=mid) cut(l,mid,2*i,ll,rr);
        else if (ll>mid) cut(mid+1,r,2*i+1,ll,rr);
        else {
            cut(l,mid,2*i,ll,rr);
            cut(mid+1,r,2*i+1,ll,rr);
        }
    }
    void pull(int l,int r,int i,int ll,int rr){
        if (ll<=l&&rr>=r)
            return;
        int mid=(l+r)>>1;
        if (rr<=mid) pull(l,mid,2*i,ll,rr);
        else if (ll>mid) pull(mid+1,r,2*i+1,ll,rr);
        else {
            pull(l,mid,2*i,ll,rr);
            pull(mid+1,r,2*i+1,ll,rr);
        }
        out[i]=out[2*i]+out[2*i+1];
    }
    int query(int l,int r,int i,int ll,int rr,int can){
        if (ll>rr) return 0;
        if (ll<=l&&rr>=r) return count(i,can);
        int mid=(l+r)>>1; push(i);
        if (rr<=mid) return query(l,mid,2*i,ll,rr,can);
        else if (ll>mid) return query(mid+1,r,2*i+1,ll,rr,can);
        else return query(l,mid,2*i,ll,rr,can)+query(mid+1,r,2*i+1,ll,rr,can);
    }
    int queryp(int l,int r,int i,int can,int need){
    //    cout<<l<<" ~ "<<r<<" "<<need<<'\n';
        if (l==r){
            if (need-count(i,can)>0) return -1;
            return l;
        } 
        int mid=(l+r)>>1; push(i);
        int cl=count(2*i,can);
        if (cl>=need) return queryp(l,mid,2*i,can,need);
        else return queryp(mid+1,r,2*i+1,can,need-cl);
    }
}seg;

void init(int N,int A[],int B[]){
    n=N;
    for (int i=1;i<=N;i++)
        stud[i]={A[i-1],B[i-1]};
    for (int i=1;i<=n;i++){
        seg.add(1,n,1,stud[i].y,stud[i].x);
    }
    seg.build(1,n,1);
}
bool can(int M,int K[]){
    sort(K,K+M);
    seg.init();
    for (int i=0;i<=4*n+3;i++)
        seg.out[i]=0;
    for (int i=0;i<M;i++){
        int qus=K[i]+seg.query(1,n,1,1,K[i]-1,K[i]);
      //  cout<<"OK\n";
        int p=seg.queryp(1,n,1,K[i],qus),need_out=K[i];
      //  cout<<i<<" "<<K[i]<<" -> "<<p<<" "<<qus<<" "<<"\n";
        if (p==-1) return 0;
        seg.cut(1,n,1,K[i],p);
        for (auto [s,j]:md_seg){
            int cnt=seg.count(j,K[i]);
     //       cout<<"out "<<s.x<<' '<<s.y<<" "<<min(cnt,need_out)<<'\n';
            seg.out[j]+=min(cnt,need_out);
            need_out-=min(cnt,need_out);
            if (s.x!=s.y) seg.push(j);
        }
        md_seg.clear();
       // cout<<"after "<<need_out<<'\n';
        seg.pull(1,n,1,K[i],p);
       // cout<<i<<" finish\n";
    }
    return 1;
}

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

teams.cpp: In member function 'int segtree::count(int, int)':
teams.cpp:16:89: warning: conversion from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   16 |         int p=(upper_bound(seg[i].begin(),seg[i].end(),make_pair(can,2))-seg[i].begin())-out[i];
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~

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