Submission #669867

#	Time	Username	Problem	Language	Result	Execution time	Memory
669867		victor_gao	Teams (IOI15_teams)	C++17	100 / 100	2221 ms	174096 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];
int n;
struct segtree{
    vector<pii>seg[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;
        sort(seg[i].begin(),seg[i].end());
        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]+=min(cl,last); last-=cl;
            out[2*i+1]+=max(last,0); 
        }
    }
    void init(){ out[1]=0; era[1]=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);
    }
    void queryp(int l,int r,int i,int can,int need){
        if (l==r){
            out[i]+=need;
            return;
        }
        int mid=(l+r)>>1; push(i);
        int cl=count(2*i,can);
        if (cl>=need) queryp(l,mid,2*i,can,need);
        else {
            out[2*i]+=cl;
            queryp(mid+1,r,2*i+1,can,need-cl);
        }
        out[i]=out[2*i]+out[2*i+1];
    }
}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<M;i++){
        int qus=K[i]+seg.query(1,n,1,1,K[i]-1,K[i]);
        if (qus>seg.count(1,K[i])) return 0;
        seg.queryp(1,n,1,K[i],qus);
    }
    return 1;
}

Compilation message (stderr)

teams.cpp: In member function 'int segtree::count(int, int)':
teams.cpp:14: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]
   14 |         int p=(upper_bound(seg[i].begin(),seg[i].end(),make_pair(can,2))-seg[i].begin())-out[i];
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~

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